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 ofpairs 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.

Examples

Example 1

1
2
3
4
5
6


![](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

1
2
3
4
5
6
7
8
9


![](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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


![](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] <= 10^9
  • All points[i] are distinct.

Solution

Method 1 – Brute Force Rectangle Check

Intuition

We need to count all pairs (A, B) such that A is the upper-left and B is the lower-right corner of a rectangle, and no other point lies inside or on the rectangle. For each such pair, we check all other points to ensure the rectangle is empty except for A and B.

Approach

  1. For each pair of points (A, B):
    • A must be strictly upper-left of B: A.x < B.x and A.y > B.y.
  2. For each such pair, check all other points:
    • If any other point lies inside or on the rectangle defined by (A.x, B.x) and (B.y, A.y), skip this pair.
  3. Count all valid pairs.

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
26
27

class Solution {
public:
    int numberOfPairs(vector<vector<int>>& points) {
        int n = points.size();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == j) continue;
                int x1 = points[i][0], y1 = points[i][1];
                int x2 = points[j][0], y2 = points[j][1];
                if (x1 < x2 && y1 > y2) {
                    bool ok = true;
                    for (int k = 0; k < n; ++k) {
                        if (k == i || k == j) continue;
                        int x = points[k][0], y = points[k][1];
                        if (x1 <= x && x <= x2 && y2 <= y && y <= y1) {
                            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

func numberOfPairs(points [][]int) int {
    n := len(points)
    ans := 0
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if i == j {
                continue
            }
            x1, y1 := points[i][0], points[i][1]
            x2, y2 := points[j][0], points[j][1]
            if x1 < x2 && y1 > y2 {
                ok := true
                for k := 0; k < n; k++ {
                    if k == i || k == j {
                        continue
                    }
                    x, y := points[k][0], points[k][1]
                    if x1 <= x && x <= x2 && y2 <= y && y <= y1 {
                        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

class Solution {
    public int numberOfPairs(int[][] points) {
        int n = points.length, ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == j) continue;
                int x1 = points[i][0], y1 = points[i][1];
                int x2 = points[j][0], y2 = points[j][1];
                if (x1 < x2 && y1 > y2) {
                    boolean ok = true;
                    for (int k = 0; k < n; ++k) {
                        if (k == i || k == j) continue;
                        int x = points[k][0], y = points[k][1];
                        if (x1 <= x && x <= x2 && y2 <= y && y <= y1) {
                            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

class Solution {
    fun numberOfPairs(points: Array<IntArray>): Int {
        val n = points.size
        var ans = 0
        for (i in 0 until n) {
            for (j in 0 until n) {
                if (i == j) continue
                val (x1, y1) = points[i]
                val (x2, y2) = points[j]
                if (x1 < x2 && y1 > y2) {
                    var ok = true
                    for (k in 0 until n) {
                        if (k == i || k == j) continue
                        val (x, y) = points[k]
                        if (x1 <= x && x <= x2 && y2 <= y && y <= y1) {
                            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

class Solution:
    def numberOfPairs(self, points: list[list[int]]) -> int:
        n = len(points)
        ans = 0
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                x1, y1 = points[i]
                x2, y2 = points[j]
                if x1 < x2 and y1 > y2:
                    ok = True
                    for k in range(n):
                        if k == i or k == j:
                            continue
                        x, y = points[k]
                        if x1 <= x <= x2 and y2 <= y <= y1:
                            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
26

impl Solution {
    pub fn number_of_pairs(points: Vec<Vec<i32>>) -> i32 {
        let n = points.len();
        let mut ans = 0;
        for i in 0..n {
            for j in 0..n {
                if i == j { continue; }
                let (x1, y1) = (points[i][0], points[i][1]);
                let (x2, y2) = (points[j][0], points[j][1]);
                if x1 < x2 && y1 > y2 {
                    let mut ok = true;
                    for k in 0..n {
                        if k == i || k == j { continue; }
                        let (x, y) = (points[k][0], points[k][1]);
                        if x1 <= x && x <= x2 && y2 <= y && y <= y1 {
                            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
25
26

class Solution {
    numberOfPairs(points: number[][]): number {
        const n = points.length;
        let ans = 0;
        for (let i = 0; i < n; ++i) {
            for (let j = 0; j < n; ++j) {
                if (i === j) continue;
                const [x1, y1] = points[i];
                const [x2, y2] = points[j];
                if (x1 < x2 && y1 > y2) {
                    let ok = true;
                    for (let k = 0; k < n; ++k) {
                        if (k === i || k === j) continue;
                        const [x, y] = points[k];
                        if (x1 <= x && x <= x2 && y2 <= y && y <= y1) {
                            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.