Greatest Common Divisor Traversal - Leetcode 2709 - Python

0:00 - Read the problem
0:24 - Drawing Explanation
15:22 - Coding Explanation

leetcode 2709

#neetcode #leetcode #python

[swanv]

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

[edwardj]

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!

[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 😊

[VISHALS-hy]

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.

[saminhasan]

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

[saminhasan]

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

[amaanshaikh]

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

[jja]

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

[MP-nyep]

Great explanation! Thank you so very much

[akhilchauhan]

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 <= mx:
primes[j] = i
j += i

for i, n in enumerate(nums):
if n > 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

[mrmcpherson]

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

[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

[RuslanKovtun]

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

[mrf]

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.

[aidanthompson]

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

[Kaviarasu_S]

What tools do you use for making these tutorials?

[DeveshSoni-us]

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

[rajsuriyang]

I don't even know what is union find.

[IK-xkex]

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