#3164

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find the Number of Good Pairs II

Calculate total good pairs by scanning two arrays and using hash lookup to match divisible elements efficiently with k.

Problem Statement

You are given two integer arrays nums1 of length n and nums2 of length m, along with a positive integer k. A pair (i, j) is considered good if nums1[i] is divisible by nums2[j] multiplied by k.

Return the total number of good pairs across all possible indices. Arrays may be large, so an efficient solution using hash lookup and array scanning is required to avoid exceeding time limits.

Examples

Example 1

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

Output: 5

Example 2

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

Output: 2

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

Constraints

1 <= n, m <= 105
1 <= nums1[i], nums2[j] <= 106
1 <= k <= 103

Solution Approach

Use a Hash Map to Count Candidates

Preprocess nums2 by counting the occurrences of each value divided by k in a hash map. This allows O(1) lookup for potential divisors when scanning nums1.

Iterate nums1 and Query the Map

For each element in nums1, check if it is divisible by k and then query the hash map for matches. Sum the counts from the map to track the total good pairs efficiently.

Handle Large Numbers Safely

Since nums1[i] and nums2[j] can be up to 10^6, avoid floating point division and use integer division carefully. This prevents overflow or miscounting when multiplying by k.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n + m) if using a hash map for counts and scanning each array once. Space complexity is O(m) for storing frequency counts of nums2 divided by k.

What Interviewers Usually Probe

Expect candidate to identify divisible pairs using a combination of iteration and hash lookup.
Watch if candidate considers integer division carefully to avoid miscounting.
Check whether the solution handles arrays of size up to 10^5 efficiently without nested loops.

Common Pitfalls or Variants

Common pitfalls

Attempting nested loops over nums1 and nums2 directly can cause timeouts on large inputs.
Using floating point division instead of integer division may result in wrong pair counts.
Failing to multiply nums2 elements by k before checking divisibility leads to incorrect results.

Follow-up variants

Count good pairs where nums1[i] % (nums2[j] + k) == 0 instead of multiplication by k.
Find maximum number of good pairs instead of total count.
Extend to 3 arrays where a triple (i, j, l) is good if nums1[i] % (nums2[j] * nums3[l] * k) == 0.

FAQ

What is the main pattern in Find the Number of Good Pairs II?

The key pattern is array scanning combined with hash lookup to efficiently count divisible pairs multiplied by k.

Can I use nested loops for this problem?

Nested loops are possible but inefficient; using a hash map avoids timeouts for large arrays.

How do I handle large numbers in nums1 and nums2?

Use integer division carefully and avoid floating point operations when checking divisibility to prevent miscounts.

Is it necessary to preprocess nums2?

Yes, counting occurrences of nums2 elements divided by k in a hash map is essential for efficient lookup.

What is a common failure mode for this problem?

Miscounting arises if you forget to multiply nums2 by k or use floating division, which leads to incorrect total good pairs.

terminal

Solution

Solution 1: Hash Table + Enumerate Multiples

We use a hash table `cnt1` to record the occurrence times of each number divided by $k$ in array `nums1`, and a hash table `cnt2` to record the occurrence times of each number in array `nums2`.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
        cnt1 = Counter(x // k for x in nums1 if x % k == 0)
        if not cnt1:
            return 0
        cnt2 = Counter(nums2)
        ans = 0
        mx = max(cnt1)
        for x, v in cnt2.items():
            s = sum(cnt1[y] for y in range(x, mx + 1, x))
            ans += s * v
        return ans

Continue Practicing

#3162 find the number of good pairs i #3160 find the number of distinct colors among the balls #3159 find occurrences of an element in an array