Find the Number of Ways to Place People I

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

1class Solution {2    public int numberOfPairs(int[][] points) {3        int n = points.length;4        int count = 0;5        for (int i = 0; i < n; i++) { // Point A6            for (int j = 0; j < n; j++) { // Point B7                if (i == j) continue;8 9                int x1 = points[i][0];10                int y1 = points[i][1];11                int x2 = points[j][0];12                int y2 = points[j][1];13 14                // Check if A is upper-left of B15                if (x1 <= x2 && y1 >= y2) {16                    boolean isRectangleEmpty = true;17                    // Check for any other point C inside the rectangle18                    for (int k = 0; k < n; k++) {19                        if (k == i || k == j) continue;20 21                        int x3 = points[k][0];22                        int y3 = points[k][1];23 24                        if (x3 >= x1 && x3 <= x2 && y3 >= y2 && y3 <= y1) {25                            isRectangleEmpty = false;26                            break;27                        }28                    }29                    if (isRectangleEmpty) {30                        count++;31                    }32                }33            }34        }35        return count;36    }37}

• Sort the points array. The primary sorting key is the x-coordinate in ascending order. The secondary key is the y-coordinate in descending order.
• Initialize a counter count to 0.
• Iterate through the sorted points with an outer loop for i from 0 to n-1. Let A = points[i].
• Inside this loop, initialize a variable max_y = -1. This will track the maximum y-coordinate of points encountered so far in the inner loop.
• Start an inner loop for j from i+1 to n-1. Let B = points[j].
• Due to sorting, A.x <= B.x is always true. We check if B.y <= A.y to see if A is upper-left of B.
• If B.y <= A.y, we then check if B.y > max_y. If this is true, it means no intermediate point C = points[k] (with i < k < j) can block the view from A to B, because all their y-coordinates are less than or equal to max_y, which is less than B.y. Thus, the pair (A, B) is valid, and we increment count.
• In every iteration of the inner loop, update max_y = max(max_y, B.y). This is because the current point B can act as an interfering point for subsequent pairs.
• After the loops complete, return count.

The key to this optimization is sorting. We sort the points array first by x-coordinate (ascending) and then by y-coordinate (descending). This ordering ensures that if we pick A = points[i] and B = points[j] with i < j, then A.x <= B.x is guaranteed.

The problem then reduces to finding pairs (A, B) where A.y >= B.y, and there is no intermediate point C = points[k] (with i < k < j) such that B.y <= C.y <= A.y.

We can solve this with a double loop. The outer loop fixes A = points[i]. The inner loop iterates through j from i+1 to n-1, considering each B = points[j] as a potential partner. To efficiently check for an interfering point C, we maintain a variable max_y which stores the maximum y-coordinate of all points visited so far in the inner loop (points[i+1] to points[j-1]).

When we consider a new point B = points[j], if B.y <= A.y (making it a potential partner) and B.y > max_y, it implies that all intermediate points C have C.y <= max_y < B.y. Therefore, no C can satisfy C.y >= B.y, meaning the rectangle is empty and the pair (A, B) is valid. We then update max_y with B.y for the next iteration.

1import java.util.Arrays;2 3class Solution {4    public int numberOfPairs(int[][] points) {5        int n = points.length;6        Arrays.sort(points, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);7 8        int count = 0;9        for (int i = 0; i < n; i++) {10            int y1 = points[i][1];11            int maxY = -1; // Max y seen for k between i and j12 13            for (int j = i + 1; j < n; j++) {14                int y2 = points[j][1];15 16                // A = points[i], B = points[j]17                // A is upper-left of B if y1 >= y2 (since x1 <= x2 is guaranteed by sort)18                // Rectangle is empty if no C=points[k] (i<k<j) has y2 <= C.y <= y119                // maxY stores max(points[k].y) for k in (i+1, j).20                // If y2 > maxY, then for all k in (i+1,j), points[k].y <= maxY < y2.21                // So no intermediate point can be >= y2. The condition is met.22                if (y2 <= y1) {23                    if (y2 > maxY) {24                        count++;25                    }26                }27                // Update maxY with the y-coordinate of the current point B (which is points[j])28                // because it can act as an interfering point for subsequent points in the inner loop.29                maxY = Math.max(maxY, y2);30            }31        }32        return count;33    }34}