Skip to main content
Talentd

Find the Number of Good Pairs II - Solution & Explanation

MediumArrayHash Table15 min readAsked at: Amazon, Airbus
Practice this problem

Problem Statement

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 <= 105
  • 1 <= nums1[i], nums2[j] <= 106
  • 1 <= 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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

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).

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

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.

HashMap Optimization

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).

Hash Table + Enumerate Multiples—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair CheckO(n * m)O(1)Small arrays or when validating the basic logic first
HashMap + Multiples EnumerationO(n + v log v)O(n)General case with large inputs where divisibility relationships can be exploited

Video Solution

3164. Find the Number of Good Pairs II | Math | Factors | 3162. Find the Number of Good Pairs I • Aryan Mittal • 6,059 views views

Watch 5 more video solutions →

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.

Ready to solve this problem?

Practice Find the Number of Good Pairs II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Array Pairs Divisible by K