Problem statement

https://binarysearch.com/problems/Remove-Smaller-Coordinates/

Solution

Sort points by x in decreasing order. Also keep cumulative min for maximum of prefixes. Then when we have new point, we know that its x coordinate is smaller than all previous. About y, we will choose the biggest y in points so far and if it is bigger than y coordinate of new point, we can be sure than new point is OK.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, P):
        arr = sorted(((i, x, y) for i, (x, y) in enumerate(P)), key=lambda x: (-x[1], -x[2]))
        ans_idx, last_y = [], -float("inf")
        for i, x, y in arr:
            if y > last_y:
                ans_idx += [i]
                last_y = y
        return [P[i] for i in sorted(ans_idx)]