2709. Greatest Common Divisor Traversal

HardUnion FindArrayMathNumber Theory
Leetcode Link

Problem Description

You have an array of integers nums where each element is at a specific index (0-indexed). You can move between two indices i and j (where i ≠ j) only if the greatest common divisor (GCD) of nums[i] and nums[j] is greater than 1. In other words, you can traverse from index i to index j if the values at those positions share at least one common factor other than 1.

The problem asks you to determine if it's possible to create a path between every pair of indices in the array. Specifically, for any two indices i and j where i < j, there must exist some sequence of valid traversals that connects them (possibly through intermediate indices).

For example:

  • If nums = [2, 4, 6], you can traverse between any pair of indices because all numbers share the factor 2
  • If nums = [2, 3, 5], you cannot traverse between any indices because no two numbers share a common factor greater than 1

The function should return true if all pairs of indices are reachable from each other through some path of valid traversals, and false otherwise.

The solution uses a Union-Find (Disjoint Set Union) data structure to group indices that can be connected. It pre-computes prime factors for numbers and connects indices that share prime factors. If all indices end up in the same connected component, then all pairs are reachable from each other.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is recognizing this as a graph connectivity problem. If we think of each index as a node, and draw an edge between two indices when their values share a common factor greater than 1, then the problem asks: "Is this graph fully connected?"

Initially, we might consider checking every pair of numbers to see if gcd(nums[i], nums[j]) > 1, but this would be inefficient for large arrays.

A crucial observation is that two numbers share a common factor greater than 1 if and only if they share at least one prime factor. For example, 6 and 15 both contain the prime factor 3, so gcd(6, 15) = 3 > 1.

This leads to a clever approach: instead of directly connecting indices whose values share factors, we can use prime factors as "bridges." If two numbers share a prime factor p, they're both connected to p, and therefore connected to each other through p.

Here's the transformation:

  • Instead of checking if index i can connect to index j directly
  • We connect index i to all prime factors of nums[i]
  • We connect index j to all prime factors of nums[j]
  • If they share any prime factor, they'll be in the same connected component

For example, if nums = [6, 10, 15]:

  • Index 0 (value 6) connects to primes 2 and 3
  • Index 1 (value 10) connects to primes 2 and 5
  • Index 2 (value 15) connects to primes 3 and 5
  • All indices end up connected through this prime factor network

Using Union-Find to track these connections efficiently determines if all indices form a single connected component. If they do, every pair of indices is reachable; otherwise, some pairs are isolated from each other.

Learn more about Union Find and Math patterns.

Solution Implementation

1from collections import defaultdict 2from typing import List 3 4 5class UnionFind: 6 """Union-Find (Disjoint Set Union) data structure with path compression and union by size.""" 7 8 def __init__(self, n: int): 9 """Initialize Union-Find with n elements.""" 10 self.parent = list(range(n)) # Each element is initially its own parent 11 self.size = [1] * n # Size of each component 12 13 def find(self, x: int) -> int: 14 """Find the root of element x with path compression.""" 15 if self.parent[x] != x: 16 self.parent[x] = self.find(self.parent[x]) # Path compression 17 return self.parent[x] 18 19 def union(self, a: int, b: int) -> bool: 20 """ 21 Union two elements a and b. 22 Returns True if they were in different sets, False if already in same set. 23 """ 24 root_a, root_b = self.find(a), self.find(b) 25 26 if root_a == root_b: 27 return False # Already in same set 28 29 # Union by size: attach smaller tree under root of larger tree 30 if self.size[root_a] > self.size[root_b]: 31 self.parent[root_b] = root_a 32 self.size[root_a] += self.size[root_b] 33 else: 34 self.parent[root_a] = root_b 35 self.size[root_b] += self.size[root_a] 36 37 return True 38 39 40# Precompute prime factors for all numbers up to MAX_VALUE 41MAX_VALUE = 100010 42prime_factors = defaultdict(list) 43 44for number in range(1, MAX_VALUE + 1): 45 current_value = number 46 divisor = 2 47 48 # Find all prime factors by trial division 49 while divisor * divisor <= current_value: 50 if current_value % divisor == 0: 51 prime_factors[number].append(divisor) 52 # Remove all occurrences of this prime factor 53 while current_value % divisor == 0: 54 current_value //= divisor 55 divisor += 1 56 57 # If remaining value > 1, it's a prime factor 58 if current_value > 1: 59 prime_factors[number].append(current_value) 60 61 62class Solution: 63 def canTraverseAllPairs(self, nums: List[int]) -> bool: 64 """ 65 Check if all pairs of indices can be traversed. 66 Two indices i and j are connected if gcd(nums[i], nums[j]) > 1. 67 68 Strategy: Use Union-Find to connect indices through shared prime factors. 69 Create nodes for both array indices and prime factors. 70 """ 71 n = len(nums) 72 max_num = max(nums) 73 74 # Create Union-Find with space for: 75 # - n nodes for array indices (0 to n-1) 76 # - max_num+1 nodes for prime factors (offset by n) 77 union_find = UnionFind(n + max_num + 1) 78 79 # Connect each array index with its prime factors 80 for index, value in enumerate(nums): 81 for prime in prime_factors[value]: 82 # Connect array index with prime factor node 83 # Prime factor nodes are offset by n to avoid collision with indices 84 union_find.union(index, prime + n) 85 86 # Check if all array indices are in the same connected component 87 unique_roots = set(union_find.find(i) for i in range(n)) 88 return len(unique_roots) == 1 89
1/** 2 * Union-Find (Disjoint Set Union) data structure with path compression and union by size 3 */ 4class UnionFind { 5 private int[] parent; // parent[i] stores the parent of node i 6 private int[] size; // size[i] stores the size of the tree rooted at i 7 8 /** 9 * Initialize Union-Find structure with n elements (0 to n-1) 10 * @param n number of elements 11 */ 12 public UnionFind(int n) { 13 parent = new int[n]; 14 size = new int[n]; 15 for (int i = 0; i < n; i++) { 16 parent[i] = i; // Initially, each element is its own parent 17 size[i] = 1; // Initially, each tree has size 1 18 } 19 } 20 21 /** 22 * Find the root of the set containing element x with path compression 23 * @param x the element to find the root for 24 * @return the root of the set containing x 25 */ 26 public int find(int x) { 27 if (parent[x] != x) { 28 // Path compression: make every node point directly to the root 29 parent[x] = find(parent[x]); 30 } 31 return parent[x]; 32 } 33 34 /** 35 * Union two sets containing elements a and b using union by size 36 * @param a first element 37 * @param b second element 38 * @return true if union was performed, false if already in same set 39 */ 40 public boolean union(int a, int b) { 41 int rootA = find(a); 42 int rootB = find(b); 43 44 // Already in the same set 45 if (rootA == rootB) { 46 return false; 47 } 48 49 // Union by size: attach smaller tree under root of larger tree 50 if (size[rootA] > size[rootB]) { 51 parent[rootB] = rootA; 52 size[rootA] += size[rootB]; 53 } else { 54 parent[rootA] = rootB; 55 size[rootB] += size[rootA]; 56 } 57 return true; 58 } 59} 60 61class Solution { 62 // Maximum value for array elements 63 private static final int MAX_VALUE = 100010; 64 65 // Pre-computed prime factors for all numbers up to MAX_VALUE 66 // primeFactors[x] contains all unique prime factors of x 67 private static final List<Integer>[] primeFactors = new List[MAX_VALUE]; 68 69 // Static block to pre-compute all prime factors 70 static { 71 // Initialize lists for each number 72 Arrays.setAll(primeFactors, k -> new ArrayList<>()); 73 74 // Compute prime factors for each number from 1 to MAX_VALUE-1 75 for (int number = 1; number < MAX_VALUE; number++) { 76 int currentValue = number; 77 int divisor = 2; 78 79 // Trial division to find prime factors 80 while (divisor * divisor <= currentValue) { 81 if (currentValue % divisor == 0) { 82 // Found a prime factor 83 primeFactors[number].add(divisor); 84 85 // Remove all occurrences of this prime factor 86 while (currentValue % divisor == 0) { 87 currentValue /= divisor; 88 } 89 } 90 divisor++; 91 } 92 93 // If currentValue > 1, it's a prime factor itself 94 if (currentValue > 1) { 95 primeFactors[number].add(currentValue); 96 } 97 } 98 } 99 100 /** 101 * Check if all pairs in the array can be traversed 102 * Two numbers can be connected if they share a common factor > 1 103 * @param nums input array of integers 104 * @return true if all pairs can be traversed, false otherwise 105 */ 106 public boolean canTraverseAllPairs(int[] nums) { 107 // Find maximum value in the array 108 int maxValue = Arrays.stream(nums).max().getAsInt(); 109 int arrayLength = nums.length; 110 111 // Create Union-Find structure 112 // Nodes 0 to arrayLength-1 represent array indices 113 // Nodes arrayLength to arrayLength+maxValue represent prime factors 114 UnionFind unionFind = new UnionFind(arrayLength + maxValue + 1); 115 116 // Connect each array element with its prime factors 117 for (int i = 0; i < arrayLength; i++) { 118 for (int primeFactor : primeFactors[nums[i]]) { 119 // Connect array index i with prime factor node (offset by arrayLength) 120 unionFind.union(i, primeFactor + arrayLength); 121 } 122 } 123 124 // Check if all array elements are in the same connected component 125 Set<Integer> roots = new HashSet<>(); 126 for (int i = 0; i < arrayLength; i++) { 127 roots.add(unionFind.find(i)); 128 } 129 130 // All elements are connected if they have the same root 131 return roots.size() == 1; 132 } 133} 134
1// Maximum value for prime factorization preprocessing 2const int MAX_VALUE = 100010; 3 4// Store prime factors for each number (index represents the number) 5vector<int> primeFactors[100010]; 6 7// Initialize prime factors for all numbers up to MAX_VALUE using trial division 8int initialize = []() { 9 for (int num = 1; num < MAX_VALUE; ++num) { 10 int value = num; 11 int divisor = 2; 12 13 // Find all prime factors using trial division 14 while (divisor * divisor <= value) { 15 if (value % divisor == 0) { 16 // Found a prime factor 17 primeFactors[num].push_back(divisor); 18 19 // Remove all occurrences of this prime factor 20 while (value % divisor == 0) { 21 value /= divisor; 22 } 23 } 24 ++divisor; 25 } 26 27 // If remaining value > 1, it's a prime factor itself 28 if (value > 1) { 29 primeFactors[num].push_back(value); 30 } 31 } 32 return 0; 33}(); 34 35class UnionFind { 36public: 37 // Initialize Union-Find with n elements 38 UnionFind(int n) { 39 parent = vector<int>(n); 40 componentSize = vector<int>(n, 1); 41 // Initially, each element is its own parent 42 iota(parent.begin(), parent.end(), 0); 43 } 44 45 // Unite two components containing elements a and b 46 // Returns true if they were in different components, false otherwise 47 bool unite(int a, int b) { 48 int rootA = find(a); 49 int rootB = find(b); 50 51 // Already in the same component 52 if (rootA == rootB) { 53 return false; 54 } 55 56 // Union by size: attach smaller tree under root of larger tree 57 if (componentSize[rootA] > componentSize[rootB]) { 58 parent[rootB] = rootA; 59 componentSize[rootA] += componentSize[rootB]; 60 } else { 61 parent[rootA] = rootB; 62 componentSize[rootB] += componentSize[rootA]; 63 } 64 return true; 65 } 66 67 // Find root of component containing x with path compression 68 int find(int x) { 69 if (parent[x] != x) { 70 parent[x] = find(parent[x]); // Path compression 71 } 72 return parent[x]; 73 } 74 75private: 76 vector<int> parent; // Parent of each element 77 vector<int> componentSize; // Size of component rooted at each element 78}; 79 80class Solution { 81public: 82 // Check if all pairs of numbers in nums can be traversed 83 // Two numbers can be connected if gcd(nums[i], nums[j]) > 1 84 bool canTraverseAllPairs(vector<int>& nums) { 85 int maxValue = *max_element(nums.begin(), nums.end()); 86 int n = nums.size(); 87 88 // Create Union-Find structure 89 // Elements 0 to n-1: indices of nums array 90 // Elements n to n+maxValue: prime factors (offset by n) 91 UnionFind uf(maxValue + n + 1); 92 93 // Connect each number index with its prime factors 94 // This creates a bipartite graph between indices and prime factors 95 for (int i = 0; i < n; ++i) { 96 for (int primeFactor : primeFactors[nums[i]]) { 97 // Connect index i with prime factor (offset by n to avoid collision) 98 uf.unite(i, primeFactor + n); 99 } 100 } 101 102 // Check if all indices are in the same connected component 103 unordered_set<int> roots; 104 for (int i = 0; i < n; ++i) { 105 roots.insert(uf.find(i)); 106 } 107 108 // All indices should have the same root if they're all connected 109 return roots.size() == 1; 110 } 111}; 112
1// Maximum value for prime factorization preprocessing 2const MAX_VALUE = 100010; 3 4// Store prime factors for each number (index represents the number) 5const primeFactors: number[][] = Array.from({ length: MAX_VALUE }, () => []); 6 7// Initialize prime factors for all numbers up to MAX_VALUE using trial division 8(() => { 9 for (let num = 1; num < MAX_VALUE; num++) { 10 let value = num; 11 let divisor = 2; 12 13 // Find all prime factors using trial division 14 while (divisor * divisor <= value) { 15 if (value % divisor === 0) { 16 // Found a prime factor 17 primeFactors[num].push(divisor); 18 19 // Remove all occurrences of this prime factor 20 while (value % divisor === 0) { 21 value = Math.floor(value / divisor); 22 } 23 } 24 divisor++; 25 } 26 27 // If remaining value > 1, it's a prime factor itself 28 if (value > 1) { 29 primeFactors[num].push(value); 30 } 31 } 32})(); 33 34// Union-Find data structure arrays 35let parent: number[] = []; 36let componentSize: number[] = []; 37 38// Initialize Union-Find with n elements 39function initializeUnionFind(n: number): void { 40 parent = new Array(n); 41 componentSize = new Array(n).fill(1); 42 // Initially, each element is its own parent 43 for (let i = 0; i < n; i++) { 44 parent[i] = i; 45 } 46} 47 48// Find root of component containing x with path compression 49function find(x: number): number { 50 if (parent[x] !== x) { 51 parent[x] = find(parent[x]); // Path compression 52 } 53 return parent[x]; 54} 55 56// Unite two components containing elements a and b 57// Returns true if they were in different components, false otherwise 58function unite(a: number, b: number): boolean { 59 const rootA = find(a); 60 const rootB = find(b); 61 62 // Already in the same component 63 if (rootA === rootB) { 64 return false; 65 } 66 67 // Union by size: attach smaller tree under root of larger tree 68 if (componentSize[rootA] > componentSize[rootB]) { 69 parent[rootB] = rootA; 70 componentSize[rootA] += componentSize[rootB]; 71 } else { 72 parent[rootA] = rootB; 73 componentSize[rootB] += componentSize[rootA]; 74 } 75 return true; 76} 77 78// Check if all pairs of numbers in nums can be traversed 79// Two numbers can be connected if gcd(nums[i], nums[j]) > 1 80function canTraverseAllPairs(nums: number[]): boolean { 81 const maxValue = Math.max(...nums); 82 const n = nums.length; 83 84 // Create Union-Find structure 85 // Elements 0 to n-1: indices of nums array 86 // Elements n to n+maxValue: prime factors (offset by n) 87 initializeUnionFind(maxValue + n + 1); 88 89 // Connect each number index with its prime factors 90 // This creates a bipartite graph between indices and prime factors 91 for (let i = 0; i < n; i++) { 92 for (const primeFactor of primeFactors[nums[i]]) { 93 // Connect index i with prime factor (offset by n to avoid collision) 94 unite(i, primeFactor + n); 95 } 96 } 97 98 // Check if all indices are in the same connected component 99 const roots = new Set<number>(); 100 for (let i = 0; i < n; i++) { 101 roots.add(find(i)); 102 } 103 104 // All indices should have the same root if they're all connected 105 return roots.size === 1; 106} 107

Solution Approach

The implementation consists of three main components:

1. Union-Find Data Structure

The UnionFind class implements a disjoint set union with path compression and union by size optimization:

  • find(x): Finds the root of element x with path compression to flatten the tree structure
  • union(a, b): Merges two sets containing a and b, using size-based merging to keep the tree balanced
  • Each element starts as its own parent, and size tracks the size of each component

2. Prime Factorization Preprocessing

Before the main solution, the code pre-computes prime factors for all numbers up to mx = 100010:

for x in range(1, mx + 1):  v = x  i = 2  while i <= v // i: # Check divisors up to sqrt(v)  if v % i == 0:  p[x].append(i) # Add prime factor i  while v % i == 0:  v //= i # Remove all occurrences of i  i += 1  if v > 1:  p[x].append(v) # Add remaining prime factor

This creates a dictionary p where p[x] contains all prime factors of x.

3. Main Algorithm

The solution creates a Union-Find structure with n + m + 1 elements, where:

  • Indices 0 to n-1 represent the array indices
  • Indices n to n+m represent prime numbers (offset by n)

For each element nums[i]:

  1. Look up its prime factors from the preprocessed dictionary
  2. Union index i with each prime factor j (represented as j + n in the Union-Find)
  3. This creates connections: if two indices share a prime factor, they'll be in the same component

Finally, check if all array indices belong to the same connected component:

return len(set(uf.find(i) for i in range(n))) == 1

If there's only one unique root among all array indices, then all pairs are reachable from each other.

Time Complexity: O(n × log(max(nums)) + n × α(n)) where α is the inverse Ackermann function Space Complexity: O(n + max(nums)) for the Union-Find structure and prime factor storage

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example with nums = [6, 10, 15] to illustrate how the solution works.

Step 1: Prime Factorization (Preprocessing) First, we identify the prime factors for each number:

  • 6 = 2 × 3, so prime factors are [2, 3]
  • 10 = 2 × 5, so prime factors are [2, 5]
  • 15 = 3 × 5, so prime factors are [3, 5]

Step 2: Initialize Union-Find We create a Union-Find structure with space for:

  • 3 array indices (0, 1, 2)
  • Prime numbers we'll encounter (2, 3, 5)

Initially, each element is its own parent:

Array indices: [0] [1] [2] Prime factors: [2] [3] [5]

Step 3: Connect Indices to Prime Factors

For index 0 (value 6):

  • Union(0, 2): Connect index 0 with prime 2
  • Union(0, 3): Connect index 0 with prime 3
Components: [0-2-3] [1] [5]

For index 1 (value 10):

  • Union(1, 2): Connect index 1 with prime 2 (already connected to 0)
  • Union(1, 5): Connect index 1 with prime 5
Components: [0-2-3-1-5]

For index 2 (value 15):

  • Union(2, 3): Connect index 2 with prime 3 (already connected to 0 and 1)
  • Union(2, 5): Connect index 2 with prime 5 (already connected)
Final: [0-2-3-1-5-2] (all in one component)

Step 4: Check Connectivity Find the root of each array index:

  • find(0) = root
  • find(1) = root (same as index 0)
  • find(2) = root (same as index 0)

Since all three indices have the same root, they're all connected. This means:

  • Index 0 can reach index 1 (through prime 2)
  • Index 0 can reach index 2 (through prime 3)
  • Index 1 can reach index 2 (through prime 5)

The function returns true because all pairs of indices are reachable.

Counter-example: If nums = [2, 3, 5] (all prime numbers):

  • Index 0 connects only to prime 2
  • Index 1 connects only to prime 3
  • Index 2 connects only to prime 5
  • No indices share prime factors, so they remain in separate components
  • The function returns false

Time and Space Complexity

Time Complexity:

The algorithm consists of two main parts: preprocessing prime factors and the main solution.

  1. Preprocessing prime factors: For each number from 1 to mx = 100010, we find all prime factors using trial division. For each number x, the inner loop runs up to √x, making the time complexity O(mx * √mx) = O(100010 * √100010) ≈ O(10^5 * 316) ≈ O(3.16 × 10^7).

  2. Main solution:

    • Creating UnionFind: O(n + m) where n is the length of nums and m is the maximum value in nums
    • For each number in nums, we union it with all its prime factors. Each number has at most O(log m) prime factors. Each union operation with path compression has amortized complexity O(α(n + m)) where α is the inverse Ackermann function (practically constant)
    • The loop iterates through all n numbers, performing at most O(log m) unions each: O(n * log m * α(n + m))
    • Finding the root for all n elements: O(n * α(n + m))

Overall time complexity: O(mx * √mx + n * log m * α(n + m)) where the preprocessing dominates if done for all numbers up to mx. In practice, if we only precompute for numbers in the input, it would be O(n * √m + n * log m * α(n + m)).

Space Complexity:

  1. Preprocessing storage: The dictionary p stores prime factors for numbers up to mx. Each number has at most O(log mx) prime factors, so the space is O(mx * log mx) ≈ O(10^5 * log 10^5) ≈ O(10^5 * 17).

  2. UnionFind structure: Two arrays of size n + m + 1: O(n + m)

  3. Set for checking connectivity: O(n)

Overall space complexity: O(mx * log mx + n + m) where the preprocessing storage dominates. If we only store prime factors for numbers in the input, it would be O(n * log m + n + m).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Handling Single Element Arrays

A critical edge case that's easy to overlook is when the array contains only one element. By definition, if there's only one index, all pairs are trivially connected (there are no pairs to connect!). However, the algorithm might fail if the single element is 1.

Problem Example:

nums = [1] # Should return true

When nums[0] = 1, it has no prime factors (since 1 has no prime divisors). This means no union operations occur, and the single index remains isolated. The check len(unique_roots) == 1 would still pass, but conceptually, we should handle this explicitly.

Solution:

def canTraverseAllPairs(self, nums: List[int]) -> bool:  n = len(nums)   # Handle single element case explicitly  if n == 1:  return True   # If any element is 1 and n > 1, impossible to connect  if 1 in nums:  return False   # Rest of the implementation...

2. Elements with Value 1

The number 1 has no prime factors (gcd(1, x) = 1 for all x ≠ 1). If the array contains 1 and has more than one element, it's impossible to connect all pairs since index containing 1 cannot be reached from any other index.

Problem Example:

nums = [2, 1, 3] # Should return false

The index containing 1 will never be unioned with anything, creating an isolated component.

Solution:

def canTraverseAllPairs(self, nums: List[int]) -> bool:  n = len(nums)  if n == 1:  return True   # Check for 1 in arrays with multiple elements  if any(num == 1 for num in nums):  return False   # Continue with Union-Find approach...

3. Memory Optimization for Large Prime Numbers

The current implementation allocates n + max(nums) + 1 nodes in the Union-Find structure. If the array contains a very large prime number (e.g., 99991), this wastes significant memory since most prime slots won't be used.

Problem Example:

nums = [2, 4, 99991] # Allocates ~100000 nodes but uses very few

Solution: Use a mapping to assign consecutive IDs to unique primes:

def canTraverseAllPairs(self, nums: List[int]) -> bool:  n = len(nums)  if n == 1:  return True  if any(num == 1 for num in nums):  return False   # Map unique primes to consecutive IDs  prime_to_id = {}  prime_count = 0   for value in nums:  for prime in prime_factors[value]:  if prime not in prime_to_id:  prime_to_id[prime] = prime_count  prime_count += 1   # Create Union-Find with exact size needed  union_find = UnionFind(n + prime_count)   # Connect indices with their prime factors using mapped IDs  for index, value in enumerate(nums):  for prime in prime_factors[value]:  prime_id = prime_to_id[prime]  union_find.union(index, n + prime_id)   unique_roots = set(union_find.find(i) for i in range(n))  return len(unique_roots) == 1

4. Duplicate Values Optimization

If the array contains many duplicate values, the current approach redundantly processes the same prime factorizations multiple times.

Problem Example:

nums = [6, 6, 6, 6, 6] # Processes prime factors of 6 five times

Solution: Group indices by value first to avoid redundant unions:

def canTraverseAllPairs(self, nums: List[int]) -> bool:  n = len(nums)  if n == 1:  return True  if any(num == 1 for num in nums):  return False   # Group indices by value  value_to_indices = defaultdict(list)  for i, num in enumerate(nums):  value_to_indices[num].append(i)   # Create Union-Find  union_find = UnionFind(n + max(nums) + 1)   # Process each unique value once  for value, indices in value_to_indices.items():  # Connect all indices with same value  for i in range(1, len(indices)):  union_find.union(indices[0], indices[i])   # Connect first index with prime factors  for prime in prime_factors[value]:  union_find.union(indices[0], n + prime)   unique_roots = set(union_find.find(i) for i in range(n))  return len(unique_roots) == 1
Loading...
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which data structure is used to implement recursion?

Recommended Readings

DSU/Union Find Fundamentals

Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More