Is Find the Number of Good Pairs II easy or hard?

The problem is rated Medium because the brute force solution is obvious but too slow. The challenge lies in recognizing the divisibility relationship and converting it into a frequency-counting strategy using hash maps.

Find the Number of Good Pairs II Python/Java solution

Most implementations use a dictionary or HashMap to count nums1 frequencies, then iterate through nums2 and check multiples of nums2[j] * k. The logic is concise in Python with dictionaries and equally efficient in Java using HashMap for constant-time lookups.

How to solve Find the Number of Good Pairs II in O(n)?

Near-linear performance is achieved by counting frequencies of nums1 values in a hash map and iterating over multiples of nums2[j] * k. Each multiple lookup is O(1), so the algorithm avoids nested pair comparisons and only processes values that could actually divide elements in nums1.

What is the best approach for Find the Number of Good Pairs II?

The most efficient approach uses a hash map to store frequencies of values in nums1 and then iterates through multiples of nums2[j] * k. Instead of checking every pair, the algorithm counts how many multiples exist in nums1 using constant-time hash lookups. This reduces the work significantly compared to the brute force method.

Is Find the Number of Good Pairs II asked at Google/Amazon/Meta?

Problems involving divisibility counting, hash maps, and frequency tables appear frequently in interviews at companies like Amazon, Google, and Meta. This problem tests whether you can convert a naive pair-checking solution into a more scalable counting approach.

What data structure is used in Find the Number of Good Pairs II?

The optimized solution relies on a hash table (hash map) to store the frequency of elements from nums1. Hash lookups allow the algorithm to quickly determine how many numbers match each required multiple during iteration.

What is the time complexity of Find the Number of Good Pairs II?

The brute force solution runs in O(n * m) time because every pair between nums1 and nums2 is checked. The optimized hash map approach runs roughly in O(n + v log v) time depending on the number of multiples explored, with O(n) additional space for frequency storage.

Description Hints 3 Solution Video 12:51

3164. Find the Number of Good Pairs II

Medium26.6% acceptance2 companies

You are given 2 integer arrays nums1 and nums2 of lengths n and m respectively. You are also given a positive integer k.

A pair (i, j) is called good if nums1[i] is divisible by nums2[j] * k (0 <= i <= n - 1, 0 <= j <= m - 1).

Return the total number of good pairs.

Example 1:

Input: nums1 = [1,3,4], nums2 = [1,3,4], k = 1

Output: 5

Explanation:

The 5 good pairs are (0, 0), (1, 0), (1, 1), (2, 0), and (2, 2).

Example 2:

Input: nums1 = [1,2,4,12], nums2 = [2,4], k = 3

Output: 2

Explanation:

The 2 good pairs are (3, 0) and (3, 1).

Constraints:

1 <= n, m <= 10⁵
1 <= nums1[i], nums2[j] <= 10⁶
1 <= k <= 10³

Asked at 2 companies

Airbus Amazon

Topics

Array Hash Table

Hints open one at a time

Hint 1

Let f[v] be the number of occurrences of v/k in nums2.

Hint 2

For each value v in nums1, enumerating all its factors d (in sqrt(v) time) and sum up all the f[d] to get the final answer.

Hint 3

It is also possible to improve the complexity from len(nums1) * sqrt(v) to len(nums1) * log(v) - How?

12:51

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution