Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Sorting can replace the third-point scan used in the simpler version. For a fixed upper-left point, inspect potential lower-right points from left to right. Among previously inspected points at or below the upper boundary, the highest y-coordinate determines whether the next rectangle is blocked.

Approach

Sort by increasing x-coordinate and, for equal x, decreasing y-coordinate. Fix each point as the upper-left corner. Set an initially unbounded lower threshold and scan later points. Ignore a point above the upper-left corner. Count a candidate only when its y-coordinate is strictly above the threshold and no higher than the upper boundary; then raise the threshold to its y-coordinate.

Any later candidate at or below that threshold has an earlier point inside or on its rectangle. A candidate above it has no such blocker. Equal-x descending order handles vertical boundaries correctly, and the strict threshold comparison rejects horizontal-boundary blockers. Summing the accepted candidates over all upper-left corners counts exactly the valid pairs.

class Solution:
    def numberOfPairs(self, points: List[List[int]]) -> int:
        n = len(points)
        points.sort(key = lambda x: x[1], reverse = True)
        points.sort(key = lambda x: x[0])
        # points.sort(key = lambda x: (x[0], -x[1]))
        res = 0

        for i in range(n):
            mxy = points[i][1]
            mny = float('-inf')
            for j in range(i + 1, n):
                _, y = points[j]
                if mny < y <= mxy:
                    mny = y
                    res += 1

        return res

Complexity analysis

Let n = points.length. Time: O(n^2) after O(n log n) sorting. Auxiliary space: O(n) in the worst case for sorting.