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].
We define the right direction as positive x-axis (increasing x-coordinate) and the left direction as negative x-axis (decreasing x-coordinate). Similarly, we define the up direction as positive y-axis (increasing y-coordinate) and the down direction as negative y-axis (decreasing y-coordinate)
You have to place n people, including Alice and Bob, at these points such that there is exactly one person at every point. Alice wants to be alone with Bob, so Alice will build a rectangular fence with Alice's position as the upper left corner and Bob's position as the lower right corner of the fence (Note that the fence might not enclose any area, i.e. it can be a line). If any person other than Alice and Bob is either inside the fence or on the fence, Alice will be sad.
Return the number of pairs of points where you can place Alice and Bob, such that Alice does not become sad on building the fence.
Note that Alice can only build a fence with Alice's position as the upper left corner, and Bob's position as the lower right corner. For example, Alice cannot build either of the fences in the picture below with four corners (1, 1), (1, 3), (3, 1), and (3, 3), because:
(3, 3) and Bob at (1, 1), Alice's position is not the upper left corner and Bob's position is not the lower right corner of the fence.(1, 3) and Bob at (1, 1), Bob's position is not the lower right corner of the fence.
Example 1:
Input: points = [[1,1],[2,2],[3,3]] Output: 0 Explanation: There is no way to place Alice and Bob such that Alice can build a fence with Alice's position as the upper left corner and Bob's position as the lower right corner. Hence we return 0.
Example 2:
Input: points = [[6,2],[4,4],[2,6]] Output: 2 Explanation: There are two ways to place Alice and Bob such that Alice will not be sad: - Place Alice at (4, 4) and Bob at (6, 2). - Place Alice at (2, 6) and Bob at (4, 4). You cannot place Alice at (2, 6) and Bob at (6, 2) because the person at (4, 4) will be inside the fence.
Example 3:
Input: points = [[3,1],[1,3],[1,1]] Output: 2 Explanation: There are two ways to place Alice and Bob such that Alice will not be sad: - Place Alice at (1, 1) and Bob at (3, 1). - Place Alice at (1, 3) and Bob at (1, 1). You cannot place Alice at (1, 3) and Bob at (3, 1) because the person at (1, 1) will be on the fence. Note that it does not matter if the fence encloses any area, the first and second fences in the image are valid.
Constraints:
2 <= n <= 1000points[i].length == 2-109 <= points[i][0], points[i][1] <= 109points[i] are distinct.The brute force approach involves checking all possible pairs of points to see if they can form a valid rectangle such that the rectangle does not contain any other points. We define Alice's position as the upper-left corner and Bob's position as the lower-right corner.
For every pair of points, we determine if the current point can serve as Alice's position and the other as Bob's position. We ensure the rectangle formed by these positions doesn't contain any other points.
This C program iteratively selects pairs of points and checks if they can represent valid positions for Alice and Bob. Additional checks are implemented to ensure that no other point falls inside the fenced area. The function finally returns the count of all such valid pairings.
C++
Java
Python
C#
JavaScript
The time complexity is O(n^3) due to the need to check each point for inclusion in the rectangle formed by every pair of selected points. The space complexity is O(1) as no additional space, apart from counters, is used.
In this approach, we improve the performance by means of sorting. By sorting points based on their x and y coordinates, we can reduce the number of pairs we need to check. Specifically, for a given point, we only need to check those points that lie on its 'down-right'.
First, we sort the points based on their X-coordinates. With X being sorted, the position when scanning for 'up-left' and 'down-right' becomes clear. For each point, select pairs only involving those after this point in a sorted state.
This C solution sorts the points, then attempts to check minimal pairs possible by scanning newer positions that fall in the designated quadrant, significantly reducing the evaluations needed by eliminating pre-sorted areas of potential mismatch.
C++
Java
Python
C#
JavaScript
Time complexity reduced to O(n^2 log n). Sorting takes O(n log n), and evaluating pair-specific scenarios occurs in O(n^2). Space remains at O(n) for pointers to store initial references.
| Approach | Complexity |
|---|---|
| Brute Force Approach | The time complexity is O(n^3) due to the need to check each point for inclusion in the rectangle formed by every pair of selected points. The space complexity is O(1) as no additional space, apart from counters, is used. |
| Optimized Approach with Sorting | Time complexity reduced to O(n^2 log n). Sorting takes O(n log n), and evaluating pair-specific scenarios occurs in O(n^2). Space remains at O(n) for pointers to store initial references. |
The unfair way I got good at Leetcode • Dave Burji • 596,394 views views
Watch 9 more video solutions →Practice Find the Number of Ways to Place People II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor