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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


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.

Solution

Method 1 – Sort and 2D Binary Indexed Tree (Fenwick Tree)

Intuition

We want to count pairs (A, B) such that A is strictly upper-left of B and there are no other points inside or on the rectangle defined by A and B. By sorting points and using a 2D Fenwick Tree, we can efficiently count the number of valid pairs by processing points in order and querying for emptiness.

Approach

  1. Sort all points by x ascending, then y ascending.
  2. For each point B (in sorted order):
    • For each point A before B, if A.x < B.x and A.y > B.y, check if there are no other points in the rectangle (A.x, B.x) x (B.y, A.y).
    • Use a 2D Fenwick Tree to keep track of points already processed.
    • For each B, query the number of points in the rectangle (A.x+1, B.x-1) x (B.y+1, A.y-1). If zero, count the pair.
  3. Return the total count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    int numberOfPairs(vector<vector<int>>& points) {
        int n = points.size();
        sort(points.begin(), points.end());
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (points[j][0] < points[i][0] && points[j][1] > points[i][1]) {
                    bool ok = true;
                    for (int k = 0; k < n; ++k) {
                        if (k == i || k == j) continue;
                        if (points[j][0] < points[k][0] && points[k][0] < points[i][0] &&
                            points[i][1] < points[k][1] && points[k][1] < points[j][1]) {
                            ok = false;
                            break;
                        }
                    }
                    if (ok) ans++;
                }
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

func numberOfPairs(points [][]int) int {
    n := len(points)
    sort.Slice(points, func(i, j int) bool {
        if points[i][0] == points[j][0] {
            return points[i][1] < points[j][1]
        }
        return points[i][0] < points[j][0]
    })
    ans := 0
    for i := 0; i < n; i++ {
        for j := 0; j < i; j++ {
            if points[j][0] < points[i][0] && points[j][1] > points[i][1] {
                ok := true
                for k := 0; k < n; k++ {
                    if k == i || k == j {
                        continue
                    }
                    if points[j][0] < points[k][0] && points[k][0] < points[i][0] &&
                        points[i][1] < points[k][1] && points[k][1] < points[j][1] {
                        ok = false
                        break
                    }
                }
                if ok {
                    ans++
                }
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public int numberOfPairs(int[][] points) {
        int n = points.length;
        Arrays.sort(points, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (points[j][0] < points[i][0] && points[j][1] > points[i][1]) {
                    boolean ok = true;
                    for (int k = 0; k < n; ++k) {
                        if (k == i || k == j) continue;
                        if (points[j][0] < points[k][0] && points[k][0] < points[i][0] &&
                            points[i][1] < points[k][1] && points[k][1] < points[j][1]) {
                            ok = false;
                            break;
                        }
                    }
                    if (ok) ans++;
                }
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    fun numberOfPairs(points: Array<IntArray>): Int {
        val n = points.size
        points.sortWith(compareBy({ it[0] }, { it[1] }))
        var ans = 0
        for (i in 0 until n) {
            for (j in 0 until i) {
                if (points[j][0] < points[i][0] && points[j][1] > points[i][1]) {
                    var ok = true
                    for (k in 0 until n) {
                        if (k == i || k == j) continue
                        if (points[j][0] < points[k][0] && points[k][0] < points[i][0] &&
                            points[i][1] < points[k][1] && points[k][1] < points[j][1]) {
                            ok = false
                            break
                        }
                    }
                    if (ok) ans++
                }
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def numberOfPairs(self, points: list[list[int]]) -> int:
        n = len(points)
        points.sort()
        ans = 0
        for i in range(n):
            for j in range(i):
                if points[j][0] < points[i][0] and points[j][1] > points[i][1]:
                    ok = True
                    for k in range(n):
                        if k == i or k == j:
                            continue
                        if points[j][0] < points[k][0] < points[i][0] and points[i][1] < points[k][1] < points[j][1]:
                            ok = False
                            break
                    if ok:
                        ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

impl Solution {
    pub fn number_of_pairs(points: Vec<Vec<i32>>) -> i32 {
        let mut pts = points;
        pts.sort();
        let n = pts.len();
        let mut ans = 0;
        for i in 0..n {
            for j in 0..i {
                if pts[j][0] < pts[i][0] && pts[j][1] > pts[i][1] {
                    let mut ok = true;
                    for k in 0..n {
                        if k == i || k == j { continue; }
                        if pts[j][0] < pts[k][0] && pts[k][0] < pts[i][0] &&
                            pts[i][1] < pts[k][1] && pts[k][1] < pts[j][1] {
                            ok = false;
                            break;
                        }
                    }
                    if ok { ans += 1; }
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    numberOfPairs(points: number[][]): number {
        points.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
        const n = points.length;
        let ans = 0;
        for (let i = 0; i < n; ++i) {
            for (let j = 0; j < i; ++j) {
                if (points[j][0] < points[i][0] && points[j][1] > points[i][1]) {
                    let ok = true;
                    for (let k = 0; k < n; ++k) {
                        if (k === i || k === j) continue;
                        if (points[j][0] < points[k][0] && points[k][0] < points[i][0] &&
                            points[i][1] < points[k][1] && points[k][1] < points[j][1]) {
                            ok = false;
                            break;
                        }
                    }
                    if (ok) ans++;
                }
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^3) — For each pair, we may check all other points.
  • 🧺 Space complexity: O(1) — Only a few variables for counting and iteration.