Find the Number of Ways to Place People II

Hard

#2695Time: 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.

Patterns

Math Geometry Enumeration

Algorithms

Sorting

Data structures

Array

Prompt

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] = [x_i, y_i].

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 <= 1000
points[i].length == 2
-10⁹ <= points[i][0], points[i][1] <= 10⁹
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 count to 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, ensuring i is not equal to j.
Let alice = points[i] and bob = points[j].
Check if Alice is at an upper-left position relative to Bob: alice.x <= bob.x and alice.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] (where k is not i or j).
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.x and bob.y <= p.y <= alice.y.
If an interfering point is found, set is_sad = true and break the innermost loop.
After checking all other points, if is_sad remains false, it means the pair (alice, bob) is valid. Increment the count.
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.

1class Solution {2    public int numberOfPairs(int[][] points) {3        int n = points.length;4        int count = 0;5        for (int i = 0; i < n; i++) {6            for (int j = 0; j < n; j++) {7                if (i == j) continue;8 9                int[] alice = points[i];10                int[] bob = points[j];11 12                if (alice[0] <= bob[0] && alice[1] >= bob[1]) {13                    boolean isSad = false;14                    for (int k = 0; k < n; k++) {15                        if (k == i || k == j) continue;16                        int[] p = points[k];17                        if (p[0] >= alice[0] && p[0] <= bob[0] && p[1] >= bob[1] && p[1] <= alice[1]) {18                            isSad = true;19                            break;20                        }21                    }22                    if (!isSad) {23                        count++;24                    }25                }26            }27        }28        return count;29    }30}

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=1000 constraint.

This optimized approach significantly improves performance by using a clever sorting strategy. By sorting the points first by their x-coordinate (and y-coordinate for ties), we can establish a fixed order for considering pairs. This allows us to check for interfering points in a much more efficient O(N²) manner, avoiding the third nested loop of the brute-force method.

Algorithm

First, sort the points array. The primary sorting key is the x-coordinate in ascending order. The secondary key for ties in x-coordinates is the y-coordinate in descending order.
Initialize a counter count to 0.
Iterate with an outer loop from i = 0 to n-1. The point p_i at points[i] will be considered as Alice's location.
For each p_i, initialize a variable maxYUnderAlice to a very small number (e.g., Integer.MIN_VALUE). This will track the maximum y-coordinate of intermediate points that are valid blockers.
Start an inner loop from j = i + 1 to n-1. The point p_j at points[j] is a potential location for Bob or an intermediate point.
Let aliceY = p_i[1] and bobY = p_j[1].
Check if p_j is 'below' p_i (i.e., bobY <= aliceY). Points above p_i can't be Bob and can't block the view in the required manner.
If bobY <= aliceY, check if p_j is a valid Bob. It is valid if it's not blocked by any previous intermediate point that was also below Alice. This condition is met if bobY > maxYUnderAlice.
If both conditions (bobY <= aliceY and bobY > maxYUnderAlice) are true, increment count.
After the check, update maxYUnderAlice = max(maxYUnderAlice, bobY) to account for p_j as a potential blocker for subsequent points.
After the loops complete, return the total count.

Walkthrough

The core idea is to reduce the complexity of checking for interfering points. We sort the points by x-coordinate (ascending) and then by y-coordinate (descending). This ensures that if we pick p_i for Alice and p_j for Bob with i < j, the condition x_i <= x_j is automatically satisfied.

The problem then simplifies to finding pairs (p_i, p_j) with i < j such that y_i >= y_j, and no intermediate point p_k (with i < k < j) lies inside the fence. An intermediate point p_k is inside the fence if y_j <= y_k <= y_i.

To solve this efficiently, we iterate through each point p_i as Alice. For each p_i, we iterate through all subsequent points p_j (j > i). We only need to consider p_j where y_j <= y_i. For such a p_j to be a valid Bob, no intermediate point p_k that is also 'below' Alice (y_k <= y_i) can block it. A point p_k blocks p_j if y_k >= y_j. This means a valid p_j must have a y-coordinate greater than the y-coordinates of all preceding intermediate points that are also below Alice. We can track this with a single variable, maxYUnderAlice.

1import java.util.Arrays;2 3class Solution {4    public int numberOfPairs(int[][] points) {5        Arrays.sort(points, (a, b) -> {6            if (a[0] != b[0]) {7                return a[0] - b[0];8            } else {9                return b[1] - a[1];10            }11        });12 13        int n = points.length;14        int count = 0;15 16        for (int i = 0; i < n; i++) {17            int aliceY = points[i][1];18            int maxYUnderAlice = Integer.MIN_VALUE;19            for (int j = i + 1; j < n; j++) {20                int bobY = points[j][1];21                // We only consider points 'below' Alice as potential Bobs or blockers.22                if (bobY <= aliceY) {23                    // A valid Bob must have a y-coordinate greater than any24                    // intermediate point that was also below Alice.25                    if (bobY > maxYUnderAlice) {26                        count++;27                    }28                    // Update the max y-coordinate of points seen so far that are below Alice.29                    maxYUnderAlice = Math.max(maxYUnderAlice, bobY);30                }31            }32        }33 34        return count;35    }36}

Complexity

Time

O(N²). The initial sort takes O(N log N) time. The nested loops contribute O(N²) time, which is the dominant factor.

Space

O(log N) or O(N), depending on the implementation of the sorting algorithm. The rest of the algorithm uses O(1) extra space.

Trade-offs

Pros

Much more efficient with O(N²) time complexity, which is suitable for the given constraints.
The core logic is elegant and avoids complex data structures.

Cons

The logic, especially the sorting criteria and the single-pass check, is less intuitive than the brute-force method.
Requires careful implementation to handle the state (maxYUnderAlice) correctly.

Solutions

Solution

1public class Solution {2    public int NumberOfPairs(int[][] points) {3        Array.Sort(points, (a, b) => a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);4        int ans = 0;5        int n = points.Length;6        int inf = 1 << 30;7        for (int i = 0; i < n; ++i) {8            int y1 = points[i][1];9            int maxY = -inf;10            for (int j = i + 1; j < n; ++j) {11                int y2 = points[j][1];12                if (maxY < y2 && y2 <= y1) {13                    maxY = y2;14                    ++ans;15                }16            }17        }18        return ans;19    }20}

1class Solution {2public3  int numberOfPairs(int[][] points) {4    Arrays.sort(points, (a, b)->a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);5    int ans = 0;6    int n = points.length;7    final int inf = 1 << 30;8    for (int i = 0; i < n; ++i) {9      int y1 = points[i][1];10      int maxY = -inf;11      for (int j = i + 1; j < n; ++j) {12        int y2 = points[j][1];13        if (maxY < y2 && y2 <= y1) {14          maxY = y2;15          ++ans;16        }17      }18    }19    return ans;20  }21}

1class Solution {2public:3  int numberOfPairs(vector<vector<int>> &points) {4    sort(points.begin(), points.end(),5         [](const vector<int> &a, const vector<int> &b) {6           return a[0] < b[0] || (a[0] == b[0] && b[1] < a[1]);7         });8    int n = points.size();9    int ans = 0;10    for (int i = 0; i < n; ++i) {11      int y1 = points[i][1];12      int maxY = INT_MIN;13      for (int j = i + 1; j < n; ++j) {14        int y2 = points[j][1];15        if (maxY < y2 && y2 <= y1) {16          maxY = y2;17          ++ans;18        }19      }20    }21    return ans;22  }23};

1class Solution:2    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

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.

← Previous

Previous problem

Next problem