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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2 log n), due to sorting, followed by pairwise examination.
Space Complexity: O(1), maintaining fewer intermediate states.
| 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. |
Number of Ways to Rearrange Sticks With K Sticks Visible - Dynamic Programming - Leetcode 1866 • NeetCode • 14,656 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