1387. Dominated Points Tally
A survey team plots n sensor stations on a map, where points[i] = [x, y] is the position of station i. Station j is dominated by station i when points[i] has a strictly smaller x and a strictly smaller y than points[j]. Stations that share an x value, or share a y value, never dominate each other, and duplicate positions do not dominate one another.
Return an array counts of length n where counts[i] is the number of other stations that have strictly smaller x and strictly smaller y than station i, in the original order of points.
Sweep the stations by x ascending, compress the y values, and keep a Fenwick tree of the y ranks already inserted. Process a whole group of equal x first by querying every member, and only then insert the group, so equal x never counts. The intended solution runs in O(n log n) time and O(n) space.
Example 1
- Input:
- points = [[3,4],[1,1],[2,5],[3,2],[5,5]]
- Output:
- [1,0,1,1,3]
- Explanation:
Station [5,5] dominates-count 3 because [3,4], [1,1] and [3,2] are strictly smaller in both coordinates ([2,5] shares y); [3,4], [2,5] and [3,2] each see only [1,1]; [1,1] sees none.
Example 2
- Input:
- points = [[2,2],[2,2],[2,2]]
- Output:
- [0,0,0]
- Explanation:
Duplicate positions never dominate each other, so every count is 0.
Example 3
- Input:
- points = [[7,7]]
- Output:
- [0]
- Explanation:
A single station has nothing to compare with.
Constraints
1 ≤ n (points.length) ≤ 105
points[i].length == 2
0 ≤ x, y ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 6,000 msC++ 1,500 msJava 3,000 msJavaScript 3,000 msTypeScript 3,000 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)