Problem Statement in English

You’re given a list of points in a 2D plane, where each point is represented by its coordinates (x, y). Your task is to find the number of pairs of points (A, B) such that A is to the left of B (i.e., A[0] < B[0]) and the y-coordinate of A is greater than the y-coordinate of B (i.e., A[1] > B[1]).

There should be no points inside or on the boundary of the rectangle formed by A and B.

Approach

It makes a huge difference to sort the points strategically. We want smallest $x$ and biggest $y$ values first.

After that we can use a nested loop to find all valid pairs (A, B) by checking the conditions outlined in the problem statement. It does require a bit of edge case handling especially for points on the boundary and such.

Solution in Python


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

        for i in range(n):
            A = points[i]
            top = A[1]
            bottom = float("-inf")

            for j in range(i + 1, n):
                B = points[j]

                if bottom < B[1] <= top:
                    bottom = B[1]
                    res += 1

                    if top == bottom:
                        break

        return res

Complexity

  • Time: $O(n^2)$
    Since we use a nested loop.

  • Space: $O(1)$
    Since we only use a few extra constant space variables.

Mistakes I Made

I needed help handling the edge cases in this one.

And we are done.