Problem Description
You are given an array of 2D points. A pair of distinct points (A, B) is considered valid if:
- A is on the “upper left” of B. In other words, A.x ≤ B.x and A.y ≥ B.y.
- The axis-aligned rectangle (or line) defined by the two points (with A and B as opposite corners) contains no other points (including on its border).
Return the total count of such valid pairs.
Key Insights
- Since the number of points is small (n ≤ 50), a brute-force check on every pair is acceptable.
- For each candidate pair (A, B) satisfying the upper left condition, check every other point to ensure it does not lie within or on the boundary of the rectangle defined by A and B.
- Handle degenerate cases: the rectangle might collapse to a line (horizontal or vertical). These are considered valid if no extra point exists on that line segment.
- Use nested loops to iterate over pairs and a further loop to validate emptiness of the rectangle.
Space and Time Complexity
Time Complexity: O(n^3) in the worst case because for each candidate pair (n^2) we scan all n points. Space Complexity: O(1) extra space beyond the input data.
Solution
We iterate over each ordered pair of points (A, B). First, we check if A satisfies the upper left condition relative to B (A.x ≤ B.x and A.y ≥ B.y). Then, we define the rectangle with boundaries [A.x, B.x] and [B.y, A.y]. For each other point, we check if its x-coordinate is between A.x and B.x (inclusive) and its y-coordinate is between B.y and A.y (inclusive). If any such point exists (and it is not A or B), the pair is disqualified. Otherwise, we count it as a valid pair.
We use simple loops since the constraints (n ≤ 50) allow an O(n^3) solution. The main trick is correctly handling the boundaries and ensuring that only the given pair’s endpoints are allowed inside the rectangle.