3027. Find the Number of Ways to Place People II LeetCode Solution
In this guide, you will get 3027. Find the Number of Ways to Place People II LeetCode Solution with the best time and space complexity. The solution to Find the Number of Ways to Place People II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find the Number of Ways to Place People II
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:
With Alice at (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.
With Alice at (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.
2 <= n <= 1000
points[i].length == 2
-109 <= points[i][0], points[i][1] <= 109
All points[i] are distinct.
Complexity Analysis
Time Complexity: O(n^2)
Space Complexity: O(|\texttt{sort}|)
3027. Find the Number of Ways to Place People II LeetCode Solution in C++
class Solution {
public:
// Same as 3025. Find the Number of Ways to Place People I
int numberOfPairs(vector<vector<int>>& points) {
int ans = 0;
ranges::sort(points, [](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);
});
for (int i = 0; i < points.size(); ++i) {
int maxY = INT_MIN;
for (int j = i + 1; j < points.size(); ++j)
if (points[i][1] >= points[j][1] && points[j][1] > maxY) {
++ans;
maxY = points[j][1];
}
}
return ans;
}
}; /* code provided by PROGIEZ */
3027. Find the Number of Ways to Place People II LeetCode Solution in Java
class Solution {
// Same as 3025. Find the Number of Ways to Place People I
public int numberOfPairs(int[][] points) {
int ans = 0;
Arrays.sort(points,
(a, b) -> a[0] == b[0] ? Integer.compare(b[1], a[1]) : Integer.compare(a[0], b[0]));
for (int i = 0; i < points.length; ++i) {
int maxY = Integer.MIN_VALUE;
for (int j = i + 1; j < points.length; ++j)
if (points[i][1] >= points[j][1] && points[j][1] > maxY) {
++ans;
maxY = points[j][1];
}
}
return ans;
}
} // code provided by PROGIEZ
3027. Find the Number of Ways to Place People II LeetCode Solution in Python
class Solution:
# Same as 3025. Find the Number of Ways to Place People I
def numberOfPairs(self, points: list[list[int]]) -> int:
ans = 0
points.sort(key=lambda x: (x[0], -x[1]))
for i, (_, yi) in enumerate(points):
maxY = -math.inf
for j in range(i + 1, len(points)):
_, yj = points[j]
# Chisato is in the upper-left corner at (xi, yi), and Takina is in the
# lower-right corner at (xj, yj). Also, if yj > maxY, it means that
# nobody other than Chisato and Takina is inside or on the fence.
if yi >= yj > maxY:
ans += 1
maxY = yj
return ans # code by PROGIEZ
