mediumArraysPattern: HashMap / HashSet
Duplicate Coordinate Pairs Solution
Problem Statement
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
Example 1:
Input:[[1, 2], [3, 4], [1, 2], [5, 6], [1, 2]]
Output:3
Explanation: There are three pairs of spacecraft indices with the same coordinates (0, 2), (0, 4), (2, 4)
Example 2:
Input:[[1, 1], [2, 2], [3, 3], [1, 1]]
Output:1
Explanation: There is one pair of spacecraft indices with the same coordinates (0, 3)
Constraints
- {"name":"Coordinate Range","description":"-10^9 <= x, y <= 10^9"}
- {"name":"Array Length","description":"1 <= coords.length <= 10^5"}
Time: O(n) Space: O(n)
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.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.