Tuple with Same Product: Hash Map Counting Pattern

LeetCode Tuple with Same Product (problem 1726) asks you to count all tuples (a, b, c, d) from an array nums such that a * b == c * d, where a, b, c, and d are distinct elements. At first glance, checking all groups of four elements sounds expensive. But a hash map turns this from an O(n^4) brute force into a clean O(n^2) solution.

Why this problem matters

Tuple with Same Product is a perfect example of the pair counting pattern. Instead of thinking about four elements at once, you reduce the problem to counting pairs that share the same product. This "reduce the dimension" trick appears across many problems: 4Sum, number of boomerangs, and any problem where you need to count combinations of items sharing a property. Once you see the trick here, you will recognize it everywhere.

The key insight

You do not need to enumerate all groups of four. Instead, think about it as pairs. For every pair of indices (i, j) where i is less than j, compute nums[i] * nums[j] and store the count of each product in a hash map.

If a product appears c times in the map, that means c different pairs share the same product. You can choose 2 of those c pairs in c * (c - 1) / 2 ways. And each choice of two pairs (a, b) and (c, d) gives you 8 valid tuples, because you can swap a with b, swap c with d, and swap the two pairs themselves. That is 2 * 2 * 2 = 8 arrangements.

So the answer is: for each product in the map with count c, add c * (c - 1) / 2 * 8 to the result.

The solution

def tuple_same_product(nums):
    from collections import Counter

    product_count = Counter()
    n = len(nums)

    for i in range(n):
        for j in range(i + 1, n):
            product_count[nums[i] * nums[j]] += 1

    result = 0
    for count in product_count.values():
        result += count * (count - 1) // 2 * 8

    return result

The solution has two phases. First, enumerate every pair and record the product frequency. Second, for each product that appears more than once, compute the number of tuples it contributes.

Visual walkthrough

Let's trace through nums = [2, 3, 4, 6]. We enumerate all pairs, compute their products, and build a frequency map. Then we count how many tuples each repeated product contributes.

The only product that appears more than once is 12 (from pairs 26 and 34). With count 2, we get 2 * 1 / 2 * 8 = 8 tuples. That matches the expected answer.

Complexity analysis

Time: O(n^2). We enumerate all pairs, which takes O(n^2). Then we iterate through the hash map, which has at most O(n^2) entries. Total: O(n^2).

Space: O(n^2). In the worst case, every pair produces a unique product, so the hash map stores O(n^2) entries.

This is a significant improvement over the brute force O(n^4) approach of checking all groups of four elements.

The building blocks

1. Pair enumeration

The first building block is iterating through all unique pairs in the array. This is the classic nested loop where the inner index starts one past the outer index.

for i in range(n):
    for j in range(i + 1, n):
        process(nums[i], nums[j])

This pattern guarantees each pair is visited exactly once and avoids counting a pair with itself. You will see it in Two Sum, number of pairs problems, and anywhere you need to consider all combinations of two elements.

2. Frequency counting with a hash map

The second building block is using a hash map (or Counter) to track how many times each value occurs. Here, the "value" is a product, but the technique is the same whether you are counting character frequencies, sum frequencies, or difference frequencies.

from collections import Counter

freq = Counter()
for item in items:
    freq[item] += 1

Once you have the frequency map, you use the combination formula c * (c - 1) / 2 to count how many ways you can pick 2 items from a group of c. This "choose 2 from a frequency" calculation is a building block in its own right.

Edge cases

• All elements are equal. If nums = [2, 2, 2, 2], every pair has the same product (4). With 6 pairs sharing product 4, the answer is 6 * 5 / 2 * 8 = 120.
• No shared products. If every pair produces a unique product, the answer is 0. This happens when the array has very few elements or when the values are all prime and distinct.
• Array length is less than 4. You cannot form a valid tuple with fewer than 4 elements, so the answer is 0. The algorithm handles this naturally since no product can appear more than once with so few pairs.
• Large products. The products can be large if array elements are large, but Python handles big integers natively. In other languages, be mindful of overflow.

From understanding to recall

The Tuple with Same Product solution is short, but it layers three ideas on top of each other: pair enumeration, frequency counting, and the combinatorial multiplier of 8. In an interview, you need all three pieces to click together quickly.

The pair enumeration loop is muscle memory if you have practiced Two Sum. The frequency map is the same Counter you use in dozens of problems. The 8x multiplier is the one piece specific to this problem, and it comes from counting the permutations of two ordered pairs. Drill these pieces separately, and the full solution assembles itself when you need it.

Related posts

• Two Sum - The foundational hash map complement lookup, the simplest "pair finding" problem
• Group Anagrams - Another hash map grouping pattern, where you group by a computed key
• 4Sum - A different approach to four-element combinations using sorting and two pointers

Tuple with Same Product is a clean example of how hash maps let you trade space for time. Instead of checking all possible quadruplets in O(n^4), you reduce the problem to counting pairs in O(n^2) and then do a bit of combinatorics. That pattern of "precompute something about pairs, then combine" is one of the most powerful tricks in your toolkit. Practice it until the pair enumeration and frequency counting flow without hesitation.