Watch 8 video solutions for Find the Number of Good Pairs II, a medium level problem involving Array, Hash Table. This walkthrough by Aryan Mittal has 5,970 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1051 <= nums1[i], nums2[j] <= 1061 <= k <= 103Problem Overview: You are given two integer arrays nums1 and nums2 and an integer k. A pair (i, j) is considered good if nums1[i] is divisible by nums2[j] * k. The goal is to count how many such pairs exist across both arrays.
Approach 1: Brute Force (O(n * m) time, O(1) space)
The straightforward solution checks every possible pair. Iterate through each element in nums1, then iterate through each element in nums2. For every pair, compute nums2[j] * k and verify whether nums1[i] % (nums2[j] * k) == 0. If the condition holds, increment the result counter. This approach directly follows the definition of a good pair and is easy to implement, but the nested iteration leads to O(n * m) time complexity. It becomes slow when both arrays are large.
Approach 2: HashMap Optimization with Multiples (O(n + v log v) time, O(n) space)
The key observation: instead of testing every pair, focus on divisibility. If nums1[i] is divisible by nums2[j] * k, then nums1[i] must be a multiple of that value. Start by building a frequency map of values in nums1 using a hash table. Then iterate through nums2. For each value, compute target = nums2[j] * k.
Next, enumerate multiples of target up to the maximum value present in nums1. For every multiple, check whether it exists in the frequency map. If it does, add its frequency to the answer. This replaces expensive pairwise checks with constant-time hash lookups. The algorithm relies on efficient counting and arithmetic properties of multiples rather than brute comparisons.
This technique is common in problems involving divisibility and frequency counting in arrays. Using a hash map avoids scanning nums1 repeatedly and significantly reduces the number of operations in practice.
Recommended for interviews: The HashMap + multiples approach. Interviewers expect you to recognize the divisibility pattern and replace pairwise checks with frequency counting. Starting with the brute force shows you understand the problem constraints, but moving to the optimized hash-based solution demonstrates stronger problem-solving and familiarity with hash table techniques.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Check | O(n * m) | O(1) | Small arrays or when validating the basic logic first |
| HashMap + Multiples Enumeration | O(n + v log v) | O(n) | General case with large inputs where divisibility relationships can be exploited |