Greatest Common Divisor Traversal - Leetcode 2709 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑‍💼 LinkedIn: / navdeep-singh-3aaa14161
🐦 Twitter: / neetcode1
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
Problem Link: leetcode.com/problems/greates...
0:00 - Read the problem
0:24 - Drawing Explanation
15:22 - Coding Explanation
leetcode 2709
#neetcode #leetcode #python

[@akialter]

Streak destroyer problem

[@sayandey1478]

self destruction problem, every moment there is a twist

[@edwardj4454]

Your explanations are always super well structured that after hearing the first few minutes I already get the intuition for solving the entire problem. Thanks!

[@swanv951]

The n^2 solution too works very efficiently if you exit out when a number isn't "matched" with any other number

[@siddharth-gandhi]

tysm, figured out union find but was getting tle. prime explanation helped :D

[@jamesabasifreke]

7:30 I doubt you can do union find merge in constant time. It’s usually log n time even with ranking and path compression 😊

[@saminhasan87]

every video of yours deserves more than one like. Thank you for your efforts!

[@MP-ny3ep]

Great explanation! Thank you so very much

[@mnaresh3382]

I think the part where finding the prime numbers could have been explained better, after some research this is what I found, The method that is used in this problem to achieve root(n) time complexity is called Trial Division Method, which follows three steps 1) Let us consider N be the given number for which we need to find the factors, so we initialize it 2) Iterate through all potential factors(p) starting from 2 till root(N), -For each p, check if p is a prime factor(divides N completely), if so add it to our factors, and then divide N by p ( N= N/p) -repeat the above step until it is no longer divisible by p, For me this is was hard to understand, but basically consider this, let us say we have no 60, ofcourse we know 64 is divisible by 2,4,8,16 but we don't need all those numbers except just 2, this can be achieved by repeatedly multiplying the N by 2(which is p) by doing this we are essentially reducing the Number N to the point where N will not be divisible by other numbers such as 4,8,16 etc. 3) after iterating until root(n) we would either get 1, or some other number, in that case, this particular number is the only prime-factor that we are left out with the set of all prime factors of N. I hope this helps, you can also check this simple python code which makes much more sense from taking a glance at it. def prime_factors(n): factors = [] # Check for divisibility by 2 separately while n % 2 == 0: factors.append(2) n = n // 2 # Check for divisibility by odd numbers from 3 up to sqrt(n) for i in range(3, int(n**0.5) + 1, 2): while n % i == 0: factors.append(i) n = n // i # If n is a prime greater than 2, add it to factors if n > 2: factors.append(n) return factors # Example usage: n = 84 print(prime_factors(n)) # Output: [2, 2, 3, 7]

[@user-ml4je5pq7q]

Please teach a ~30 min crash course on object oriented programming in python, like your other video "python for coding interviews". You are definitely the best teacher out there.

[@saminhasan87]

where to find your advanced algorithm course for learning union find?

[@Ari-pq4db]

Keep em coming ❤

[@luisdmoralesh]

rlly good explanation, ty

[@tizekodnoon8305]

Neato!!! Brain's hurting!🤯

[@mrmcpherson2722]

This man has probably saved so many daily streaks at this point. 😂

[@mudamalajayasimhareddy9517]

Thanks.🙃

[@akhilchauhan9417]

Using Sieve of Eratosthenes for building primes factors of each number. My question is as you can see I'm checking for factor in map twice, How can I modify it such that I only have to do it once other that writing a function for that? def canTraverseAllPairs(self, nums: List[int]) -> bool: m = len(nums) uf = UnionFind(m) mx = max(nums) factor = {} # f -> index of the number with factor f primes = [i for i in range(mx + 1)] for i in range(2, mx + 1): if primes[i] == i: j = i * i while j 1: while primes[n] != n: if primes[n] in factor: uf.union(i, factor[primes[n]]) else: factor[primes[n]] = i n = n // primes[n] if primes[n] in factor: uf.union(i, factor[primes[n]]) else: factor[primes[n]] = i return uf.count == 1

[@varunpalsingh3822]

tysm

[@amaanshaikh7292]

Hey, Can you also upsolve the weekly/biweekly contests it helps a lot Thankyou. Love your efforts ❤

[@drewstake3881]

He should livestream the weekly contest, I think that'll be so entertaining see the thought process live

[@michaelharris1305]

yes please

[@belphegor32]

@ake3881 I think you have never attended a leetcode contest, because even if you think about it, its obvious, that it breaks the whole point of contest, there will be people who would just copy his solutions (it is prohibited by the rules to upload solutions before the end of contest, they even hide testcases, so people wont brute code some test cases). If you meant like uploading his thoughts and solutions right after contests, that is ok, but there are many people who already do this.

[@mrf92]

1 is not a prime. because by definition a prime number can't be factorized with other prime numbers. but if you consider 1 as a prime then existence of other prime numbers isn't possible.

[@user-gb5id1nt8v]

140 th like done:)) less go! ur great teacher

[@BlunderArmour]

RIP streak Jan 2024 - Feb 2024.

[@user-j5ja95]

Do you do LC everyday while having a full time job? If so how do you do it? I'm so tired after work and don't wanna do anything, so I usually LC only on weekends

[@ShikaIE]

I just solve daily challenge everyday. Should only take half hour at most except the problem like this 😂! Not really for interview prep only but just to keep my mind active because you rarely solve difficult algo problem at work.

[@1vader]

Afaik KZbin and working on the NeetCode website is his full time job.

[@aidanthompson5053]

This is all a test of morality. Will you do the right thing: sacrifice your ego or betray your own people

[@Kaviarasu_NS]

What tools do you use for making these tutorials?

[@belphegor32]

he said, that he just uses paint, I guess he has some personal settings in it. Some people use photoshop, which I think is also better to use, if you know how to set it up properly.

[@Kaviarasu_NS]

@@belphegor32 I’m planning to create educational animation using adobe animate, was asking for a personal suggestion

[@RuslanKovtun]

14:04 - Rounding is bad idea, better to rewrite it other way around - compare squares instead of square roots.

[@thebigpaff]

that's what he did in the code

[@rajsuriyang3427]

I don't even know what is union find.

[@Ari-pq4db]

Noice ❤

[@get_out_it]

too hard bro

[@micorlov4321]

4:40 Is 1 a prime factor?

[@IK-xk7ex]

I see that I'm still weak after solving 467 problems that I couldn't recognise and understand the problem by myself :(

[@hiteshwadhwani629]

you are not alone 🥲

[@lian1238]

Learn data structures. Learn algorithms. There are more than one way to solve any problem. If you know common algorithms, you can solve most leetcode problems because thats the answer they are looking for. Also remember that being bad at leetcode doesn’t mean you are bad at coding. Also, idk if itll help you, but the way i do leetcode is copy the code into my own editor and run a loop in the terminal that runs the file forever. So when i save, the new code and output are shown right away. Also use a lot of print statements. I then copy the cases from leetcode and run the function with their input and expected value.

[@hiteshwadhwani629]

@@lian1238 thanks

[@BurhanAijaz]

easier : class Solution: def canTraverseAllPairs(self, nums: List[int]) -> bool: if len(nums)==1:return True nums = set(nums) if 1 in nums:return False if len(nums)==1:return True nums = sorted(nums,reverse=True) for i in range(len(nums)-1): for j in range(i+1,len(nums)): if gcd(nums[i],nums[j])-1: nums[j]*=nums[i] break else: return False return True

[@xtremeff5428]

Thanks for this, I was trying hard but this helped me save my streak

[@groot3271]

Start coding in C++ again...

[@arijaa.9315]

To be honest it is hard for me .

[@aidanthompson5053]

You are obligated to get rich so you can give back to your people and free them from financial slavery

[@cocoscacao6102]

I bet you'd like my algo problem... Wanna solve it for me xD?

[@rohan14040]

i hate this problem

[@ethronixNativeCX]

TAGGR The first FULLY decentralized social network powered by the Internet Computer.