Find the Number of Ways to Place People I
Source: leetcode
Difficulty: Medium
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]`.


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.leetcode.com/uploads/2024/01/04/example1alicebob.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.leetcode.com/uploads/2024/06/25/t2.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.leetcode.com/uploads/2024/06/25/t3.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.




C++ solution:
class Solution {
public:
    static bool comp(vector<int>& a, vector<int>& b) {
        if (a[0] == b[0])
            return a[1] > b[1];
        return a[0] < b[0];
    }

    int numberOfPairs(vector<vector<int>>& points) {
        int n = points.size();
        sort(points.begin(), points.end(), comp);
        
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int x1 = points[i][0], y1 = points[i][1];
            long long k = -10000000000;
            for (int j = i + 1; j < n; j++) {
                int x2 = points[j][0], y2 = points[j][1];
                if (y2 > y1)
                    continue;
                if (y2 > k)
                    ans++;
                if (y2 > k)
                    k = y2;
            }
        }

        return ans;
    }
};

Go solution:
func numberOfPairs(points [][]int) int {
    
    sort.Slice(points, func(i, j int) bool {
        if points[i][1] == points[j][1] {
            return points[i][0] < points[j][0]
        }
        return points[i][1] > points[j][1]
    })
        
    cnt := 0
    
    for i := 0; i < len(points); i++ {
        prevDiff := math.MaxInt
        for j := i + 1; j < len(points); j++ {
            diff := points[j][0] - points[i][0]
            if diff >= 0 && diff < prevDiff {
                prevDiff = diff
                cnt++
            }
        }
    }

    return cnt

}

Java solution:
class Solution {
    public int numberOfPairs(int[][] points) {
        int maxi = 0;
        for(int i=0;i<points.length;i++)
        {
            for(int j=0;j<points.length;j++)
            {
                if(i==j || points[i][0]>points[j][0] || points[i][1]<points[j][1])
                {
                    continue;
                }
                int k = 0;
                for(;k<points.length;k++)
                {
                    if(k==i || k==j)
                    {
                        continue;
                    }
                    if(points[k][1] <= points[i][1] && points[k][1] >= points[j][1] && points[k][0] <= points[j][0] && points[k][0] >= points[i][0]) {
                        break;
                    }
                }
                if(k==points.length)
                {
                    maxi++;
                }
            }
        }
        return maxi;
    }
}

JavaScript solution:
var numberOfPairs = function (ps) {
  ps.sort(([x1, y1], [x2, y2]) => x1 - x2 || y2 - y1);
  let count = 0;
  for (let i = 0; i < ps.length; i++) {
    const [ax, ay] = ps[i];
    let highestYBetweenAandB = -Infinity;
    for (let j = i + 1; j < ps.length; j++) {
      const [bx, by] = ps[j];
      if (ay >= by) {
        if (highestYBetweenAandB < by) {
          count += 1;
          highestYBetweenAandB = by;
        }
      }
    }
  }
  return count;
};

Python solution:
class Solution:
    def numberOfPairs(self, points: List[List[int]]) -> int:
        points.sort(key=lambda x: (x[0], -x[1]))
        l = len(points)

        result = 0
        for i in range(l):
            x, y = points[i]
            b_min = -1
            for j in range(i+1, l):
                b = points[j][1]
                if b_min < b <= y:
                    result += 1
                    b_min = b
        return result

Ruby solution:
def number_of_pairs(points)
    points.sort_by! { |x, y| [x, -y] }
    count = 0
    n = points.size
    (0...n).each do |i|
        x1, y1 = points[i]
        current_max = -Float::INFINITY
        (i+1...n).each do |j|
            x2, y2 = points[j]
            next if y2 > y1
            if y2 > current_max
                count += 1
                current_max = y2
            end
        end
    end
    count
end