Scale Engineer

Find the Number of Good Pairs II

Med
#2811Time: O(m + n * sqrt(max_val)), where `max_val` is the maximum value in `nums1`. Building the map takes O(m). Then, for each of the `n` numbers in `nums1`, we find its divisors in O(sqrt(num)) time. With `n=10^5` and `max_val=10^6`, this is roughly 10<sup>5</sup> * 1000 = 10<sup>8</sup> operations, which is on the edge of timing out.Space: O(U2), where `U2` is the number of unique elements in `nums2`. In the worst case, all elements are unique, leading to O(m) space complexity for the hash map.1 company
Data structures
ArrayHash Table
Companies
Airbus SE

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

To improve upon the brute-force method, we can avoid re-scanning nums2 for every element of nums1. We can pre-process nums2 by storing its elements and their frequencies in a hash map. Then, for each element num1 in nums1, we find all its divisors. For each divisor d, we check if it could be formed by some num2 * k. This is true if d is a multiple of k. If so, we calculate the required num2 value (d/k) and add its frequency from the map to our total count.

Algorithm

  • Create a frequency map, freq2, for all numbers in nums2. A HashMap is a good choice for this.
  • Initialize a counter goodPairsCount to 0.
  • Iterate through each number num1 in nums1.
  • For each num1, find all of its divisors. This can be done by iterating from 1 up to sqrt(num1).
  • If i divides num1, then both i and num1 / i are divisors.
  • For each divisor d found:
    • Check if d is divisible by k.
    • If d % k == 0, calculate val = d / k.
    • Look up val in freq2. If it exists, add its frequency freq2.get(val) to goodPairsCount.
  • Be careful to handle perfect squares (when i * i == num1) to avoid double-counting.
  • Return goodPairsCount.

Walkthrough

The core idea is to change the check from num1 % (num2 * k) == 0 to finding divisors of num1. If d is a divisor of num1, we need to see if d can be represented as num2 * k for some num2 that exists in the nums2 array. This is equivalent to checking if d is divisible by k and if d/k is a number present in nums2.

import java.util.HashMap;import java.util.Map; class Solution {    public long numberOfGoodPairs(int[] nums1, int[] nums2, int k) {        Map<Integer, Integer> freq2 = new HashMap<>();        for (int num : nums2) {            freq2.put(num, freq2.getOrDefault(num, 0) + 1);        }         long goodPairsCount = 0;        for (int num1 : nums1) {            for (int d = 1; d * d <= num1; d++) {                if (num1 % d == 0) {                    // d is a divisor                    if (d % k == 0) {                        int val = d / k;                        goodPairsCount += freq2.getOrDefault(val, 0);                    }                                        // num1 / d is another divisor                    int d2 = num1 / d;                    if (d * d != num1) { // Avoid double counting for perfect squares                        if (d2 % k == 0) {                            int val = d2 / k;                            goodPairsCount += freq2.getOrDefault(val, 0);                        }                    }                }            }        }        return goodPairsCount;    }}

Complexity

Time

O(m + n * sqrt(max_val)), where `max_val` is the maximum value in `nums1`. Building the map takes O(m). Then, for each of the `n` numbers in `nums1`, we find its divisors in O(sqrt(num)) time. With `n=10^5` and `max_val=10^6`, this is roughly 10<sup>5</sup> * 1000 = 10<sup>8</sup> operations, which is on the edge of timing out.

Space

O(U2), where `U2` is the number of unique elements in `nums2`. In the worst case, all elements are unique, leading to O(m) space complexity for the hash map.

Trade-offs

Pros

  • Much faster than the naive brute-force approach.

  • Reduces redundant work by pre-calculating frequencies of numbers in nums2.

Cons

  • The time complexity is still high and may result in a 'Time Limit Exceeded' error for the largest constraints.

  • The performance is dependent on the magnitude of the numbers in nums1, not just the length of the array.

Solutions

class Solution {public  long numberOfPairs(int[] nums1, int[] nums2, int k) {    Map<Integer, Integer> cnt1 = new HashMap<>();    for (int x : nums1) {      if (x % k == 0) {        cnt1.merge(x / k, 1, Integer : : sum);      }    }    if (cnt1.isEmpty()) {      return 0;    }    Map<Integer, Integer> cnt2 = new HashMap<>();    for (int x : nums2) {      cnt2.merge(x, 1, Integer : : sum);    }    long ans = 0;    int mx = Collections.max(cnt1.keySet());    for (var e : cnt2.entrySet()) {      int x = e.getKey(), v = e.getValue();      int s = 0;      for (int y = x; y <= mx; y += x) {        s += cnt1.getOrDefault(y, 0);      }      ans += 1L * s * v;    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem