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.
This approach involves iterating over each element in nums1 and nums2 and checking if the condition given for a 'good' pair is satisfied. This solution involves a nested loop where for each element in nums1, we go through all elements in nums2.
The C solution uses two nested loops to iterate over nums1 and nums2. For each pair (nums1[i], nums2[j]), it checks if nums1[i] is divisible by nums2[j] * k. The number of good pairs is returned as the result.
Time Complexity: O(n * m), where n is the length of nums1 and m is the length of nums2.
Space Complexity: O(1) as the additional space used does not depend on the input size.
This approach aims to optimize the search for good pairs by utilizing a hashmap to store results of previously seen computations. By storing values needed for divisibility checks, we aim to reduce redundant calculations and speed up the process.
The Python solution uses a defaultdict to store counts of potential divisors derived from nums2 by multiplying each by k. It then iterates over nums1, checking for each element the number of divisors it is divisible by and counts these.
Python
JavaScript
Time Complexity: O(n + m * d), where d is the number of unique products that can be obtained from multiplying elements in nums2 by k.
Space Complexity: O(d).
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.
Next, we enumerate each number x in array nums2. For each number x, we enumerate its multiples y, where the range of y is [x, mx], where mx is the maximum key value in cnt1. Then we count the sum of cnt1[y], denoted as s. Finally, we add s times v to the answer, where v is cnt2[x].
The time complexity is O(n + m + (M / k) times log m), and the space complexity is O(n + m). Where n and m are the lengths of arrays nums1 and nums2 respectively, and M is the maximum value in array nums1.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n * m), where n is the length of |
| HashMap Optimization | Time Complexity: O(n + m * d), where d is the number of unique products that can be obtained from multiplying elements in |
| Hash Table + Enumerate Multiples | — |
| 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 |
3164. Find the Number of Good Pairs II | Math | Factors | 3162. Find the Number of Good Pairs I • Aryan Mittal • 5,970 views views
Watch 7 more video solutions →Practice Find the Number of Good Pairs II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor