Problem Description

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

The task is to count the number of valid pairs of points (A, B) that satisfy two conditions:

1. Point A is on the upper left side of point B. This means:

   • The x-coordinate of A is less than or equal to the x-coordinate of B (A.x <= B.x)
   • The y-coordinate of A is greater than or equal to the y-coordinate of B (A.y >= B.y)

2. There are no other points inside or on the boundary of the rectangle formed by points A and B. The rectangle has A as the upper-left corner and B as the lower-right corner.

For example, if A = (1, 3) and B = (4, 1), they form a rectangle with corners at (1, 3), (4, 3), (1, 1), and (4, 1). For this pair to be valid, no other points from the array should lie within this rectangular region or on its edges.

Return the total count of such valid pairs.

Intuition

To find valid pairs efficiently, we need to avoid checking every possible pair against all other points, which would be too slow. The key insight is to process points in a specific order that allows us to eliminate invalid pairs quickly.

If we sort the points by x-coordinate (ascending) and then by y-coordinate (descending for same x), we create an ordering where potential point A candidates come before their corresponding point B candidates. This sorting strategy (x, -y) ensures that when we fix a point as A, all points that could potentially be B (having x >= A.x) come after it in the sorted array.

For each point acting as A, we iterate through subsequent points as potential B candidates. Since B must be to the lower-right of A, we need B.y <= A.y. But here's the clever part: we don't need to check all other points for the "no points in rectangle" condition individually.

Instead, we maintain a max_y variable that tracks the highest y-coordinate we've seen so far among valid B points. When we encounter a new potential B, if its y-coordinate is higher than max_y but still not exceeding A.y, then we know there are no interfering points in the rectangle formed by A and this new B. This is because:

1. Any point with a higher y-coordinate than B.y would need to be checked, but if B.y > max_y, we haven't seen any such interfering point yet
2. Points with lower y-coordinates than max_y don't matter because they would be outside or below the rectangle

By updating max_y each time we find a valid pair, we effectively track a "barrier" that helps us quickly determine if future points form valid pairs with the current A.

Learn more about Math and Sorting patterns.

Solution Approach

The implementation follows a systematic approach using sorting and efficient pair validation:

Step 1: Sort the points

points.sort(key=lambda x: (x[0], -x[1]))

We sort points by x-coordinate in ascending order, and for points with the same x-coordinate, by y-coordinate in descending order. This ordering ensures that when we fix a point as A, all potential B points (with x >= A.x) appear later in the sorted array.

Step 2: Iterate through each point as potential point A

for i, (_, y1) in enumerate(points):

We iterate through each point in the sorted array, treating it as the upper-left point A. We only need the y-coordinate (y1) since the x-coordinate ordering is already handled by the sort.

Step 3: Track the maximum y-coordinate barrier

max_y = -inf

For each point A, we initialize max_y to negative infinity. This variable tracks the highest y-coordinate among all valid B points we've found so far for the current A.

Step 4: Check subsequent points as potential point B

for _, y2 in points[i + 1 :]:
    if max_y < y2 <= y1:
        max_y = y2
        ans += 1

For each subsequent point in the array (guaranteed to have x >= A.x due to sorting), we check if it can form a valid pair with A:

• y2 <= y1: Ensures point B is not above point A
• max_y < y2: Ensures no previously seen point would be inside the rectangle

If both conditions are met, we've found a valid pair. We update max_y to y2 and increment our answer counter.

The key efficiency comes from the max_y tracking mechanism. Once a point with y-coordinate y2 becomes a valid B, any future point with y-coordinate less than or equal to y2 cannot form a valid pair with the current A because the point at y2 would be inside their rectangle. This eliminates the need to check all other points for each potential pair.

Time Complexity: O(n^2) where n is the number of points - we have nested loops but each inner operation is O(1).

Space Complexity: O(1) excluding the space used for sorting.

Example Walkthrough

Let's walk through the solution with a concrete example to understand how the algorithm works.

Given points: [[1,1], [2,2], [3,3]]

Step 1: Sort the points After sorting by (x, -y): [[1,1], [2,2], [3,3]] (In this case, the order remains the same since x-coordinates are all different and already in ascending order)

Step 2: Process each point as potential point A

Iteration 1: A = [1,1] (index 0)

• Initialize max_y = -inf
• Check subsequent points as B:
  • B = [2,2] (index 1):
    • Is max_y < 2 <= 1? No, because 2 > 1 (B.y must be ≤ A.y)
    • Not a valid pair
  • B = [3,3] (index 2):
    • Is max_y < 3 <= 1? No, because 3 > 1
    • Not a valid pair
• Valid pairs found: 0

Iteration 2: A = [2,2] (index 1)

• Initialize max_y = -inf
• Check subsequent points as B:
  • B = [3,3] (index 2):
    • Is max_y < 3 <= 2? No, because 3 > 2
    • Not a valid pair
• Valid pairs found: 0

Iteration 3: A = [3,3] (index 2)

• No subsequent points to check
• Valid pairs found: 0

Total valid pairs: 0

Let's try another example with more interesting geometry:

Given points: [[1,3], [2,1], [3,2], [4,0]]

Step 1: Sort the points After sorting by (x, -y): [[1,3], [2,1], [3,2], [4,0]]

Step 2: Process each point as potential point A

Iteration 1: A = [1,3] (index 0)

• Initialize max_y = -inf
• Check subsequent points as B:
  • B = [2,1]: Is -inf < 1 <= 3? Yes!
    • Valid pair: ([1,3], [2,1])
    • Update max_y = 1, count = 1
  • B = [3,2]: Is 1 < 2 <= 3? Yes!
    • Valid pair: ([1,3], [3,2])
    • Update max_y = 2, count = 2
  • B = [4,0]: Is 2 < 0 <= 3? No, because 0 < 2
    • Not valid (point [3,2] would be inside the rectangle)

Iteration 2: A = [2,1] (index 1)

• Initialize max_y = -inf
• Check subsequent points as B:
  • B = [3,2]: Is -inf < 2 <= 1? No, because 2 > 1
  • B = [4,0]: Is -inf < 0 <= 1? Yes!
    • Valid pair: ([2,1], [4,0])
    • Update max_y = 0, count = 3

Iteration 3: A = [3,2] (index 2)

• Initialize max_y = -inf
• Check subsequent points as B:
  • B = [4,0]: Is -inf < 0 <= 2? Yes!
    • Valid pair: ([3,2], [4,0])
    • Update max_y = 0, count = 4

Total valid pairs: 4

The key insight illustrated here is how max_y acts as a barrier. For example, when A = [1,3] and we've already paired it with B = [3,2], the max_y = 2 prevents [4,0] from being a valid pair because the point [3,2] would lie inside the rectangle formed by [1,3] and [4,0].

Solution Implementation

Time and Space Complexity

The time complexity of this code is O(n^2) where n is the number of points. This is because:

• The sorting operation takes O(n log n) time
• The nested loops iterate through all pairs where i < j, resulting in approximately n * (n-1) / 2 iterations, which is O(n^2)
• Since O(n^2) dominates O(n log n), the overall time complexity is O(n^2)

The space complexity is O(1) if we don't count the space used by the sorting algorithm (which could be O(log n) for the recursive call stack in typical implementations). The algorithm only uses a constant amount of extra space for variables ans, max_y, i, y1, and y2, regardless of the input size.

Note: The reference answer stating O(1) for time complexity appears to be incorrect, as the algorithm clearly has nested loops that depend on the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Understanding of "Upper Left" Relationship

The Problem: A common mistake is misunderstanding what "upper left" means in a coordinate system. In standard 2D plane coordinates, y-values increase upward, so "upper left" means the point has a smaller x-coordinate AND a larger y-coordinate. Some developers might incorrectly assume "upper" means smaller y-values (thinking in terms of screen coordinates where y increases downward).

Example of Incorrect Logic:

# WRONG: Treating smaller y as "upper"
if x1 <= x2 and y1 <= y2:  # This is incorrect!
    # Process as valid upper-left relationship

Solution:

# CORRECT: Larger y is "upper" in standard coordinates
if x1 <= x2 and y1 >= y2:  # Point A has larger or equal y-coordinate
    # Process as valid upper-left relationship

Pitfall 2: Not Handling the Blocking Points Correctly

The Problem: When checking if a rectangle is empty, developers often forget that once a point B is found to be valid for point A, it creates a "barrier" - any subsequent point with a y-coordinate less than or equal to B's y-coordinate cannot form a valid pair with A because B would be inside their rectangle.

Example of Incorrect Logic:

# WRONG: Checking all other points for each pair independently
for i in range(n):
    for j in range(i + 1, n):
        if is_upper_left(points[i], points[j]):
            valid = True
            for k in range(n):
                if k != i and k != j:
                    if point_in_rectangle(points[k], points[i], points[j]):
                        valid = False
                        break
            if valid:
                count += 1

This approach has O(n³) complexity and redundantly checks conditions.

Solution: Use the max_y tracking mechanism as shown in the original solution. Once we find a valid B point, we know that any point with y ≤ B.y cannot form a valid pair with the current A:

# CORRECT: Track maximum y to avoid redundant checks
max_y_seen = -inf
for x2, y2 in points[i + 1:]:
    if max_y_seen < y2 <= y1:  # Only check if y2 is above our barrier
        max_y_seen = y2
        pair_count += 1

Pitfall 3: Incorrect Sorting Strategy

The Problem: Using the wrong sorting order can make the algorithm incorrect or inefficient. A common mistake is sorting only by x-coordinate without considering y-coordinates for ties.

Example of Incorrect Logic:

# WRONG: Only sorting by x-coordinate
points.sort(key=lambda p: p[0])

This fails when multiple points share the same x-coordinate. Without proper y-ordering, we might miss valid pairs or count invalid ones.

Solution: Sort by x-coordinate ascending, then by y-coordinate descending for ties:

# CORRECT: Sort by x ascending, then y descending
points.sort(key=lambda p: (p[0], -p[1]))

This ensures that for points with the same x-coordinate, those with higher y-values come first, maintaining the correct processing order for the upper-left relationship.