How do you solve Find the Number of Good Pairs II on LeetCode?

Find the Number of Good Pairs II (LeetCode #3164) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n * sqrt(v)) time complexity and O(m) space complexity. Key insight: Understanding divisibility and how to find factors efficiently can greatly reduce the number of operations needed.

What is the brute force solution for Find the Number of Good Pairs II?

The brute force approach for Find the Number of Good Pairs II is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks every possible pair of elements from nums1 and nums2 to see if the condition of being a good pair is satisfied. This is straightforward but inefficient for larger arrays. The optimal Optimal Solution approach improves this to O(n * sqrt(v)).

What algorithm or data structure is used to solve Find the Number of Good Pairs II?

Find the Number of Good Pairs II uses the following concepts: Array, Hash Table. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Find the Number of Good Pairs II?

Always start with a brute force solution to understand the problem before optimizing. Think about how you can reduce the number of checks needed, such as using a HashMap for counts. Be clear about your thought process when explaining your solution to the interviewer.

What are common mistakes when solving Find the Number of Good Pairs II?

Failing to account for the multiplication by k when checking divisibility. Not recognizing that checking divisors can be optimized by limiting to sqrt(num).

#3164

Find the Number of Good Pairs II

Medium

ArrayHash TableHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n * sqrt(v))
Space	O(1)	O(m)

💡

Intuition

Time O(n * sqrt(v))Space O(m)

Instead of checking every pair, we can use a HashMap to count occurrences of the required divisors derived from nums2. This allows us to efficiently find how many good pairs can be formed for each element in nums1.

⚙️

Algorithm

4 steps

1Step 1: Create a HashMap to count occurrences of each value in nums2 divided by k.
2Step 2: For each element in nums1, find its divisors up to the square root of the element.
3Step 3: For each divisor, check if it exists in the HashMap and add its count to the total good pairs.
4Step 4: Return the total count of good pairs.

solution.py14 lines

1def countGoodPairs(nums1, nums2, k):
2    from collections import defaultdict
3    count_map = defaultdict(int)
4    for num in nums2:
5        count_map[num] += 1
6    count = 0
7    for num1 in nums1:
8        for d in range(1, int(num1**0.5) + 1):
9            if num1 % d == 0:
10                if d in count_map:
11                    count += count_map[d]
12                if d != num1 // d and (num1 // d) in count_map:
13                    count += count_map[num1 // d]
14    return count

ℹ

Complexity note: The time complexity is O(n * sqrt(v)) where n is the length of nums1 and v is the maximum value in nums1. We loop through nums1 and find divisors, which takes sqrt(v) time. The space complexity is O(m) for storing counts of nums2 in a HashMap.

1Understanding divisibility and how to find factors efficiently can greatly reduce the number of operations needed.
2Using a HashMap to store counts of elements allows for quick lookups, improving performance.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.