Find the Number of Ways to Place People I

main.md

Question

Approach

I consider a pair of points $(A, B)$ valid if $A$ lies to the upper-left of $B$, which means the $x$-coordinate of $A$ is less than or equal to that of $B$, and the $y$-coordinate of $A$ is greater than or equal to that of $B$. Equality on one axis is allowed, so cases where the two points form a straight vertical or horizontal line are also valid. Once such a pair is identified, I then check that no other point lies inside or on the border of the rectangle defined by $A$ and $B$ as opposite corners. In practice, this means for each candidate pair $(i, j)$, I scan all other points $k \neq i, j$ and verify that none of them satisfy the condition $x_i \leq x_k \leq x_j$ and $y_j \leq y_k \leq y_i$.

Implementation

class Solution:
    def numberOfPairs(self, points: List[List[int]]) -> int:
        n = len(points)
        ans = 0
        for i in range(n):
            xi, yi = points[i]
            for j in range(n):
                if i == j:
                    continue
                xj, yj = points[j]
                if xi <= xj and yi >= yj:
                    empty = True
                    for k in range(n):
                        if k == i or k == j:
                            continue
                        xk, yk = points[k]
                        if xi <= xk <= xj and yj <= yk <= yi:
                            empty = False
                            break
                    if empty:
                        ans += 1
        return ans

Complexities

• Time: O(n^2)
• Space: O(1)