# Find the Number of Ways to Place People I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-number-of-ways-to-place-people-i)
Canonical: https://scaleengineer.com/dsa/problems/find-the-number-of-ways-to-place-people-i
**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]`.

Count the number of pairs of points `(A, B)`, where

* `A` is on the **upper left** side of `B`, and
* there are no other points in the rectangle (or line) they make (**including the border**).

Return the count.

**Example 1:**

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

**Output:** 0

**Explanation:**

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

There is no way to choose `A` and `B` so `A` is on the upper left side of `B`.

**Example 2:**

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

**Output:** 2

**Explanation:**

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

* The left one is the pair `(points[1], points[0])`, where `points[1]` is on the upper left side of `points[0]` and the rectangle is empty.
* The middle one is the pair `(points[2], points[1])`, same as the left one it is a valid pair.
* The right one is the pair `(points[2], points[0])`, where `points[2]` is on the upper left side of `points[0]`, but `points[1]` is inside the rectangle so it's not a valid pair.

**Example 3:**

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

**Output:** 2

**Explanation:**

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

* The left one is the pair `(points[2], points[0])`, where `points[2]` is on the upper left side of `points[0]` and there are no other points on the line they form. Note that it is a valid state when the two points form a line.
* The middle one is the pair `(points[1], points[2])`, it is a valid pair same as the left one.
* The right one is the pair `(points[1], points[0])`, it is not a valid pair as `points[2]` is on the border of the rectangle.

**Constraints:**

* `2 <= n <= 50`
* `points[i].length == 2`
* `0 <= points[i][0], points[i][1] <= 50`
* All `points[i]` are distinct.

# Approaches
## Brute-Force Approach
This approach directly translates the problem statement into code. It iterates through all possible pairs of points (A, B) and for each pair, it first checks if A is to the upper-left of B. If this condition is met, it then performs another iteration through all other points (C) to check if any of them lie inside the rectangle formed by A and B. If no such point C is found, the pair (A, B) is counted.
**Time:** O(n^3), where `n` is the number of points. There are two nested loops to select a pair of points `(A, B)`, and a third nested loop to check for any interfering point `C`. This results in a cubic number of operations. · **Space:** O(1) extra space. The algorithm only requires a few variables for loop counters and the result, not dependent on the input size.
**Pros:** It is straightforward to understand and implement as it directly follows the problem's definition.; It is guaranteed to be correct and works well for the given small constraints (n <= 50).
**Cons:** The O(n^3) time complexity makes it inefficient and potentially too slow if the constraints on `n` were larger.
### Explanation
The brute-force algorithm systematically checks every possible ordered pair of points `(A, B)`. For each pair, it first validates the geometric condition: `A.x <= B.x` and `A.y >= B.y`. If this condition holds, the algorithm proceeds to check for the 'empty rectangle' constraint. It does this by iterating through every other point `C` in the list and checking if `C` lies inside or on the boundary of the rectangle defined by `A` and `B`. A point `C` is inside if `A.x <= C.x <= B.x` and `B.y <= C.y <= A.y`. If any such point `C` is found, the rectangle is not empty, and the pair `(A, B)` is invalid. If the loop over all points `C` completes without finding any interfering point, the pair `(A, B)` is valid, and a counter is incremented. This process is repeated for all pairs to find the total count.

```java
class Solution {
    public int numberOfPairs(int[][] points) {
        int n = points.length;
        int count = 0;
        for (int i = 0; i < n; i++) { // Point A
            for (int j = 0; j < n; j++) { // Point B
                if (i == j) continue;

                int x1 = points[i][0];
                int y1 = points[i][1];
                int x2 = points[j][0];
                int y2 = points[j][1];

                // Check if A is upper-left of B
                if (x1 <= x2 && y1 >= y2) {
                    boolean isRectangleEmpty = true;
                    // Check for any other point C inside the rectangle
                    for (int k = 0; k < n; k++) {
                        if (k == i || k == j) continue;

                        int x3 = points[k][0];
                        int y3 = points[k][1];

                        if (x3 >= x1 && x3 <= x2 && y3 >= y2 && y3 <= y1) {
                            isRectangleEmpty = false;
                            break;
                        }
                    }
                    if (isRectangleEmpty) {
                        count++;
                    }
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Iterate through each point `A` in the `points` array using an index `i`.
- In a nested loop, iterate through each point `B` in the `points` array using an index `j`.
- If `i` and `j` are the same, skip to the next iteration to avoid comparing a point with itself.
- Check if point `A` is on the upper-left side of point `B`. This condition is `points[i][0] <= points[j][0]` and `points[i][1] >= points[j][1]`.
- If the upper-left condition is met, we must check if the rectangle they form is empty. Initialize a boolean flag `is_empty` to `true`.
- Start a third nested loop, iterating through every point `C` with index `k`.
- If `k` is the same as `i` or `j`, skip.
- Check if point `C` lies inside or on the boundary of the rectangle formed by `A` and `B`. The condition is `points[k][0] >= points[i][0]`, `points[k][0] <= points[j][0]`, `points[k][1] >= points[j][1]`, and `points[k][1] <= points[i][1]`.
- If such a point `C` is found, set `is_empty` to `false` and break the innermost loop.
- After checking all points `C`, if `is_empty` is still `true`, it means we found a valid pair. Increment `count`.
- After all loops complete, return the final `count`.

## Optimized Approach with Sorting
This approach significantly improves efficiency by pre-sorting the points. By sorting the points by their x-coordinates (and y-coordinates as a tie-breaker), we can eliminate the third loop used in the brute-force method. For each point `A`, we iterate through subsequent points `B` and can determine in O(1) time if the rectangle `(A, B)` is empty by keeping track of the maximum y-coordinate seen so far.
**Time:** O(n^2). The initial sorting step takes O(n log n) time. The subsequent nested loops run in O(n^2) time. The overall complexity is dominated by the nested loops, resulting in O(n^2). · **Space:** O(log n) or O(n), depending on the space complexity of the sorting algorithm used by the language's standard library. For instance, Java's `Arrays.sort` for primitives uses a Dual-Pivot Quicksort which has an average space complexity of O(log n).
**Pros:** Highly efficient with O(n^2) time complexity, which is optimal for this problem.; Scales well even if constraints were moderately larger.
**Cons:** The logic is more subtle and less direct than the brute-force approach.; Requires a custom sorting comparator, adding a small amount of implementation complexity.
### Explanation
The key to this optimization is sorting. We sort the `points` array first by x-coordinate (ascending) and then by y-coordinate (descending). This ordering ensures that if we pick `A = points[i]` and `B = points[j]` with `i < j`, then `A.x <= B.x` is guaranteed.

The problem then reduces to finding pairs `(A, B)` where `A.y >= B.y`, and there is no intermediate point `C = points[k]` (with `i < k < j`) such that `B.y <= C.y <= A.y`.

We can solve this with a double loop. The outer loop fixes `A = points[i]`. The inner loop iterates through `j` from `i+1` to `n-1`, considering each `B = points[j]` as a potential partner. To efficiently check for an interfering point `C`, we maintain a variable `max_y` which stores the maximum y-coordinate of all points visited so far in the inner loop (`points[i+1]` to `points[j-1]`).

When we consider a new point `B = points[j]`, if `B.y <= A.y` (making it a potential partner) and `B.y > max_y`, it implies that all intermediate points `C` have `C.y <= max_y < B.y`. Therefore, no `C` can satisfy `C.y >= B.y`, meaning the rectangle is empty and the pair `(A, B)` is valid. We then update `max_y` with `B.y` for the next iteration.

```java
import java.util.Arrays;

class Solution {
    public int numberOfPairs(int[][] points) {
        int n = points.length;
        Arrays.sort(points, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);

        int count = 0;
        for (int i = 0; i < n; i++) {
            int y1 = points[i][1];
            int maxY = -1; // Max y seen for k between i and j

            for (int j = i + 1; j < n; j++) {
                int y2 = points[j][1];

                // A = points[i], B = points[j]
                // A is upper-left of B if y1 >= y2 (since x1 <= x2 is guaranteed by sort)
                // Rectangle is empty if no C=points[k] (i<k<j) has y2 <= C.y <= y1
                // maxY stores max(points[k].y) for k in (i+1, j).
                // If y2 > maxY, then for all k in (i+1,j), points[k].y <= maxY < y2.
                // So no intermediate point can be >= y2. The condition is met.
                if (y2 <= y1) {
                    if (y2 > maxY) {
                        count++;
                    }
                }
                // Update maxY with the y-coordinate of the current point B (which is points[j])
                // because it can act as an interfering point for subsequent points in the inner loop.
                maxY = Math.max(maxY, y2);
            }
        }
        return count;
    }
}
```
### Algorithm
- Sort the `points` array. The primary sorting key is the x-coordinate in ascending order. The secondary key is the y-coordinate in descending order.
- Initialize a counter `count` to 0.
- Iterate through the sorted points with an outer loop for `i` from `0` to `n-1`. Let `A = points[i]`.
- Inside this loop, initialize a variable `max_y = -1`. This will track the maximum y-coordinate of points encountered so far in the inner loop.
- Start an inner loop for `j` from `i+1` to `n-1`. Let `B = points[j]`.
- Due to sorting, `A.x <= B.x` is always true. We check if `B.y <= A.y` to see if `A` is upper-left of `B`.
- If `B.y <= A.y`, we then check if `B.y > max_y`. If this is true, it means no intermediate point `C = points[k]` (with `i < k < j`) can block the view from `A` to `B`, because all their y-coordinates are less than or equal to `max_y`, which is less than `B.y`. Thus, the pair `(A, B)` is valid, and we increment `count`.
- In every iteration of the inner loop, update `max_y = max(max_y, B.y)`. This is because the current point `B` can act as an interfering point for subsequent pairs.
- After the loops complete, return `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
```