Find the Number of Good Pairs II solution and explanation
Airbus
5 more videos on this problem
3164. Find the Number of Good Pairs II | Math | Factors | 3162. Find the Number of Good Pairs IAryan Mittal · 12:51 · 6K views
3164. Find the Number of Good Pairs II | 2 Approaches | Weekly Leetcode 399codingMohan · 34:45 · 1K views
3164. Find the Number of Good Pairs II (Leetcode Medium)Programming Live with Larry · 16:21 · 482 views
3164. Find the Number of Good Pairs IITech Courses · 15:46 · 395 views
3164. Find the Number of Good Pairs IIThe Local Coder! · 14:08 · 133 views
DECODEDSA#LEVELUP#CONTESTSOL#leetcode#challengeL.C.3164. Find the Number of Good Pairs IIDecode · 5:48 · 33 views
The problem
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 <= 103
Approach overview
Problem 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 1: Brute Force Approach
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.
def countGoodPairs(nums1, nums2, k):
count = 0
for x in nums1:
for y in nums2:
if x % (y * k) == 0:
count += 1
return count
nums1 = [1, 3, 4]
nums2 = [1, 3, 4]
k = 1
print(countGoodPairs(nums1, nums2, k)) # Output: 5import java.util.*;
public class Main {
public static int countGoodPairs(int[] nums1, int[] nums2, int k) {
int count = 0;
for (int i = 0; i < nums1.length; i++) {
for (int j = 0; j < nums2.length; j++) {
if (nums1[i] % (nums2[j] * k) == 0) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
int[] nums1 = {1, 3, 4};
int[] nums2 = {1, 3, 4};
int k = 1;
System.out.println(countGoodPairs(nums1, nums2, k)); // Output: 5
}
}#include <iostream>
#include <vector>
using namespace std;
int countGoodPairs(vector<int>& nums1, vector<int>& nums2, int k) {
int count = 0;
for (int i = 0; i < nums1.size(); ++i) {
for (int j = 0; j < nums2.size(); ++j) {
if (nums1[i] % (nums2[j] * k) == 0) {
count++;
}
}
}
return count;
}
int main() {
vector<int> nums1 = {1, 3, 4};
vector<int> nums2 = {1, 3, 4};
int k = 1;
cout << countGoodPairs(nums1, nums2, k) << endl; // Output: 5
return 0;
}function countGoodPairs(nums1, nums2, k) {
let count = 0;
for (let x of nums1) {
for (let y of nums2) {
if (x % (y * k) === 0) {
count++;
}
}
}
return count;
}
const nums1 = [1, 3, 4];
const nums2 = [1, 3, 4];
const k = 1;
console.log(countGoodPairs(nums1, nums2, k)); // Output: 5#include <stdio.h>
int countGoodPairs(int* nums1, int nums1Size, int* nums2, int nums2Size, int k) {
int count = 0;
for (int i = 0; i < nums1Size; i++) {
for (int j = 0; j < nums2Size; j++) {
if (nums1[i] % (nums2[j] * k) == 0) {
count++;
}
}
}
return count;
}
int main() {
int nums1[] = {1, 3, 4};
int nums2[] = {1, 3, 4};
int k = 1;
int result = countGoodPairs(nums1, 3, nums2, 3, k);
printf("%d\n", result); // Output: 5
return 0;
}using System;
class Solution {
public static int CountGoodPairs(int[] nums1, int[] nums2, int k) {
int count = 0;
for (int i = 0; i < nums1.Length; i++) {
for (int j = 0; j < nums2.Length; j++) {
if (nums1[i] % (nums2[j] * k) == 0) {
count++;
}
}
}
return count;
}
static void Main(string[] args) {
int[] nums1 = {1, 3, 4};
int[] nums2 = {1, 3, 4};
int k = 1;
Console.WriteLine(CountGoodPairs(nums1, nums2, k)); // Output: 5
}
}In the Python solution, nested loops are used to iterate through the combinations of elements from both input arrays. The function checks if the condition for good pairs is met, and counts such occurrences.
Time Complexity: O(n * m)
Space Complexity: O(1)
Approach 2: HashMap Optimization
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.
def countGoodPairs(nums1, nums2, k):
from collections import defaultdict
count = 0
divisor_count = defaultdict(int)
# Create a map of all possible divisors that are multiples of k from nums2
for y in nums2:
divisor_count[y * k] += 1
# For each number in nums1, check how many can divide it
for x in nums1:
for divisor in divisor_count:
if x % divisor == 0:
count += divisor_count[divisor]
return count
nums1 = [1, 3, 4]
nums2 = [1, 3, 4]
k = 1
print(countGoodPairs(nums1, nums2, k)) # Output: 5function countGoodPairs(nums1, nums2, k) {
const divisorCountMap = new Map();
let count = 0;
// Fill the map with divisors derived from nums2
for (let num of nums2) {
const divisor = num * k;
divisorCountMap.set(divisor, (divisorCountMap.get(divisor) || 0) + 1);
}
// Check each number in nums1
for (let num of nums1) {
// Check how many divisors can divide num
for (let divisor of divisorCountMap.keys()) {
if (num % divisor === 0) {
count += divisorCountMap.get(divisor);
}
}
}
return count;
}
const nums1 = [1, 3, 4];
const nums2 = [1, 3, 4];
const k = 1;
console.log(countGoodPairs(nums1, nums2, k)); // Output: 5The 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.
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).
Approach 3: 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.
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.
function numberOfPairs(nums1: number[], nums2: number[], k: number): number {
const cnt1: Map<number, number> = new Map();
for (const x of nums1) {
if (x % k === 0) {
cnt1.set((x / k) | 0, (cnt1.get((x / k) | 0) || 0) + 1);
}
}
if (cnt1.size === 0) {
return 0;
}
const cnt2: Map<number, number> = new Map();
for (const x of nums2) {
cnt2.set(x, (cnt2.get(x) || 0) + 1);
}
const mx = Math.max(...cnt1.keys());
let ans = 0;
for (const [x, v] of cnt2) {
let s = 0;
for (let y = x; y <= mx; y += x) {
s += cnt1.get(y) || 0;
}
ans += s * v;
}
return ans;
}func numberOfPairs(nums1 []int, nums2 []int, k int) (ans int64) {
cnt1 := map[int]int{}
for _, x := range nums1 {
if x%k == 0 {
cnt1[x/k]++
}
}
if len(cnt1) == 0 {
return 0
}
cnt2 := map[int]int{}
for _, x := range nums2 {
cnt2[x]++
}
mx := 0
for x := range cnt1 {
mx = max(mx, x)
}
for x, v := range cnt2 {
s := 0
for y := x; y <= mx; y += x {
s += cnt1[y]
}
ans += int64(s) * int64(v)
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n * m) |
| 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 | – |
Complexity analysis
| 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 |
Frequently asked questions
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.