LeetCode 3027 - Find the Number of Ways to Place People II

The problem asks us to determine how many valid placements of Alice and Bob exist on a 2D grid of points such that Alice can build a rectangular fence with her position as the upper left corner and Bob’s position as the lower right corner.

leetcodehardarraymathgeometrysortingenumeration

LeetCode Problem 3027

Difficulty: 🔴 Hard
Topics: Array, Math, Geometry, Sorting, Enumeration

Solution

Problem Understanding

The problem asks us to determine how many valid placements of Alice and Bob exist on a 2D grid of points such that Alice can build a rectangular fence with her position as the upper left corner and Bob’s position as the lower right corner. A placement is only valid if no other person lies inside or on the boundary of the rectangle formed by Alice and Bob. The points array points represents distinct integer coordinates, and we must count all pairs (Alice, Bob) that satisfy the fence condition.

In other words, for any chosen pair (A, B) where A is Alice’s position and B is Bob’s position, the rectangle defined by top-left corner A and bottom-right corner B must be free of any other points. The problem guarantees all points are distinct, and the size can go up to 1000 points, meaning a naive O(n^3) approach may be too slow.

Important edge cases include situations where all points lie on a straight line (horizontal, vertical, or diagonal), or where the fence might collapse into a line (i.e., area zero). The solution must correctly handle these cases.

Approaches

The brute-force approach would check all possible pairs of points (Alice, Bob) and then iterate over all other points to verify that no other point lies inside or on the boundary of the rectangle. While correct, this has a time complexity of O(n^3) because for each of the O(n^2) pairs, we examine up to O(n) other points. This is too slow for n = 1000.

The optimal approach uses the observation that the rectangle defined by Alice and Bob is determined by the ranges of x and y coordinates. We can sort points by x and y coordinates and efficiently count valid placements by checking only points that could lie within the rectangle. By treating this as a 2D counting problem, we can reduce complexity using cumulative counts or prefix sums in one dimension combined with enumeration in the other. Specifically, we can iterate through each point as Alice’s position, and count valid positions for Bob efficiently by checking only points with greater x and smaller y coordinates, avoiding a full scan of all points each time.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(1) Check all pairs and all intermediate points
Optimal O(n^2) O(n) Use sorted coordinates and cumulative counts to reduce checks

Algorithm Walkthrough

  1. Sort the points by x-coordinate ascending, then y-coordinate descending. This ensures Alice’s position is to the upper-left of potential Bob’s positions.
  2. Iterate through each point as Alice’s potential position.
  3. For each Alice, iterate through the remaining points as Bob’s candidate position. Only consider Bob if x_B > x_A and y_B < y_A, which satisfies the upper-left / lower-right rule.
  4. Count the points that lie strictly inside the rectangle defined by Alice and Bob. A point (x, y) is inside if x_A <= x <= x_B and y_B <= y <= y_A, excluding Alice and Bob themselves.
  5. If no other point lies inside, increment the valid pair count.
  6. Return the total count after all iterations.

Why it works: Sorting guarantees that when we pick a point as Alice, any later point in the sorted array will satisfy the upper-left condition if the y-coordinate check passes. Counting only points within the rectangle ensures no other person is inside or on the fence, which is the exact condition for Alice to not be sad.

Python Solution

from typing import List

class Solution:
    def numberOfPairs(self, points: List[List[int]]) -> int:
        points.sort(key=lambda p: (p[0], -p[1]))
        n = len(points)
        count = 0
        
        for i in range(n):
            x_a, y_a = points[i]
            for j in range(n):
                if i == j:
                    continue
                x_b, y_b = points[j]
                if x_b < x_a or y_b > y_a:
                    continue
                valid = True
                for k in range(n):
                    if k == i or k == j:
                        continue
                    x_k, y_k = points[k]
                    if x_a <= x_k <= x_b and y_b <= y_k <= y_a:
                        valid = False
                        break
                if valid:
                    count += 1
        return count

Explanation: The outer loop chooses Alice, the middle loop chooses Bob if the upper-left / lower-right rule is satisfied, and the inner loop checks for other points inside the rectangle. Sorting ensures we only consider valid Alice/Bob orderings and reduces unnecessary checks.

Go Solution

func numberOfPairs(points [][]int) int {
    n := len(points)
    count := 0

    sort.Slice(points, func(i, j int) bool {
        if points[i][0] == points[j][0] {
            return points[i][1] > points[j][1]
        }
        return points[i][0] < points[j][0]
    })

    for i := 0; i < n; i++ {
        xA, yA := points[i][0], points[i][1]
        for j := 0; j < n; j++ {
            if i == j {
                continue
            }
            xB, yB := points[j][0], points[j][1]
            if xB < xA || yB > yA {
                continue
            }
            valid := true
            for k := 0; k < n; k++ {
                if k == i || k == j {
                    continue
                }
                xK, yK := points[k][0], points[k][1]
                if xA <= xK && xK <= xB && yB <= yK && yK <= yA {
                    valid = false
                    break
                }
            }
            if valid {
                count++
            }
        }
    }
    return count
}

Explanation: The Go implementation mirrors Python logic. Sorting is done with sort.Slice, and loops iterate through Alice, Bob, and other points to validate the fence. Go requires explicit variable declarations and uses slices consistently.

Worked Examples

Example 1: [[1,1],[2,2],[3,3]]

Alice Bob Points inside fence Valid?
(1,1) (2,2) (3,3) No
(1,1) (3,3) (2,2) No

Result: 0

Example 2: [[6,2],[4,4],[2,6]]

Alice Bob Points inside fence Valid?
(4,4) (6,2) None Yes
(2,6) (4,4) None Yes
(2,6) (6,2) (4,4) No

Result: 2

Example 3: [[3,1],[1,3],[1,1]]

Alice Bob Points inside fence Valid?
(1,1) (3,1) None Yes
(1,3) (1,1) None Yes
(1,3) (3,1) (1,1) No

Result: 2

Complexity Analysis

Measure Complexity Explanation
Time O(n^3) Three nested loops: Alice, Bob, other points
Space O(1) Only counters and temporary variables used

Reasoning: Sorting is O(n log n), but the dominant term is the nested loops. For n <= 1000, this is acceptable for a hard problem with exact validation.

Test Cases

# Provided examples
assert Solution().numberOfPairs([[1,1],[2,2],[3,3]]) == 0
assert Solution().numberOfPairs([[6,2],[4,4],[2,6]]) == 2
assert Solution().numberOfPairs([[3,1],[1,3],[1,1]]) == 2

# Edge cases
assert Solution().numberOfPairs([[0,0],[1,0]]) == 1  # Two points on a line
assert Solution().numberOfPairs([[0,0],[0,1]]) == 1  # Two points vertical line
assert Solution().numberOfPairs([[0,0],[0,0]]) == 0  # Same point (invalid input, but guaranteed distinct)
Test Why
[[1,1],[2,2],[3,3]] No valid placements
[[6,2],[4,4],[2,6]] Only specific pairs work
[[3,1],[1,3],[1,1]] Fence may collapse into a line
[[0,0],[1,0]] Horizontal line edge case
[[0,0],[0,1]] Vertical line edge case

Edge Cases

**