#3027

Hard

LeetCode Problem Workspace

Find the Number of Ways to Place People II

Calculate all valid placements of people on a 2D grid ensuring Alice can fence herself with Bob without enclosing others.

array math geometry sorting enumeration

Problem Statement

You are given a list of n unique points on a 2D plane represented as points[i] = [xi, yi]. Each point must hold exactly one person. Alice and Bob are two special people, and Alice wants to build a rectangular fence using her position as the upper-left corner and Bob's position as the lower-right corner. No other person should lie on or inside the fence.

Determine the total number of ways to assign all people to points so that Alice can fence with Bob according to the rules. The fence can be degenerate (a line), and placement is invalid if any other person interferes with the fence boundaries.

Examples

Example 1

Input: points = [[1,1],[2,2],[3,3]]

Output: 0

There is no way to place Alice and Bob such that Alice can build a fence with Alice's position as the upper left corner and Bob's position as the lower right corner. Hence we return 0.

Example 2

Input: points = [[6,2],[4,4],[2,6]]

Output: 2

There are two ways to place Alice and Bob such that Alice will not be sad:

Place Alice at (4, 4) and Bob at (6, 2).
Place Alice at (2, 6) and Bob at (4, 4). You cannot place Alice at (2, 6) and Bob at (6, 2) because the person at (4, 4) will be inside the fence.

Example 3

Input: points = [[3,1],[1,3],[1,1]]

Output: 2

There are two ways to place Alice and Bob such that Alice will not be sad:

Place Alice at (1, 1) and Bob at (3, 1).
Place Alice at (1, 3) and Bob at (1, 1). You cannot place Alice at (1, 3) and Bob at (3, 1) because the person at (1, 1) will be on the fence. Note that it does not matter if the fence encloses any area, the first and second fences in the image are valid.

Constraints

2 <= n <= 1000
points[i].length == 2
-109 <= points[i][0], points[i][1] <= 109
All points[i] are distinct.

Solution Approach

Sort Points Strategically

Sort the points by increasing x-coordinate and break ties by decreasing y-coordinate. This order ensures that when selecting Alice as upper-left and Bob as lower-right, the fence can be checked quickly for interference using index ranges.

Check Valid Fences Using Math

For each candidate pair of Alice and Bob, compute the rectangle defined by their coordinates. Use simple comparisons to detect if any other person lies within or on the fence. If none do, increment the valid count.

Optimize Counting

Instead of testing all permutations, use combinatorial logic and array scanning to avoid redundant checks. Maintain precomputed min/max y-values in ranges to quickly skip invalid pairs, reducing time complexity.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The naive approach checks every pair of points with every other point inside the rectangle, giving O(n^3). Sorting and precomputing min/max values reduces repeated scans and can approach O(n^2) in practice, using O(n) extra space for auxiliary arrays.

What Interviewers Usually Probe

Sorting points cleverly can simplify fence validation.
Consider degenerate rectangles where fence area is zero.
Be mindful of off-by-one errors when checking if points lie on the fence.

Common Pitfalls or Variants

Common pitfalls

Forgetting that the fence can be a line, not just a rectangle with area.
Checking all permutations instead of efficient pair-based counting.
Incorrectly including points exactly on the fence as invalid.

Follow-up variants

Allow multiple people inside the fence and count ways with k extra people.
Change the fence shape from rectangle to arbitrary convex polygon.
Limit Alice and Bob placements to a specific quadrant and count arrangements.

FAQ

What is the main pattern used in Find the Number of Ways to Place People II?

The primary pattern is 'Array plus Math', combining array sorting and geometric checks to verify valid fences for Alice and Bob.

Can the fence have zero area?

Yes, the rectangle can degenerate into a line if Alice and Bob share an x or y coordinate.

Do other people on the fence make Alice sad?

Yes, if any person besides Alice and Bob is on or inside the fence, the placement is invalid.

What is an efficient way to check if a rectangle is empty?

Sort points and precompute min/max y-values in subarrays, then compare Alice and Bob coordinates to skip invalid ranges quickly.

What input sizes are supported for this problem?

The problem supports 2 <= n <= 1000 points, with all coordinates in the range -10^9 to 10^9.

terminal

Solution

Solution 1: Sorting and Classification

First, we sort the array. Then, we can classify the results based on the properties of a triangle.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def numberOfPairs(self, points: List[List[int]]) -> int:
        points.sort(key=lambda x: (x[0], -x[1]))
        ans = 0
        for i, (_, y1) in enumerate(points):
            max_y = -inf
            for _, y2 in points[i + 1 :]:
                if max_y < y2 <= y1:
                    max_y = y2
                    ans += 1
        return ans

Continue Practicing

#3025 find the number of ways to place people i #3380 maximum area rectangle with point constraints i #3102 minimize manhattan distances