LeetCode Solutions Blog

Number of Ways Where Square of Number Is Equal to Product of Two Numbers

Number: 1699

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given two arrays of integers nums1 and nums2, count the total number of triplets that satisfy one of the two rules:

Type 1: For an index i in nums1 and indices j, k in nums2 (with j < k), the triplet is valid if nums1[i]² equals nums2[j] * nums2[k].
Type 2: For an index i in nums2 and indices j, k in nums1 (with j < k), the triplet is valid if nums2[i]² equals nums1[j] * nums1[k].

Return the total number of valid triplets.

Key Insights

Use frequency maps (hash tables) to count the occurrences of each number in the arrays.
For a given target value (which is a square of an element from one array), count the number of pairs in the other array that multiply to this target.
To count pairs from a frequency map, iterate over the sorted distinct keys using a two-pointer technique.
When the two factors are the same, use combination counting (n * (n-1) / 2); otherwise, multiply the frequencies.
Cache computed results for a given target value so that if the same square appears multiple times, the costly pair counting is done only once.

Space and Time Complexity

Time Complexity: O(n * m) where n is the length of one array and m is the number of unique elements in the other array (and vice versa)
Space Complexity: O(n) for the frequency maps and caching structures.

Solution

The solution involves:

Building frequency maps for both arrays.
For each unique number (and its frequency) in one array, computing its square.
Counting the number of unordered pairs in the other array whose product equals that square. The two-pointer technique is used on the sorted unique keys from the frequency map.
Caching the result for each computed target to avoid redundant computation.
Repeating the process for both types (using nums1’s square and pairs from nums2, and vice versa) and summing the results.

Code Solutions

def numTriplets(nums1, nums2):
    from collections import Counter
    # Helper function that counts number of unordered pairs in freq mapping whose product equals target.
    # Uses two pointers on the sorted unique keys. Cache is used to store previously computed targets.
    def count_pairs(freq, target, cache):
        if target in cache:
            return cache[target]
        count = 0
        factors = sorted(freq.keys())
        left, right = 0, len(factors) - 1
        while left <= right:
            product = factors[left] * factors[right]
            if product < target:
                left += 1
            elif product > target:
                right -= 1
            else:
                if factors[left] == factors[right]:
                    count += freq[factors[left]] * (freq[factors[left]] - 1) // 2
                else:
                    count += freq[factors[left]] * freq[factors[right]]
                left += 1
                right -= 1
        cache[target] = count
        return count

    freq1 = Counter(nums1)
    freq2 = Counter(nums2)
    
    type1 = 0
    type2 = 0
    cache2 = {}  # Cache for computing pairs in nums2
    cache1 = {}  # Cache for computing pairs in nums1
    
    # Count Type 1 triplets: for each number in nums1, check how many pairs in nums2 multiply to its square.
    for num, freq in freq1.items():
        target = num * num
        pairs = count_pairs(freq2, target, cache2)
        type1 += freq * pairs
    
    # Count Type 2 triplets: for each number in nums2, check how many pairs in nums1 multiply to its square.
    for num, freq in freq2.items():
        target = num * num
        pairs = count_pairs(freq1, target, cache1)
        type2 += freq * pairs

    return type1 + type2

# Example test cases
print(numTriplets([7,4], [5,2,8,9]))     # Expected output: 1
print(numTriplets([1,1], [1,1,1]))       # Expected output: 9
print(numTriplets([7,7,8,3], [1,2,9,7])) # Expected output: 2