Find the Number of Ways to Place People II
Source: leetcode
Difficulty: Hard
Tags: array, math, geometry, sorting, enumeration

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.leetcode.com/uploads/2024/01/04/example0alicebob-1.png)
 


**Example 1:**


![](https://assets.leetcode.com/uploads/2024/01/04/example1alicebob.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.leetcode.com/uploads/2024/02/04/example2alicebob.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.leetcode.com/uploads/2024/02/04/example4alicebob.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.




C++ solution:
class Solution {
  struct Point {
    int x, y;
    bool operator < (const Point& other) const 
    {
      if (x < other.x) return true;
      if (x > other.x) return false;
      return y > other.y;
    }

  };
public:
    int numberOfPairs(vector<vector<int>>& points) {
      int n = points.size();
      vector<Point> p(n);
      for (int i=0; i<n; i++) p[i] = Point{points[i][0], points[i][1]};
      sort(p.begin(), p.end());

      int r = 0;
      for (int i=0; i<n-1; i++)
      {
        int ay = p[i].y;
        int y_limit = INT_MIN;        
        for (int j=i+1; j<n; j++)
        {
          int by = p[j].y;
          if (by>ay || by<=y_limit) continue;
          r++;
          y_limit = by;
        }
      }
      return r;        
    }
};

static auto speedUp = []() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 0;
}();

Go solution:
func numberOfPairs(points [][]int) int {
    sort.Slice(points, func(i, j int) bool {
        if points[i][1] > points[j][1] {return true}
        if points[i][1] == points[j][1] {return points[i][0] < points[j][0]}
        return false
    })
    count := 0
    for i := 0; i < len(points); i++ {
        minX := points[i][0]
        maxX := 1_000_000_001
        for j := i + 1; j < len(points); j++ {
            if (points[j][0] >= minX && points[j][0] < maxX) {
                count++
                maxX = points[j][0]
            }
        }
    }
    return count
}

Java solution:
class Solution {
    public int numberOfPairs(int[][] points) {
        //sort points by x (in increasing order)
        // if x coordinate is same, then sort by y (in decreasing order)
        Arrays.sort(points, (x, y) -> {
            if (x[0] == y[0])
                return Integer.compare(y[1], x[1]);
            else
                return Integer.compare(x[0], y[0]);
        });
        
        int result = 0;
        
        for (int c = 0; c < points.length; c++) {
            //coordinates of Chisato
            int cx = points[c][0], cy = points[c][1];
            
            //used to store "y" position of people other than Chisato or Takina
            //in other words, this treeset will store (in increasing order) y coordinate of all those points whos "x" coordinate lies between
            //Chisato and Takina's "x" coordinate
            TreeSet<Integer> set = new TreeSet<>();
            
            for (int t = c + 1; t < points.length; t++) {
                //coordinates of Takina
                int tx = points[t][0], ty = points[t][1];
                
                //Takina doesn't lie on the lower right corner, continue to next point
                if (ty > cy) continue;
                
                //get the lowest person who's "y" cordinate is >= Takina's y coordinate
                Integer mid = set.ceiling(ty);
                
                // the "y" coordinate of lowest person >= Takina's as well as Chisato's "y" coordinate,
                // since this person is lowest, this means that no other person lies such that the "y" coordinate of person
                // lies between Chisato and Takina's "y" coordinate
                // hence count this ractangle in result
                if (mid == null || mid > cy)
                    result++;
                
                // before moving on to next point (and consider that point as Takina's), add current point to the set
                set.add(ty);
            }
        }
        
        return result;
    }
}

JavaScript solution:
/**
 * @param {number[][]} points
 * @return {number}
 */
var numberOfPairs = function(points) {
    points.sort((x,y)=>{
        if (x[1]==y[1]) return y[0] - x[0]
        else return y[1]-x[1]
    })
    var res = 0
    for (const[top_x, top_y] of points){
        var curr = Number.MAX_SAFE_INTEGER 
        var flag = 0
        var i =0
        while (i<points.length){
            const [px,py] = points[i]
            if((top_x==px && top_y==py)|| py>top_y){
                i+=1
                continue}
            else if(px==top_x) {
                flag+=1
                break}
            else if (px>top_x){
                if (py==top_y){
                    curr=Math.min(curr, px)
                    flag = 1   
                }else if (px>=curr){
                    i+=1
                    continue
                }
                else{
                    bb=false
                    while(i+1<points.length && points[i+1][1]==py && points[i+1][0]>=top_x){
                        i+=1
                        curr = Math.min(curr, points[i][0])
                        if (points[i][0]==top_x){
                            flag += 1
                            bb=true}
                    }
                    if (bb==true)break;
                    if (points[i][0]<=curr){
                        res+=1
                        curr = points[i][0]
                    }
                }
            }
            i+=1
        }
        res+=flag
    } 
    return res
};

Python solution:
"""
    - we have points
    - if alice is on point (x, y), then you can find bob's point along the same line.
    - Given bob & alice points, we can check if other points fall inside the rectangle
    - Edge cases:
        - We can have bob exist on the same horizontal or vertical lines too.
        - In this case we have to check whether other points exist on this line

    Brute-force:
        - Find alice and bob candidates O(n^2)
        - Check if each of those candidates are valid with respect to other points
            - For each candidate, you can check in O(n)
            - So if there are O(n^2) candidates, it becomes O(n^3)
    
    Improvement:
        - If you sort by x & store it in one list
        - Check if the indices are consecutive in either x axis or y_axis. => No other points fall in between them = O(1) to check this?
        - then you can add this pair to the list.

    Algo:
        - Sort by x & y to store the two lists = O(nlogn)
        - For each point, check if other points meet the condition = O(n^2)
            - This was missing a case where the points in between were actually not the same.

    Can you do faster than O(n^2)?
"""

def boundary_check(alice, bob):
    if (alice[0] <= bob[0]) and (alice[1] >= bob[1]):
        return True
    return False

class Solution:
    def numberOfPairs(self, points: List[List[int]]) -> int:
        # Sort by x axis
        points = sorted(points, key=lambda x: (x[0], -x[1]))
        count = 0
        for i, (x1, y1) in enumerate(points):
            largest_y = -inf
            for (x2, y2) in points[i + 1:]:
                if (y1 >= y2) and (largest_y < y2):
                    count += 1
                    largest_y = y2
        return count

Ruby solution:
def number_of_pairs(points)
  sorted = points.sort_by { |x, y| [x, -y] }
  count = 0
  n = sorted.size
  (0...n).each do |i|
    alice = sorted[i]
    y_limit = -Float::INFINITY
    (i+1...n).each do |j|
      bob = sorted[j]
      if bob[1] <= alice[1] && bob[1] > y_limit
        count += 1
        y_limit = bob[1]
      end
    end
  end
  count
end