3027. Find the Number of Ways to Place People II
Problem Description
In this problem, we're given a 2D array points
representing coordinates of certain points on a plane. Each point is meant to be occupied by one individual, and there are two particular individuals of interest: Alice and Bob. The task is to figure out how many ways Alice can be positioned at a point that will serve as the upper left corner of a rectangular fence, and Bob can be positioned at a point that will serve as the lower right corner of the same fence, without any other person being inside or on the boundary of this fence.
The essence of this problem revolves around the concept that we can only place Alice and Bob in such a way that Alice is above and to the left of Bob (based on their x and y coordinates). Thus, no individual should have coordinates such that they fall within or on the boundary of the rectangle defined by Alice's and Bob's locations.
To summarize, the challenge is to find all pairs (Alice, Bob)
that allow the fence to be built without enclosing or including any other individuals on its boundary or within its area.
Intuition
Approaching this problem begins with the understanding that if we have Aliceās position fixed as the upper left corner, then Bob must be positioned diagonally across from her at the lower right corner. This means Bobās x-coordinate must be greater than Aliceās x-coordinate, and his y-coordinate must be less than Aliceās y-coordinate, to form a valid rectilinear fence.
The intuition behind the solution hinges on efficiently checking potential Bob
points for every potential Alice
point. We must avoid counting any point that would be inside or on the proposed fence boundary.
Sorting points
by their x-coordinate distinctly helps in the forward search since it naturally orders Bobs to the right of Alice. The y-coordinates are sorted inversely to deal with ensuring that Alice's y-coordinate is more than Bob's. After sorting, iterate through each Alice candidate while keeping track of the maximal y-coordinate observed for Bob that is less than or equal to Aliceās y-coordinateāthe idea being that we don't want any point that sits on or inside the imaginary fence.
For each potential Alice, we search for potential Bobs. If we find a Bob with a y-coordinate less than Alice's but greater than any we've previously encountered, we know we've found a pair that can build a fence without including another individual, so we increment our pairs count. The process is repeated until all viable Alice and Bob pairs are accounted for.
Solution Approach
To implement the solution, the following steps are taken:
-
Sort the Points: Firstly, we sort the
points
array. This is done based on the x-coordinates in ascending order so that potential Bobs are to the right of Alice. For points with the same x-coordinate, we sort based on the y-coordinate in descending order so that potential Alices are above Bobs. This is accomplished with the line:points.sort(key=lambda x: (x[0], -x[1]))
This step is crucial as it aligns all points to a common reference that respects the direction constraints (right and down) mentioned in the problem statement.
-
Initialize Counter: We have an
ans
variable set to 0, which will keep track of the number of valid pairs (Alice, Bob) found. -
Iterate Through Points: We iterate through the sorted
points
list, treating each point as a potential Alice's position. -
Track Maximum y-coordinate: As we iterate through potential Bob positions (to the right of Alice), we maintain a
max_y
variable set to negative infinity to track the highest y-coordinate of points encountered that could serve as a Bob's position and still not invalidate the fence. -
Check and Update Fence Conditions: For each potential Bob, we check if any previous point's y-coordinate (greater than
max_y
but less than or equal to current Alice's y-coordinate) can be used as Bob's position. This is done with the following check:if max_y < y2 <= y1: max_y = y2 ans += 1
This checks whether the current point can be a Bob without any other point on the fence. If it can, we update
max_y
to this new value and incrementans
. -
Return the Count: After iterating over all points, the
ans
value will contain the total number of valid (Alice, Bob) pairs that can be placed such that no other point will be inside or on the fence. This value is returned as the final answer:return ans
Algorithm and Data Structures: The solution employs a simple sorting algorithm along with a linear iteration and tracking of maximum y-values. There was no need for complex data structures as the sorted list itself was sufficient to find all possible pairs.
Patterns Used: What stands out is the use of the two-pointer approach, in a way, where we keep a moving pointer for Alice and another moving pointer for Bob, within the sorted array. This pattern is efficient because it omits the need for nested iterations over the entire set of points for every Alice, reducing the potential time complexity.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use a small example to illustrate the solution approach.
Consider the following points representing coordinates on a plane: points = [[1, 3], [3, 0], [3, 4], [2, 2]]
Following the steps of the solution:
-
Sort the Points: After sorting based on the given key, we have the points array sorted as
[[1, 3], [2, 2], [3, 4], [3, 0]]
. Notice how the points are sorted left to right first, and then for the same x-coordinate, they are sorted from top to bottom. -
Initialize Counter: We set
ans = 0
, ready to count valid pairs. -
Iterate Through Points: We treat each point as potential Alice's position and move from left to right, top to bottom.
-
Track Maximum y-coordinate: We start with
max_y = -inf
as we haven't encountered any Bobs yet. -
Check and Update Fence Conditions:
- Firstly, we consider point
[1, 3]
as a potential Alice. The max_y is still-inf
. - We move to the next point
[2, 2]
. Could this be Bob for Alice[1, 3]
? Yes, becausemax_y < 2 <= 3
, so we updatemax_y = 2
, and incrementans
to 1. - Then, we consider point
[3, 4]
- this cannot be Bob for the current Alice because its y-coordinate is not less than Alice's. - Lastly, we check point
[3, 0]
. This could potentially serve as Bob to Alice[1, 3]
, as it satisfies the conditionmax_y < 0 <= 3
. Therefore, we update themax_y
to 0, and incrementans
to 2.
At this moment, if we try to find a Bob for Alice
[2, 2]
, no point to its right has a lesser y-coordinate. Similarly, points[3, 4]
and[3, 0]
serve as potential Alice positions but have no valid Bobs to the right. - Firstly, we consider point
-
Return the Count: Since we only found valid (Alice, Bob) configurations with the initial Alice
[1, 3]
, the finalans
is 2.
The result tells us there are two distinct ways to position Alice and Bob for the creation of a fence that does not enclose or include others on its boundary. The pairs found were ([1, 3], [3, 0])
and ([1, 3], [2, 2])
.
Solution Implementation
1from math import inf
2
3class Solution:
4 def number_of_pairs(self, points: List[List[int]]) -> int:
5 # Sort the points by their x-coordinate, and then by their y-coordinate in descending order
6 points.sort(key=lambda point: (point[0], -point[1]))
7 ans = 0 # Initialize the number of valid pairs to zero
8
9 # Iterate over each point
10 for i, (_, y1) in enumerate(points):
11 max_y = -inf # Initialize the maximum y-value for the points considered so far
12
13 # Compare with subsequent points to check for pairs
14 for _, y2 in points[i + 1:]:
15 # If the y-value of the current point is greater than max_y
16 # and not greater than y1, this is a valid pair
17 if max_y < y2 <= y1:
18 max_y = y2 # Update max_y to the current y-value
19 ans += 1 # Increment the count of valid pairs
20
21 return ans # Return the total number of valid pairs found
22
1class Solution {
2 public int numberOfPairs(int[][] points) {
3 // Sort the array of points in ascending order by x-coordinates,
4 // and in descending order by y-coordinates if x-coordinates are the same
5 Arrays.sort(points, (point1, point2) -> point1[0] == point2[0] ? point2[1] - point1[1] : point1[0] - point2[0]);
6
7 int count = 0; // Initialize the count of valid pairs
8 int numberOfPoints = points.length; // Total number of points
9 final int INFINITY = 1 << 30; // Representation of negative infinity
10
11 // Iterate over each point to check for valid pairs
12 for (int i = 0; i < numberOfPoints; ++i) {
13 int y1 = points[i][1]; // Get the y-coordinate of the current point
14
15 int maxY = -INFINITY; // Set maxY as negative infinity initially
16
17 // Iterate over the points that come after the current point
18 for (int j = i + 1; j < numberOfPoints; ++j) {
19 int y2 = points[j][1]; // Get the y-coordinate of the next point
20
21 // Check if the current maxY is less than y2 and y2 is less than or equal to y1
22 // If so, this forms a valid pair and update maxY and increment count
23 if (maxY < y2 && y2 <= y1) {
24 maxY = y2; // Update maxY
25 ++count; // Increment the number of valid pairs
26 }
27 }
28 }
29
30 return count; // Return the total number of valid pairs
31 }
32}
33
1#include <vector>
2#include <algorithm> // Include algorithm header for sort
3#include <climits> // Include climits header for INT_MIN
4
5class Solution {
6public:
7 int numberOfPairs(std::vector<std::vector<int>>& points) {
8 // Sort the points in non-decreasing order of their x-values.
9 // In case of a tie, sort by the y-values in decreasing order.
10 std::sort(points.begin(), points.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
11 return a[0] < b[0] || (a[0] == b[0] && b[1] < a[1]);
12 });
13
14 int n = points.size(); // The total number of points
15 int ans = 0; // Initialize the count of pairs
16
17 for (int i = 0; i < n; ++i) {
18 int y1 = points[i][1]; // Get the y-value of the current point
19 int maxY = INT_MIN; // Initialize maxY with the smallest possible integer
20
21 // Iterate through all points that come after the current point
22 for (int j = i + 1; j < n; ++j) {
23 int y2 = points[j][1]; // Get the y-value of the next point
24 // If maxY is less than y2, and y2 is less than or equal to y1,
25 // it means we found a pair where the second point can potentially
26 // form a pair with the first, based on the y-values.
27 if (maxY < y2 && y2 <= y1) {
28 maxY = y2; // Update maxY to the new found y-value
29 ++ans; // Increment the count of pairs
30 }
31 }
32 }
33
34 return ans; // Return the total number of pairs found
35 }
36};
37
1function numberOfPairs(points: number[][]): number {
2 // Sort the points array. First by x-coordinate and then by y-coordinate in descending order if x is the same
3 points.sort((pointA, pointB) => pointA[0] === pointB[0] ? pointB[1] - pointA[1] : pointA[0] - pointB[0]);
4
5 const totalPoints = points.length; // Total number of points
6 let pairCount = 0; // Initialize pairs count
7
8 // Iterate over each point
9 for (let i = 0; i < totalPoints; ++i) {
10 const y1 = points[i][1]; // Get the y-coordinate of the current point
11 let maxY = -Infinity; // Initialize the max Y seen so far for the pairs
12
13 // Iterate over the points after the current one to find pairs
14 for (let j = i + 1; j < totalPoints; ++j) {
15 const y2 = points[j][1]; // Get the y-coordinate of the next point
16
17 // Check if the current y-coordinate is within the required range and update maxY
18 if (maxY < y2 && y2 <= y1) {
19 maxY = y2;
20 ++pairCount; // Increment the count of valid pairs
21 }
22 }
23 }
24
25 return pairCount; // Return the total number of valid pairs found
26}
27
Time and Space Complexity
The time complexity of the code provided is not O(1)
. It first sorts the list, which has O(n log n)
complexity where n
is the length of the points
list. Then it uses a nested loop to iterate through the points
list, leading to a worst-case scenario of O(n^2)
complexity since for each point, it potentially compares it to all other points. Therefore, the overall time complexity is O(n^2)
due to the nested loop after sorting.
The space complexity is O(1)
(ignoring the space taken up by the input and the sort implementation), as the code only uses a fixed amount of additional space ā a few variables like ans
and max_y
, which do not scale with the size of the input.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following problems can be solved with backtracking (select multiple)
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!