Find the Number of Good Pairs I - Video Solutions

Problem Overview: You are given two integer arrays nums1 and nums2, along with an integer k. A pair (i, j) is considered good if nums1[i] is divisible by nums2[j] * k. The task is to count how many such pairs exist across both arrays.

Approach 1: Brute Force Pair Check (Time: O(n * m), Space: O(1))

The most direct strategy is to check every possible pair. Iterate through each element in nums1 and for each element iterate through nums2. For every pair, compute nums2[j] * k and check whether nums1[i] % (nums2[j] * k) == 0. If the condition holds, increment the count. This approach uses simple nested iteration over the two arrays and requires no additional data structures. It works well when the arrays are small, but performance degrades as their sizes grow because every combination must be evaluated.

Approach 2: Hash Table + Divisor Enumeration (Time: O(n * sqrt(V) + m), Space: O(m))

A more efficient strategy reduces repeated checks using a hash table. First build a frequency map of values in nums2. Then iterate through nums1. Only elements divisible by k can form valid pairs, so compute x = nums1[i] / k. The condition becomes finding values in nums2 that divide x. Instead of checking every element in nums2, enumerate all divisors of x up to sqrt(x). If a divisor exists in the frequency map, add its count. Also check the paired divisor x / d when it differs from d. This preprocessing step avoids scanning the entire second array for each element and replaces it with constant-time hash lookups.

The key insight is rewriting the divisibility condition. If nums1[i] % (nums2[j] * k) == 0, then nums2[j] must divide nums1[i] / k. Turning the problem into divisor matching allows efficient lookups using a hash map rather than repeated multiplication checks. This technique appears frequently in problems combining array traversal with factor relationships.

Recommended for interviews: Start with the brute force explanation because it demonstrates clear understanding of the pair condition. Then move to the hash-table optimization that transforms the divisibility rule and uses divisor enumeration. Interviewers typically expect this transition from O(n * m) scanning to a structure-assisted lookup that significantly reduces redundant comparisons.