Duplicate Coordinate Pairs ā Problem Statement & Solution Guide
Problem Description
You are given an array of coordinate pairs coords, where each coordinate pair is represented as an array of two integers [x, y]. Find all pairs of indices (i, j) such that coords[i] is equal to coords[j] and i < j. Return the count of such pairs.
Examples
Input
[[1, 2], [1, 2], [1, 2], [1, 2], [1, 2], [1, 2]]
Output
3
Explanation: Step-by-step: with input [[1, 2], [1, 2], [1, 2], [1, 2], [1, 2], [1, 2]], we first create a hashmap to store the frequency of each coordinate pair. Then, we iterate through the hashmap and for each pair, we calculate the number of pairs that can be formed with the current pair. Finally, we return the total count of pairs.
Input
[[1, 2], [2, 3], [1, 2], [3, 4], [1, 2], [4, 5]]
Output
4
Explanation: Step-by-step: with input [[1, 2], [2, 3], [1, 2], [3, 4], [1, 2], [4, 5]], we first create a hashmap to store the frequency of each coordinate pair. Then, we iterate through the hashmap and for each pair, we calculate the number of pairs that can be formed with the current pair. Finally, we return the total count of pairs.
Constraints
- {"name":"Coordinate Range","description":"-10^9 <= x, y <= 10^9"}
- {"name":"Array Length","description":"1 <= coords.length <= 10^5"}
Optimal Approach & Strategy
The optimized approach uses a HashMap to store the coordinates and their indices, allowing for a time complexity of O(n). This approach iterates over the array once, making it much more efficient for large arrays.
Brute Force Approach
The brute-force approach involves comparing each pair of coordinates in the array, resulting in a time complexity of O(nĀ²). This approach is inefficient for large arrays.
Verified Code Solutions
function duplicateCoordinatePairs(coords) {
let count = 0;
let map = new Map();
for (let i = 0; i < coords.length; i++) {
let key = coords[i].join(',');
if (map.has(key)) {
count += map.get(key);
map.set(key, map.get(key) + 1);
} else {
map.set(key, 1);
}
}
return count;
}class Solution {
public int duplicatePairs(int[][] coords) {
Map<String, Integer> freq = new HashMap<>();
int count = 0;
for (int[] coord : coords) {
String key = coord[0] + " " + coord[1];
if (freq.containsKey(key)) {
count += freq.get(key);
freq.put(key, freq.get(key) + 1);
} else {
freq.put(key, 1);
}
}
return count - coords.length;
}
}def duplicate_pairs(coords):
freq = {}
count = 0
for coord in coords:
if coord in freq:
count += freq[coord]
freq[coord] += 1
else:
freq[coord] = 1
return count - len(coords)function duplicateCoordinatePairs(coords) {
let count = 0;
let map = new Map();
for (let i = 0; i < coords.length; i++) {
let key = coords[i].join(',');
if (map.has(key)) {
count += map.get(key);
map.set(key, map.get(key) + 1);
} else {
map.set(key, 1);
}
}
return count;
}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.