3025. Find the Number of Ways to Place People I LeetCode Solution
In this guide, you will get 3025. Find the Number of Ways to Place People I LeetCode Solution with the best time and space complexity. The solution to Find the Number of Ways to Place People I 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 I
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, and
there are no other points in the rectangle (or line) they make (including the border).
The left one is the pair (points[1], points[0]), where points[1] is on the upper left side of points[0] and the rectangle is empty.
The middle one is the pair (points[2], points[1]), same as the left one it is a valid pair.
The right one is the 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.
The left one is the pair (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.
The middle one is the pair (points[1], points[2]), it is a valid pair same as the left one.
The right one is the pair (points[1], points[0]), it is not a valid pair as points[2] is on the border of the rectangle.
Constraints:
2 <= n <= 50
points[i].length == 2
0 <= points[i][0], points[i][1] <= 50
All points[i] are distinct.
Complexity Analysis
Time Complexity: O(n^2)
Space Complexity: O(|\texttt{sort}|)
3025. Find the Number of Ways to Place People I LeetCode Solution in C++
class Solution {
public:
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 */
3025. Find the Number of Ways to Place People I LeetCode Solution in Java
class Solution {
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
3025. Find the Number of Ways to Place People I LeetCode Solution in Python
class Solution:
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
