Duplicate Coordinate Pairs — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Arrays and solve the Duplicate Coordinate Pairs problem optimally.
O(n)O(m)Problem Description
Given an array coords of length n, where each element is a two‑integer pair [x,y] representing a point on the Cartesian plane, determine how many unordered index pairs (i,j) satisfy i<j and coords[i] equals coords[j] (i.e., both x and y coordinates match). Return this count as an integer.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Duplicate Coordinate Pairs"
WHY DOES IT MATTER?
Counting duplicate pairs appears in many deduplication, clustering, and collision‑detection tasks; mastering the frequency‑map pattern lets you solve a broad class of problems that would otherwise be quadratic.
OPTIMIZATION CHALLENGE
The key insight is that the number of unordered index pairs from a bucket of size k is k*(k-1)/2, so you never need to enumerate the pairs—just the bucket size. This reduces both time from O(n²) to O(n) and space to O(distinct points).
REAL-WORLD CONNECTION
Think of a GPS logging service that receives millions of location pings; detecting how many devices reported the exact same latitude‑longitude at the same second is analogous to counting duplicate coordinate pairs across a distributed log stream.
When coding, build the hashmap with a composite key (e.g., "x#y" or a tuple) and update the answer on the fly: answer += currentCount before incrementing, which avoids a second pass over the map.
COMPLEXITY AT A GLANCE
O(n)O(m)Core Theory — Why This Approach?
The problem reduces to counting how many times each distinct coordinate pair appears and then summing the number of unordered index pairs that can be formed from those frequencies. A naive double‑loop checks every (i,j) combination, yielding O(n²) time which quickly becomes infeasible for n up to 10⁵ or higher. The optimal paradigm leverages a frequency map (hash table) to aggregate identical points in linear time, then applies the combinatorial formula nC2 = n*(n-1)/2 for each bucket. This transforms the problem into a classic “count duplicate elements” pattern, where the heavy lifting is done by constant‑time hash operations rather than quadratic comparisons.
Interview Questions on This Problem
Q1How would you modify the solution if the coordinates could be floating‑point numbers with precision issues?
Normalize the floats by rounding to a fixed number of decimal places or converting them to scaled integers before using them as hashmap keys, ensuring that two points that are effectively equal map to the same bucket.
Q2What is the time and space complexity if the input array is already sorted lexicographically by (x,y)?
Even if sorted, you can still solve it in O(n) time and O(1) extra space by scanning once and counting consecutive equal pairs; however, the hashmap solution remains O(n) time and O(n) space, which is acceptable for unsorted data.
Q3In a distributed system where the coordinate list is sharded across multiple nodes, how would you compute the total duplicate count efficiently?
Each node computes local frequencies and the local duplicate count, then a reduce step merges the frequency maps (or just aggregates the counts) across nodes; the final sum of nC2 for each global frequency yields the answer with O(total n) work distributed across nodes.
Examples
Input
[[0,0],[1,2],[0,0],[3,4],[1,2]]
Output
2
Explanation: The pair (0,2) shares the point [0,0] and the pair (1,4) shares the point [1,2]; no other indices match, so the total is 2.
Input
[[5,5],[5,5],[5,5]]
Output
3
Explanation: All three points are identical. The matching index pairs are (0,1), (0,2) and (1,2), giving a total of 3.
Input
[[-1,2],[3,4],[5,6]]
Output
0
Explanation: No two points are the same, therefore the count of duplicate pairs is 0.
Constraints
- 1<=coords.length<=100000
- -1000000000<=coords[i][0]<=1000000000
- -1000000000<=coords[i][1]<=1000000000
Optimal Approach & Strategy
Traverse the array once, store each point’s frequency in a hashmap, and accumulate the result using the combination formula for each frequency.
Brute Force Approach
Loop over all i<j and compare coords[i] with coords[j]; increment a counter each time they match.
Code Solutions
function countDuplicatePairs(coords) {
const map = new Map();
for(const [x,y] of coords){
const key = `${x},${y}`;
map.set(key, (map.get(key) || 0) + 1);
}
let ans = 0;
for(const c of map.values()){
ans += c * (c - 1) / 2;
}
return ans;
}
const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(input.length===0){process.exit(0);}
let idx=0; const n = input[idx++];
let coords=[];
for(let i=0;i<n;i++){
const x = input[idx++];
const y = input[idx++];
coords.push([x,y]);
}
process.stdout.write(String(countDuplicatePairs(coords)));#include <bits/stdc++.h>
using namespace std;
int countDuplicatePairs(const vector<pair<int,int>>& coords) {
unordered_map<long long,long long> freq;
for(const auto& p: coords){
long long key = (static_cast<long long>(p.first) << 32) ^ (static_cast<unsigned int>(p.second));
++freq[key];
}
long long ans = 0;
for(const auto& kv: freq){
long long c = kv.second;
ans += c * (c - 1) / 2;
}
return static_cast<int>(ans);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; if(!(cin>>n)) return 0;
vector<pair<int,int>> coords(n);
for(int i=0;i<n;++i) cin>>coords[i].first>>coords[i].second;
cout<<countDuplicatePairs(coords);
return 0;
}import java.io.*;
import java.util.*;
public class Main {
public static long countDuplicatePairs(List<int[]> coords) {
Map<Long, Long> map = new HashMap<>();
for (int[] p : coords) {
long key = ((long) p[0] << 32) ^ (p[1] & 0xffffffffL);
map.put(key, map.getOrDefault(key, 0L) + 1);
}
long ans = 0;
for (long c : map.values()) {
ans += c * (c - 1) / 2;
}
return ans;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if (line == null || line.isEmpty()) return;
int n = Integer.parseInt(line.trim());
List<int[]> coords = new ArrayList<>();
for (int i = 0; i < n; i++) {
String[] parts = br.readLine().trim().split("\\s+");
int x = Integer.parseInt(parts[0]);
int y = Integer.parseInt(parts[1]);
coords.add(new int[]{x, y});
}
System.out.print(countDuplicatePairs(coords));
}
}from collections import Counter
def count_duplicate_pairs(coords):
cnt = Counter(coords)
return sum(c*(c-1)//2 for c in cnt.values())
if __name__ == "__main__":
import sys
data = sys.stdin.read().strip().split()
if not data:
sys.exit(0)
it = iter(data)
n = int(next(it))
coords = [(int(next(it)), int(next(it))) for _ in range(n)]
print(count_duplicate_pairs(coords))function countDuplicatePairs(coords) {
const map = new Map();
for(const [x,y] of coords){
const key = `${x},${y}`;
map.set(key, (map.get(key) || 0) + 1);
}
let ans = 0;
for(const c of map.values()){
ans += c * (c - 1) / 2;
}
return ans;
}
const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(input.length===0){process.exit(0);}
let idx=0; const n = input[idx++];
let coords=[];
for(let i=0;i<n;i++){
const x = input[idx++];
const y = input[idx++];
coords.push([x,y]);
}
process.stdout.write(String(countDuplicatePairs(coords)));Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.