Watch 10 video solutions for Find the Number of Ways to Place People II, a hard level problem involving Array, Math, Geometry. This walkthrough by codestorywithMIK has 4,790 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 2D array points of size n x 2 representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].
We define the right direction as positive x-axis (increasing x-coordinate) and the left direction as negative x-axis (decreasing x-coordinate). Similarly, we define the up direction as positive y-axis (increasing y-coordinate) and the down direction as negative y-axis (decreasing y-coordinate)
You have to place n people, including Alice and Bob, at these points such that there is exactly one person at every point. Alice wants to be alone with Bob, so Alice will build a rectangular fence with Alice's position as the upper left corner and Bob's position as the lower right corner of the fence (Note that the fence might not enclose any area, i.e. it can be a line). If any person other than Alice and Bob is either inside the fence or on the fence, Alice will be sad.
Return the number of pairs of points where you can place Alice and Bob, such that Alice does not become sad on building the fence.
Note that Alice can only build a fence with Alice's position as the upper left corner, and Bob's position as the lower right corner. For example, Alice cannot build either of the fences in the picture below with four corners (1, 1), (1, 3), (3, 1), and (3, 3), because:
(3, 3) and Bob at (1, 1), Alice's position is not the upper left corner and Bob's position is not the lower right corner of the fence.(1, 3) and Bob at (1, 1), Bob's position is not the lower right corner of the fence.
Example 1:
Input: points = [[1,1],[2,2],[3,3]] Output: 0 Explanation: 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 Explanation: 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 Explanation: 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 <= 1000points[i].length == 2-109 <= points[i][0], points[i][1] <= 109points[i] are distinct.Problem Overview: You are given coordinates of people on a 2D grid. Count how many ordered pairs can form the top-left and bottom-right corners of a rectangle such that no other person lies inside or on the boundary of that rectangle. The task is essentially checking geometric relationships between pairs of points while ensuring the rectangle they form is empty.
Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)
The most direct approach checks every pair of people as potential rectangle corners. For each pair (i, j), first verify that the coordinates form a valid top-left and bottom-right relationship: x[i] ≤ x[j] and y[i] ≥ y[j]. If the pair qualifies, iterate through all other points and check whether any point lies inside or on the rectangle defined by those two corners. If no such point exists, the pair contributes one valid configuration.
This method relies purely on enumeration using basic array iteration and simple geometry checks. While easy to reason about, it performs three nested scans and becomes slow when the number of points grows.
Approach 2: Optimized with Sorting and Sweep (O(n^2) time, O(1) space)
A key observation eliminates the need to check every interior point explicitly. Sort all coordinates by x in ascending order, and for ties sort by y in descending order. Fix a person i as the potential top-left corner, then scan candidates j > i as bottom-right corners.
During this scan maintain a variable maxY representing the highest y value encountered so far that is still below or equal to y[i]. When visiting a new point j, it forms a valid pair only if y[j] ≤ y[i] and y[j] > maxY. The first condition ensures the rectangle orientation is correct. The second guarantees no previously processed point lies inside the rectangle. Once counted, update maxY to y[j].
This works because sorting by x ensures every candidate lies to the right of i. Tracking the highest blocking y prevents counting rectangles that would contain another person. The approach combines sorting with controlled enumeration to remove the inner validation loop.
Recommended for interviews: Interviewers usually expect the sorted sweep approach. Starting with the brute force solution shows you understand the geometric constraints, but recognizing that sorting by x and tracking the next valid y eliminates the third loop demonstrates stronger algorithmic reasoning.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair + Interior Check | O(n^3) | O(1) | Best for understanding the geometric constraints and validating logic on small inputs |
| Sorting + Controlled Enumeration | O(n^2) | O(1) | Preferred solution for interviews and competitive programming with moderate input sizes |