# Find the Number of Ways to Place People II
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-the-number-of-ways-to-place-people-ii)
Canonical: https://scaleengineer.com/dsa/problems/find-the-number-of-ways-to-place-people-ii
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Geometry](https://scaleengineer.com/dsa/patterns/geometry), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
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.
![](https://assets.glich.co/dsa/find-the-number-of-ways-to-place-people-ii/image0.png) 

**Example 1:**

![](https://assets.glich.co/dsa/find-the-number-of-ways-to-place-people-ii/image1.png) 

**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:**

![](https://assets.glich.co/dsa/find-the-number-of-ways-to-place-people-ii/image2.png) 

**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:**

![](https://assets.glich.co/dsa/find-the-number-of-ways-to-place-people-ii/image3.png) 

**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`
* `-109 <= points[i][0], points[i][1] <= 109`
* All `points[i]` are distinct.

# Approaches
## Brute-Force Approach
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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`.

## Optimized Approach with Sorting
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.
**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.
**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.
### Explanation
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`.

```java
import java.util.Arrays;

class Solution {
    public int numberOfPairs(int[][] points) {
        Arrays.sort(points, (a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            } else {
                return b[1] - a[1];
            }
        });

        int n = points.length;
        int count = 0;

        for (int i = 0; i < n; i++) {
            int aliceY = points[i][1];
            int maxYUnderAlice = Integer.MIN_VALUE;
            for (int j = i + 1; j < n; j++) {
                int bobY = points[j][1];
                // We only consider points 'below' Alice as potential Bobs or blockers.
                if (bobY <= aliceY) {
                    // A valid Bob must have a y-coordinate greater than any
                    // intermediate point that was also below Alice.
                    if (bobY > maxYUnderAlice) {
                        count++;
                    }
                    // Update the max y-coordinate of points seen so far that are below Alice.
                    maxYUnderAlice = Math.max(maxYUnderAlice, bobY);
                }
            }
        }

        return count;
    }
}
```
### 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`.

# Solutions
### CSharp

```csharp
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;
    }
}
```

### Java

```java
class Solution {
public
  int numberOfPairs(int[][] points) {
    Arrays.sort(points, (a, b)->a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
    int ans = 0;
    int n = points.length;
    final 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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numberOfPairs(vector<vector<int>> &points) {
    sort(points.begin(), points.end(),
         [](const vector<int> &a, const vector<int> &b) {
           return a[0] < b[0] || (a[0] == b[0] && b[1] < a[1]);
         });
    int n = points.size();
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      int y1 = points[i][1];
      int maxY = INT_MIN;
      for (int j = i + 1; j < n; ++j) {
        int y2 = points[j][1];
        if (maxY < y2 && y2 <= y1) {
          maxY = y2;
          ++ans;
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
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

```