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].
Count the number of pairs of points (A, B), where
A is on the upper left side of B, andReturn the count.
Example 1:
Input: points = [[1,1],[2,2],[3,3]]
Output: 0
Explanation:
There is no way to choose A and B so A is on the upper left side of B.
Example 2:
Input: points = [[6,2],[4,4],[2,6]]
Output: 2
Explanation:
(points[1], points[0]), where points[1] is on the upper left side of points[0] and the rectangle is empty.(points[2], points[1]), same as the left one it is a valid pair.(points[2], points[0]), where points[2] is on the upper left side of points[0], but points[1] is inside the rectangle so it's not a valid pair.Example 3:
Input: points = [[3,1],[1,3],[1,1]]
Output: 2
Explanation:
(points[2], points[0]), where points[2] is on the upper left side of points[0] and there are no other points on the line they form. Note that it is a valid state when the two points form a line.(points[1], points[2]), it is a valid pair same as the left one.(points[1], points[0]), it is not a valid pair as points[2] is on the border of the rectangle.
Constraints:
2 <= n <= 50points[i].length == 20 <= points[i][0], points[i][1] <= 50points[i] are distinct.Problem Overview: You are given coordinates of people on a 2D grid. A valid pair forms a rectangle where one person acts as the top‑left corner and another as the bottom‑right corner. The pair is valid only if no other person lies inside or on the boundary of that rectangle. The task is to count how many such pairs exist.
Approach 1: Naive Brute Force (O(n^3) time, O(1) space)
The direct approach is to enumerate every pair of points (i, j). Treat i as the top‑left candidate and j as the bottom‑right candidate, which requires x_i ≤ x_j and y_i ≥ y_j. For every valid pair, iterate through all remaining points and check whether any point lies inside the rectangle defined by these two corners. If a third point satisfies x_i ≤ x_k ≤ x_j and y_j ≤ y_k ≤ y_i, the pair is invalid. This approach relies purely on enumeration and is useful for understanding the geometric constraint, but the extra scan for each pair leads to O(n^3) time.
Approach 2: Optimized Sorting and Sweep Line Technique (O(n^2) time, O(1) space)
A more efficient strategy avoids repeatedly scanning all points. First sort the points by x ascending and by y descending when x values tie. This ordering allows you to process potential top‑left candidates while sweeping to the right. For each point i, iterate through points j > i. If y_j ≤ y_i, the pair could form a valid rectangle. While scanning, maintain the highest y value encountered that is still below y_i. If y_j is greater than this tracked boundary, the rectangle between i and j remains empty and the pair is counted. This technique relies on ordered traversal using sorting and a geometric sweep similar to a geometry sweep‑line algorithm, reducing redundant interior checks.
Recommended for interviews: Start with the brute force pair enumeration to demonstrate you understand the rectangle constraint. Then move to the sorted sweep approach. Interviewers typically expect the optimized solution because it removes the expensive third loop and uses ordering to implicitly enforce the empty‑rectangle condition.
The simplest approach involves checking every possible pair of points to see if they meet the criteria: one point must be in the 'upper left' of another and no other point should lie within the rectangle they form. This approach leverages nested loops to iterate through the list and check each pair of points.
This solution checks every pair of points to see if one point is to the upper-left of the other. If it is, it validates that no other point lies within the rectangle formed by the two. This is done using nested loops.
Time Complexity: O(n^3) due to the nested loops.
Space Complexity: O(1) as we use constant additional space.
We can optimize the brute force approach by sorting the points and using a sweep line technique. By sorting points either by x or y coordinates, and then processing them in a specific order, we can reduce unnecessary checks. This approach uses a line sweep to maintain set of 'active' points that determine valid pairs as we iterate over the points.
This C implementation leverages the properties of sorted points to reduce checks and focus on possible rectangles dynamically.
Time Complexity: O(n^2 log n), due to sorting, followed by pairwise examination.
Space Complexity: O(1), maintaining fewer intermediate states.
First, we sort the array. Then, we can classify the results based on the properties of a triangle.
The time complexity is O(1), and the space complexity is O(1).
| Approach | Complexity |
|---|---|
| Naive Brute Force | Time Complexity: O(n^3) due to the nested loops. |
| Optimized Sorting and Sweep Line Technique | Time Complexity: O(n^2 log n), due to sorting, followed by pairwise examination. |
| Sorting and Classification | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Brute Force Pair Enumeration | O(n^3) | O(1) | Useful for understanding the geometric constraint and validating logic for small inputs. |
| Sorting + Sweep Line | O(n^2) | O(1) | Preferred approach for interviews and competitive programming. Sorting removes the need to check every interior point. |
Find the Number of Ways to Place People I | 2 Detailed Approaches | Leetcode 3025 | codestorywithMIK • codestorywithMIK • 10,421 views views
Watch 9 more video solutions →Practice Find the Number of Ways to Place People I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor