Tuple With Same Product — Frequency Maps Plus Combinatorics

Problem Statement#

Given an array nums of distinct positive integers, return the number of tuples (a, b, c, d) such that a * b == c * d, where all four are elements of nums and a, b, c, d are pairwise distinct.

Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 10^4
• All elements are pairwise distinct.

Input:  nums = [2,3,4,6]
Output: 8

Input:  nums = [1,2,4,5,10]
Output: 16

Why This Problem Matters#

LeetCode 1726 is a hash table FAANG question Google, Amazon, and Meta favor because it tests two skills at once: building a frequency map and reasoning about combinatorial multiplicity. Many candidates write a brute-force O(n^4) loop, then sweat through correctness; the optimal answer is O(n^2) and elegant.

The key insight is to count unordered pairs by their product, then expand back to ordered tuples with a constant multiplier. The multiplier turns out to be 8: each unordered pair-of-pairs can be arranged in 2 * 2 * 2 = 8 ordered tuples (two orderings inside the first pair, two inside the second, and two ways to swap which pair comes first).

The Core Insight#

For every unordered pair {a, b} compute a * b and increment count[product] in a hashmap. After processing all pairs, each product with k pairs contributes C(k, 2) = k * (k - 1) / 2 unordered pair-of-pairs. Multiply by 8 to get ordered tuples.

Visual Dry Run#

nums = [2, 3, 4, 6]. All pair products:

Only product 12 has 2 pairs. Tuples = 8 * C(2,2) = 8 * 1 = 8.

Solution (Optimal)#

from collections import defaultdict
 
class Solution:
    def tupleSameProduct(self, nums: list[int]) -> int:
        product_count = defaultdict(int)
        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 k in product_count.values():
            if k >= 2:
                result += 8 * k * (k - 1) // 2
        return result

var tupleSameProduct = function(nums) {
    const productCount = new Map();
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const p = nums[i] * nums[j];
            productCount.set(p, (productCount.get(p) || 0) + 1);
        }
    }
    let result = 0;
    for (const k of productCount.values()) {
        if (k >= 2) result += 8 * k * (k - 1) / 2;
    }
    return result;
};

Time: O(n^2) — every unordered pair is processed once. Space: O(n^2) — the hashmap can hold up to C(n, 2) distinct products.

Common Mistakes#

• Forgetting the factor of 8; counting only unordered pair-of-pairs gives result / 8.
• Iterating with j > i to avoid double counting, then accidentally double counting with j != i.
• Using C(k, 2) * 4 because the candidate forgot one of the three orderings.
• Overflow when nums[i] and nums[j] reach 10^4 and n is large; in JavaScript and Java use 64-bit math.
• Treating the input as having duplicates; the problem guarantees pairwise distinct, which simplifies the formula.

Interview Tips#

• Derive the multiplier of 8 from first principles. Interviewers often test this.
• Mention that a Counter (multi-set) is required because multiple pairs can share a product.
• Note the trade-off: O(n^2) time is unavoidable because the answer can be Θ(n^4) in the worst case.
• Walk through the example [2, 3, 4, 6] to ground the abstract formula.

Follow-up Questions#

• What if duplicates were allowed? Hint: pre-canonicalize pairs by sorted indices and adjust the count formula.
• What if you must return the actual tuples? Hint: store (i, j) lists per product, then enumerate cross-products.
• What if products are very large (up to 10^18)? Hint: hashing is fine but use 64-bit keys.
• Can you parallelize the count? Hint: shard pairs by product hash; counts are associative.
• What if products use + instead of * (so a + b == c + d)? Hint: same algorithm with sums.

Key Takeaways#

• LeetCode 1726 is a FAANG hashmap interview pattern: pair-product frequency map plus combinatorics.
• Each shared product with k pairs contributes 8 * C(k, 2) ordered tuples.
• Time is O(n^2), space is O(n^2); the answer can be Θ(n^4), so you cannot do better.
• The multiplier 8 = 2 (swap inside pair 1) * 2 (swap inside pair 2) * 2 (swap pairs).
• The pattern reappears in any "tuple with shared property" problem; recognize it once and reuse it.
• Watch for integer overflow when products grow large.
• This is a high-signal medium that separates candidates who panic at O(n^4) from those who reason combinatorially.