Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The small input permits testing every ordered pair of people directly. A pair is valid only if the first point can be the upper-left corner, the second can be the lower-right corner, and no other point lies inside or on the boundary of their rectangle.

Approach

Choose distinct indices i and j. Reject them unless ax <= bx and ay >= by. These non-strict comparisons also allow rectangles that collapse to a horizontal or vertical line.

Scan every other point. If its x-coordinate is between ax and bx inclusively and its y-coordinate is between by and ay inclusively, reject the pair immediately. Otherwise count the pair after the scan finishes. Ordered enumeration assigns the two roles explicitly, and skipping the chosen indices prevents their corner points from being mistaken for blockers.

class Solution:
    def numberOfPairs(self, points: List[List[int]]) -> int:
        n = len(points)
        res = 0

        for i in range(n):
            ax, ay = points[i]
            for j in range(n):
                if i == j:
                    continue
                bx, by = points[j]
                if not (ax <= bx and ay >= by):
                    continue
                skip = False
                for k in range(n):
                    if k == i or k == j:
                        continue
                    cx, cy = points[k]
                    if (cx >= ax and cx <= bx) and (cy <= ay and cy >= by):
                        skip = True
                        break
                if not skip:
                    res += 1

        return res

Complexity analysis

Let n = points.length. Time: O(n^3). Auxiliary space: O(1).