Find the Number of Ways to Place People II
HardPrompt
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:
- With Alice at
(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. - With Alice at
(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] <= 109- All
points[i]are distinct.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly translates the problem statement into code. It examines every possible pair of points for Alice and Bob. For each potential pair that satisfies the upper-left/lower-right condition, it then checks every other point to see if it falls within the rectangular fence. This method is straightforward but computationally expensive.
Algorithm
- Initialize a counter
countto 0. - Iterate through each point
points[i]as a potential location for Alice. - Inside this loop, iterate through each point
points[j]as a potential location for Bob, ensuringiis not equal toj. - Let
alice = points[i]andbob = points[j]. - Check if Alice is at an upper-left position relative to Bob:
alice.x <= bob.xandalice.y >= bob.y. If not, this pair is invalid, so continue to the next pair. - If the position condition holds, assume the pair is valid by setting a flag
is_sad = false. - Start a third loop to check for interfering points. Iterate through all other points
points[k](wherekis notiorj). - For each point
p = points[k], check if it lies inside or on the fence defined by Alice and Bob:alice.x <= p.x <= bob.xandbob.y <= p.y <= alice.y. - If an interfering point is found, set
is_sad = trueand break the innermost loop. - After checking all other points, if
is_sadremainsfalse, it means the pair(alice, bob)is valid. Increment thecount. - After all loops complete, return the total
count.
Walkthrough
The brute-force algorithm systematically checks all possibilities. It uses three nested loops. The outer two loops select a pair of distinct points for Alice and Bob. The first check ensures that Alice's point (x_A, y_A) and Bob's point (x_B, y_B) satisfy the geometric requirement x_A <= x_B and y_A >= y_B. If they do, the third loop iterates through all remaining n-2 points to verify that none of them are inside or on the boundary of the rectangle formed by Alice and Bob. A pair is counted only if this 'emptiness' condition is met.
class Solution { public int numberOfPairs(int[][] points) { int n = points.length; int count = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j) continue; int[] alice = points[i]; int[] bob = points[j]; if (alice[0] <= bob[0] && alice[1] >= bob[1]) { boolean isSad = false; for (int k = 0; k < n; k++) { if (k == i || k == j) continue; int[] p = points[k]; if (p[0] >= alice[0] && p[0] <= bob[0] && p[1] >= bob[1] && p[1] <= alice[1]) { isSad = true; break; } } if (!isSad) { count++; } } } } return count; }}Complexity
Time
O(N³), where N is the number of points. The three nested loops each run up to N times, leading to a cubic time complexity.
Space
O(1) extra space, as it only requires a few variables for loops and counting.
Trade-offs
Pros
Simple to understand and implement as it follows the problem's definition directly.
Cons
Highly inefficient due to its cubic time complexity.
Will likely result in a 'Time Limit Exceeded' error for larger inputs, such as the
n=1000constraint.
Solutions
Solution
public class Solution { public int NumberOfPairs(int[][] points) { Array.Sort(points, (a, b) => a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]); int ans = 0; int n = points.Length; int inf = 1 << 30; for (int i = 0; i < n; ++i) { int y1 = points[i][1]; int maxY = -inf; for (int j = i + 1; j < n; ++j) { int y2 = points[j][1]; if (maxY < y2 && y2 <= y1) { maxY = y2; ++ans; } } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.