Tuple with Same Product solution and explanation
Google
9 more videos on this problem
Tuple with Same Product - Leetcode 1726 - PythonNeetCodeIO · 19:27 · 12K views
Tuple with Same Product | 4 Detailed Approaches | Dry Runs | Leetcode 1726 | codestorywithMIKcodestorywithMIK · 57:29 · 9K views
Tuple with Same Product | Leetcode 1726Techdose · 13:36 · 6K views
1726. Tuple with Same Product | leetcode daily challenge | shashcode | java | dsa | shashwatShashCode · 18:12 · 2K views
1726. Tuple with Same Product | Hash Table | Math | 3 ApproachesAryan Mittal · 19:39 · 2K views
LeetCode 1726. Tuple with Same Product - Interview Prep Ep 117Fisher Coder · 10:40 · 1K views
Tuple with Same Product | Leetcode 1726 | Contest 224 | Live coding sessionCoding Decoded · 10:28 · 1K views
1726. Tuple with Same Product (Leetcode Medium)Programming Live with Larry · 7:30 · 738 views
1726. Tuple With Same Product | Brute | Better | Optimal | Hash Map | LeetcodeRapid Syntax · 15:59 · 182 views
LeetCode 1726 Tuple with Same Product | Array | Hash Table | Asked in GoogleCode Harmony · 27:17 · 166 views
The problem
Given an array nums of distinct positive integers, return the number of tuples (a, b, c, d) such that a * b = c * d where a, b, c, and d are elements of nums, and a != b != c != d.
Example 1:
Input: nums = [2,3,4,6] Output: 8 Explanation: There are 8 valid tuples: (2,6,3,4) , (2,6,4,3) , (6,2,3,4) , (6,2,4,3) (3,4,2,6) , (4,3,2,6) , (3,4,6,2) , (4,3,6,2)
Example 2:
Input: nums = [1,2,4,5,10] Output: 16 Explanation: There are 16 valid tuples: (1,10,2,5) , (1,10,5,2) , (10,1,2,5) , (10,1,5,2) (2,5,1,10) , (2,5,10,1) , (5,2,1,10) , (5,2,10,1) (2,10,4,5) , (2,10,5,4) , (10,2,4,5) , (10,2,5,4) (4,5,2,10) , (4,5,10,2) , (5,4,2,10) , (5,4,10,2)
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 104- All elements in
numsare distinct.
Approach overview
Problem Overview: You receive an array of distinct integers. The task is to count the number of tuples (a, b, c, d) such that a * b = c * d and all four elements come from different indices. Order matters, so each valid pair combination generates multiple permutations of tuples.
Approach 1: Hashmap Based Approach (O(n^2) time, O(n^2) space)
The key observation: if two different pairs of numbers produce the same product, they can form valid tuples. Iterate through all pairs (i, j) with i < j and compute their product. Store the frequency of each product in a hash map. If a product appears k times, it means there are k pairs producing that product. Any two of these pairs can combine to form tuples. The number of pair combinations is k choose 2, and each pair combination generates 8 valid permutations of (a, b, c, d). This approach relies on fast hash lookups and pair enumeration, making it the optimal method using a hash table and counting technique.
Approach 2: Two Pointers Approach (O(n^3) time, O(1) space)
Sort the array first. Then iterate through every pair (i, j) to form a target product. For the remaining elements, attempt to find another pair whose product matches the target using a two‑pointer scan from both ends of the remaining subarray. Each time a matching pair is found, count the valid tuple permutations. This method avoids additional memory but repeatedly scans the array for matching products, which increases the runtime significantly compared to the hashing approach.
Recommended for interviews: The hashmap approach is what interviewers expect. It demonstrates recognition of pair-product collisions and reduces the search space from brute-force tuple enumeration to pair counting. Brute-force or pointer-based exploration shows understanding of the problem structure, but the O(n^2) hash map solution highlights strong pattern recognition and efficient use of data structures.
Approach 1: Hashmap Based Approach
In this approach, we will use a hashmap (dictionary) to keep track of products of each pair. The key will be the product, and the value will be the number of ways a particular product can be formed. We will iterate over each unique pair of numbers in the array, compute their product, and store the count of each product in the hashmap. For every pair, the count in the hashmap will give the number of tuples that can be formed with this product. For every new product count, the number of tuples formed can be calculated using combinatorial arithmetic logic (multiplying counts of previously seen pairs forming the same product).
def numOfTuples(nums):
product_count = {}
tuple_count = 0
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
product = nums[i] * nums[j]
if product in product_count:
tuple_count += product_count[product] * 8
product_count[product] = product_count.get(product, 0) + 1
return tuple_count
nums = [2, 3, 4, 6]
print(numOfTuples(nums))import java.util.HashMap;
import java.util.Map;
public class TupleCount {
public static int numOfTuples(int[] nums) {
Map<Integer, Integer> productCount = new HashMap<>();
int tupleCount = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
int product = nums[i] * nums[j];
tupleCount += productCount.getOrDefault(product, 0) * 8;
productCount.put(product, productCount.getOrDefault(product, 0) + 1);
}
}
return tupleCount;
}
public static void main(String[] args) {
int[] nums = {2, 3, 4, 6};
System.out.println(numOfTuples(nums));
}
}#include <iostream>
#include <unordered_map>
#include <vector>
int numOfTuples(const std::vector<int>& nums) {
std::unordered_map<int, int> productCount;
int tupleCount = 0;
for (size_t i = 0; i < nums.size(); i++) {
for (size_t j = i + 1; j < nums.size(); j++) {
int product = nums[i] * nums[j];
tupleCount += productCount[product] * 8; // Each existing pair gives 8 ways
productCount[product]++;
}
}
return tupleCount;
}
int main() {
std::vector<int> nums = {2, 3, 4, 6};
std::cout << numOfTuples(nums) << std::endl;
return 0;
}function numOfTuples(nums) {
const productCount = {};
let tupleCount = 0;
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
const product = nums[i] * nums[j];
if (product in productCount) {
tupleCount += productCount[product] * 8;
}
productCount[product] = (productCount[product] || 0) + 1;
}
}
return tupleCount;
}
const nums = [2, 3, 4, 6];
console.log(numOfTuples(nums));#include <stdio.h>
#include <stdlib.h>
int numOfTuples(int* nums, int numsSize) {
int* productCount = (int*)calloc(100000001, sizeof(int));
int tupleCount = 0;
for (int i = 0; i < numsSize; i++) {
for (int j = i + 1; j < numsSize; j++) {
int product = nums[i] * nums[j];
tupleCount += productCount[product] * 8; // Each pair contributes 8 tuples
productCount[product]++;
}
}
free(productCount);
return tupleCount;
}
int main() {
int nums[] = {2, 3, 4, 6};
int result = numOfTuples(nums, 4);
printf("%d\n", result);
return 0;
}using System;
using System.Collections.Generic;
public class TupleCount {
public static int NumOfTuples(int[] nums) {
Dictionary<int, int> productCount = new Dictionary<int, int>();
int tupleCount = 0;
for (int i = 0; i < nums.Length; i++) {
for (int j = i + 1; j < nums.Length; j++) {
int product = nums[i] * nums[j];
if (productCount.ContainsKey(product)) {
tupleCount += productCount[product] * 8;
}
if (productCount.ContainsKey(product)) {
productCount[product]++;
} else {
productCount[product] = 1;
}
}
}
return tupleCount;
}
public static void Main() {
int[] nums = { 2, 3, 4, 6 };
Console.WriteLine(NumOfTuples(nums));
}
}The Python solution uses a dictionary to store the frequency of each product encountered while iterating over all pairs. It calculates the number of possible tuples when a matching product is found in the dictionary.
The time complexity remains O(N^2) and space complexity is also O(U), where U is the number of unique products.
Approach 2: Two Pointers Approach
This approach aims to reduce time complexity by first sorting the array, and leveraging the two-pointer technique to find pairs with the same product more efficiently. Once the array is sorted, for each pair, the pointers can be adjusted based on whether the product is less than or greater than the target product for current analysis.
def numOfTuples(nums):
nums.sort()
tuple_count = 0
for i in range(len(nums) - 1):
for j in range(i + 1, len(nums)):
product = nums[i] * nums[j]
left, right = j + 1, len(nums) - 1
while left < right:
target = nums[left] * nums[right]
if target == product:
tuple_count += 8
left += 1
right -= 1
elif target < product:
left += 1
else:
right -= 1
return tuple_count
nums = [2, 3, 4, 6]
print(numOfTuples(nums))import java.util.Arrays;
public class TupleCount {
public static int numOfTuples(int[] nums) {
Arrays.sort(nums);
int tupleCount = 0;
for (int i = 0; i < nums.length - 1; i++) {
for (int j = i + 1; j < nums.length; j++) {
int product = nums[i] * nums[j];
int left = j + 1, right = nums.length - 1;
while (left < right) {
int target = nums[left] * nums[right];
if (target == product) {
tupleCount += 8;
left++;
right--;
} else if (target < product) {
left++;
} else {
right--;
}
}
}
}
return tupleCount;
}
public static void main(String[] args) {
int[] nums = {2, 3, 4, 6};
System.out.println(numOfTuples(nums));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int numOfTuples(vector<int>& nums) {
sort(nums.begin(), nums.end());
int tupleCount = 0;
for (size_t i = 0; i < nums.size() - 1; i++) {
for (size_t j = i + 1; j < nums.size(); j++) {
int product = nums[i] * nums[j];
size_t left = j + 1, right = nums.size() - 1;
while (left < right) {
int target = nums[left] * nums[right];
if (target == product) {
tupleCount += 8;
left++;
right--;
} else if (target < product) {
left++;
} else {
right--;
}
}
}
}
return tupleCount;
}
int main() {
vector<int> nums = {2, 3, 4, 6};
cout << numOfTuples(nums) << endl;
return 0;
}function numOfTuples(nums) {
nums.sort((a, b) => a - b);
let tupleCount = 0;
for (let i = 0; i < nums.length - 1; i++) {
for (let j = i + 1; j < nums.length; j++) {
let product = nums[i] * nums[j];
let left = j + 1, right = nums.length - 1;
while (left < right) {
let target = nums[left] * nums[right];
if (target === product) {
tupleCount += 8;
left++;
right--;
} else if (target < product) {
left++;
} else {
right--;
}
}
}
}
return tupleCount;
}
const nums = [2, 3, 4, 6];
console.log(numOfTuples(nums));#include <stdio.h>
#include <stdlib.h>
// Comparator function for qsort
int cmp(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int numOfTuples(int* nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), cmp);
int tupleCount = 0;
for (int i = 0; i < numsSize - 1; i++) {
for (int j = i + 1; j < numsSize; j++) {
int product = nums[i] * nums[j];
int left = j + 1, right = numsSize - 1;
while (left < right) {
int target = nums[left] * nums[right];
if (target == product) {
tupleCount += 8;
left++;
right--;
} else if (target < product) {
left++;
} else {
right--;
}
}
}
}
return tupleCount;
}
int main() {
int nums[] = {2, 3, 4, 6};
int result = numOfTuples(nums, 4);
printf("%d\n", result);
return 0;
}using System;
public class TupleCount {
public static int NumOfTuples(int[] nums) {
Array.Sort(nums);
int tupleCount = 0;
for (int i = 0; i < nums.Length - 1; i++) {
for (int j = i + 1; j < nums.Length; j++) {
int product = nums[i] * nums[j];
int left = j + 1, right = nums.Length - 1;
while (left < right) {
int target = nums[left] * nums[right];
if (target == product) {
tupleCount += 8;
left++;
right--;
} else if (target < product) {
left++;
} else {
right--;
}
}
}
}
return tupleCount;
}
public static void Main() {
int[] nums = { 2, 3, 4, 6 };
Console.WriteLine(NumOfTuples(nums));
}
}Python utilizes sorting, and the two-pointer method to quickly discover appropriate tuples by adjusting the pointer positions when the product condition is not met, attempting improvement over direct brute-force trials.
The time complexity is approximately O(N^3), considering both sorting and reduced search time with two pointers. Space complexity remains nominal at O(1) barring sorting.
Approach 3: Combination + Hash Table
Assuming there are n pairs of numbers, for any two pairs of numbers a, b and c, d that satisfy the condition a times b = c times d, there are a total of C_n^2 = \frac{n times (n-1)}{2} such combinations.
According to the problem description, each combination that satisfies the above condition can form 8 tuples that satisfy the problem requirements. Therefore, we can multiply the number of combinations with the same product by 8 (equivalent to left shifting by 3 bits) and add them up to get the result.
The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the length of the array.
function tupleSameProduct(nums: number[]): number {
const cnt: Map<number, number> = new Map();
for (let i = 1; i < nums.length; ++i) {
for (let j = 0; j < i; ++j) {
const x = nums[i] * nums[j];
cnt.set(x, (cnt.get(x) ?? 0) + 1);
}
}
let ans = 0;
for (const [_, v] of cnt) {
ans += (v * (v - 1)) / 2;
}
return ans << 3;
}func tupleSameProduct(nums []int) int {
cnt := map[int]int{}
for i := 1; i < len(nums); i++ {
for j := 0; j < i; j++ {
x := nums[i] * nums[j]
cnt[x]++
}
}
ans := 0
for _, v := range cnt {
ans += v * (v - 1) / 2
}
return ans << 3
}use std::collections::HashMap;
impl Solution {
pub fn tuple_same_product(nums: Vec<i32>) -> i32 {
let mut cnt: HashMap<i32, i32> = HashMap::new();
let mut ans = 0;
for i in 1..nums.len() {
for j in 0..i {
let x = nums[i] * nums[j];
*cnt.entry(x).or_insert(0) += 1;
}
}
for v in cnt.values() {
ans += (v * (v - 1)) / 2;
}
ans << 3
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Hashmap Based Approach | The time complexity remains O(N^2) and space complexity is also O(U), where U is the number of unique products. |
| Two Pointers Approach | The time complexity is approximately O(N^3), considering both sorting and reduced search time with two pointers. Space complexity remains nominal at O(1) barring sorting. |
| Combination + Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hashmap Based Approach | O(n^2) | O(n^2) | General case. Best performance when enumerating pair products and grouping them efficiently. |
| Two Pointers Approach | O(n^3) | O(1) | Useful when minimizing extra memory is required or when exploring pointer-based pair searching after sorting. |
Frequently asked questions
Is Tuple with Same Product easy or hard?
Tuple with Same Product is generally classified as a medium difficulty problem. The challenge lies in recognizing that equal products between pairs can be grouped and counted instead of checking every possible quadruple.
Tuple with Same Product Python/Java solution
Most implementations compute all pair products and store counts in a dictionary or hash map. Python uses a dictionary, Java uses HashMap, and C++ typically uses unordered_map. After counting frequencies, the result is calculated using the combination formula and multiplied by 8 for tuple permutations.
How to solve Tuple with Same Product in O(n)?
An O(n) solution is not achievable because the problem fundamentally depends on examining pair relationships between elements. At minimum, all O(n^2) pairs must be considered to detect equal products. The best practical approach uses a hash map to process these pairs efficiently in O(n^2) time.
What is the best approach for Tuple with Same Product?
The hash map pair-product approach is the most efficient. Compute the product for every pair of elements and store its frequency in a hash table. If a product appears k times, it forms k choose 2 pair combinations, and each combination produces 8 valid tuples. This results in O(n^2) time and O(n^2) space complexity.
Is Tuple with Same Product asked at Google/Amazon/Meta?
Tuple with Same Product represents a common interview pattern involving pair enumeration and hash maps. Variations of this problem appear in interviews at companies like Amazon, Google, and Meta where candidates are expected to recognize product collisions and optimize pair counting.
What data structure is used in Tuple with Same Product?
A hash table (hash map) is the primary data structure. It stores the frequency of each product generated by element pairs. This enables constant-time lookups and allows counting how many pair combinations share the same product.
What is the time complexity of Tuple with Same Product?
The optimal solution runs in O(n^2) time because it iterates through all pairs in the array and records their products in a hash map. Space complexity is also O(n^2) in the worst case due to storing pair product frequencies.