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

LeetCode Number of Ways Where Square of Number Is Equal to Product of Two Numbers (Problem 1577) asks you to count triplets across two arrays where the square of one element equals the product of two elements from the other array.

The problem

Given two arrays of integers nums1 and nums2, return the number of triplets formed from two types:

• Type 1: Triplet (i, j, k) where nums1[i]^2 == nums2[j] * nums2[k] and 0 <= i, 0 <= j < k < nums2.length.
• Type 2: Triplet (i, j, k) where nums2[i]^2 == nums1[j] * nums1[k] and 0 <= i, 0 <= j < k < nums1.length.

Example: nums1 = [7, 4], nums2 = [5, 2, 8, 9]. For Type 1, 4^2 = 16 = 2 * 8, so there is 1 triplet. No Type 2 triplets exist. The answer is 1.

The brute force approach

The most direct approach checks every possible triplet combination. For Type 1, iterate over every i in nums1, then every pair (j, k) in nums2 where j < k. Check if the square equals the product.

def numTriplets(nums1, nums2):
    count = 0
    for i in range(len(nums1)):
        for j in range(len(nums2)):
            for k in range(j + 1, len(nums2)):
                if nums1[i] * nums1[i] == nums2[j] * nums2[k]:
                    count += 1
    for i in range(len(nums2)):
        for j in range(len(nums1)):
            for k in range(j + 1, len(nums1)):
                if nums2[i] * nums2[i] == nums1[j] * nums1[k]:
                    count += 1
    return count

This runs in O(n * m^2 + m * n^2) time, which is too slow for large inputs. The triple nested loop is doing redundant work. We can precompute the product pairs.

The key insight

Instead of checking every pair on the fly, precompute a hash map of all product frequencies for one array. Then for each element in the other array, look up its square in the map. The count at that key tells you how many valid pairs exist.

For Type 1, build a map of all nums2[j] * nums2[k] products (where j < k) and their frequencies. Then for each nums1[i], check map[nums1[i]^2]. Do the same with roles reversed for Type 2.

Step-by-step walkthrough

Let's trace through nums1 = [7, 4] and nums2 = [5, 2, 8, 9].

The final answer is 1. One Type 1 triplet (from 4^2 = 2 * 8) and zero Type 2 triplets.

The code

from collections import Counter

def numTriplets(nums1, nums2):
    def count_triplets(squares, products):
        prod_map = Counter()
        n = len(products)
        for j in range(n):
            for k in range(j + 1, n):
                prod_map[products[j] * products[k]] += 1
        total = 0
        for val in squares:
            total += prod_map[val * val]
        return total

    return count_triplets(nums1, nums2) + count_triplets(nums2, nums1)

Here is what each piece does:

1. count_triplets(squares, products) handles one direction. It takes the array whose elements get squared and the array whose pairs form products.
2. Build prod_map by iterating over all pairs (j, k) where j < k in the products array. Each product gets its frequency counted.
3. For each value in squares, compute val * val and look up how many pairs produce that product. Add that count to the total.
4. Call the helper twice with swapped arguments to cover both Type 1 and Type 2 triplets.

Complexity analysis

The hash map approach builds product maps in O(n^2) and O(m^2), then does linear lookups. The total is O(n^2 + m^2), which is much better than the cubic brute force for large inputs.

The building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Product pair frequency counting

The pattern of precomputing all pairwise products in an array and storing their frequencies in a hash map:

prod_map = Counter()
for j in range(n):
    for k in range(j + 1, n):
        prod_map[arr[j] * arr[k]] += 1

This same approach works in any problem where you need to quickly look up how many pairs produce a given value. Two Sum uses addition instead of multiplication, but the structure is identical: precompute pair results and store them for O(1) lookup.

2. Symmetric role reversal

The pattern of solving a problem in one direction, then swapping roles and solving it again:

result = solve(nums1, nums2) + solve(nums2, nums1)

This appears in problems like 4Sum II, where you split the four arrays into two groups and count complementary sums. Recognizing that both directions use the same logic lets you write one helper function and call it twice.

Edge cases

Before submitting, make sure your solution handles these:

• All identical elements: nums1 = [2, 2, 2], nums2 = [2, 2, 2]. Every element squares to 4, and every pair product is 4. The count grows quadratically with duplicates.
• No valid triplets: nums1 = [1], nums2 = [1]. Only one element in each array means no valid pair j < k can be formed from either array. The answer is 0.
• Large values: Elements can be up to 10^5, so squares can reach 10^10. Use 64-bit integers if your language requires it. Python handles big integers natively.
• Single element arrays: If one array has only one element, no pairs can form from it. Triplets can only come from the direction where the single-element array provides the square.
• Zeros in the arrays: If nums1[i] = 0, then 0^2 = 0, so you need pairs in nums2 whose product is 0. Any pair containing a zero element in nums2 qualifies.

From understanding to recall

You have seen the hash map approach and it makes sense. Precompute product frequencies, then look up each square. Two calls to the same helper cover both triplet types. Clean and efficient.

But in an interview, the pressure makes it easy to forget the symmetric structure, mix up which array gets squared versus paired, or fumble the pair enumeration. These are not understanding problems. They are recall problems.

Spaced repetition fixes this. You practice writing the product frequency map and the symmetric helper call from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "count triplets matching a target across two arrays" and the structure flows out: build map, look up squares, swap and repeat.

The product pair counting pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Two Sum - The classic complement lookup pattern that this problem extends from addition to multiplication
• 3Sum - Another problem that counts triplets matching a target, using sorting and two pointers instead of hash maps
• Subarray Sum Equals K - Prefix sums paired with hash map frequency counting, the same "precompute and look up" strategy

CodeBricks breaks the number of ways where square equals product LeetCode problem into its product pair counting and symmetric role reversal building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a pair-counting question shows up in your interview, you do not think about it. You just write it.