NeetCode #930LC-1726MediumMath & Geometry
← Back to All Problems#930 · #1726 · Tuple with Same Product(同积元组)
📌 Problem Statement & Constraints
Given an array
nums of distinct positive integers, count the tuples (a, b, c, d) with a * b = c * d where a, b, c, d are four distinct elements of nums in any order. Constraints: 1 <= nums.length <= 1000, 1 <= nums[i] <= 10^4, all elements distinct.💡 Core Algorithmic Approaches
- Enumerate every unordered pair and count how many pairs share each product using a hash map.
- If a product occurs
ktimes, any two of those pairs form a valid set of four indices, givingC(k, 2)index-quadruples. - Because the elements are distinct, two different pairs never share an index, so no extra filtering is needed.
- Each index-quadruple yields 8 ordered tuples
(a, b, c, d): 2 ways to order the two pairs times 2 orderings inside each pair. Answer =sum(C(k, 2) * 8).
💻 Benchmark Python3 Implementation
class Solution:
def tupleSameProduct(self, nums: List[int]) -> int:
from collections import defaultdict
from itertools import combinations
cnt = defaultdict(int)
for a, b in combinations(nums, 2):
cnt[a * b] += 1
res = 0
for k in cnt.values():
res += k * (k - 1) // 2 * 8 # C(k, 2) pairs of pairs, 8 orders each
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^2): all pairs are enumerated.
💾 Space Complexity
O(n^2): the product hash map.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting the factor 8: each choice of two pairs gives 8 ordered tuples, not 4 — 2 pair orderings times 2 internal orderings per pair.
- Brute-forcing four nested loops: O(n^4) with
n = 1000is far too slow. - Fearing repeated indices: the distinctness guarantee means any two distinct pairs use four different indices.
- Using a set of products instead of counts: the multiplicity is needed to apply
C(k, 2).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.