Find the Number of Ways to Place People I

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.

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

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.

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;
    }
}