Find the Number of Ways to Place People II solution and explanation
Google
9 more videos on this problem
Find the Number of Ways to Place People II | Same as Part I | Leetcode 3027 | codestorywithMIKcodestorywithMIK · 7:09 · 4K views
3027. Find the Number of Ways to Place People II | Sorting | Geometry | Biweekly Contest 123Aryan Mittal · 36:39 · 3K views
Find the Number of Ways to Place People II | Leetcode 3027Techdose · 29:18 · 1K views
3027. Find the Number of Ways to Place People II | Leetcode Biweekly 123codingMohan · 32:45 · 559 views
Daily Leetcode #1982: Sep 03, 2025 - 3027. Find the Number of Ways to Place People IIProgramming Live with Larry · 33:59 · 438 views
3027. Find the Number of Ways to Place People II | Leetcode Daily - PythonLeetcode Daily · 5:44 · 350 views
3027. Find the Number of Ways to Place People II (Leetcode Hard)Programming Live with Larry · 27:51 · 287 views
Find the Number of Ways to Place People II | LeetCode 3027 - Pythonimpoldev · 11:47 · 225 views
Find the Number of Ways to Place People II | LeetCode 3027 | Not a Hard problemSanyam IIT Guwahati · 11:34 · 192 views
Find the Number of Ways to Place People II | LeetCode 3027 | Java Code | Developer CoderDeveloper Coder · 24:58 · 192 views
The problem
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.
Constraints:
2 <= n <= 1000points[i].length == 2-109 <= points[i][0], points[i][1] <= 109- All
points[i]are distinct.
Approach overview
Problem Overview: You are given coordinates of people on a 2D grid. Count how many ordered pairs can form the top-left and bottom-right corners of a rectangle such that no other person lies inside or on the boundary of that rectangle. The task is essentially checking geometric relationships between pairs of points while ensuring the rectangle they form is empty.
Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)
The most direct approach checks every pair of people as potential rectangle corners. For each pair (i, j), first verify that the coordinates form a valid top-left and bottom-right relationship: x[i] ≤ x[j] and y[i] ≥ y[j]. If the pair qualifies, iterate through all other points and check whether any point lies inside or on the rectangle defined by those two corners. If no such point exists, the pair contributes one valid configuration.
This method relies purely on enumeration using basic array iteration and simple geometry checks. While easy to reason about, it performs three nested scans and becomes slow when the number of points grows.
Approach 2: Optimized with Sorting and Sweep (O(n^2) time, O(1) space)
A key observation eliminates the need to check every interior point explicitly. Sort all coordinates by x in ascending order, and for ties sort by y in descending order. Fix a person i as the potential top-left corner, then scan candidates j > i as bottom-right corners.
During this scan maintain a variable maxY representing the highest y value encountered so far that is still below or equal to y[i]. When visiting a new point j, it forms a valid pair only if y[j] ≤ y[i] and y[j] > maxY. The first condition ensures the rectangle orientation is correct. The second guarantees no previously processed point lies inside the rectangle. Once counted, update maxY to y[j].
This works because sorting by x ensures every candidate lies to the right of i. Tracking the highest blocking y prevents counting rectangles that would contain another person. The approach combines sorting with controlled enumeration to remove the inner validation loop.
Recommended for interviews: Interviewers usually expect the sorted sweep approach. Starting with the brute force solution shows you understand the geometric constraints, but recognizing that sorting by x and tracking the next valid y eliminates the third loop demonstrates stronger algorithmic reasoning.
Approach 1: Brute Force Approach
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.
def number_of_ways(points):
n = len(points)
count = 0
for i in range(n):
for j in range(n):
if points[i][0] < points[j][0] and points[i][1] > points[j][1]:
valid = True
for k in range(n):
if k != i and k != j and \
points[k][0] >= points[i][0] and points[k][0] <= points[j][0] and \
points[k][1] <= points[i][1] and points[k][1] >= points[j][1]:
valid = False
break
if valid:
count += 1
return count
points = [[6, 2], [4, 4], [2, 6]]
print(number_of_ways(points))import java.util.ArrayList;
import java.util.List;
public class AliceBobFence {
public static int numberOfWays(int[][] points) {
int n = points.length;
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (points[i][0] < points[j][0] && points[i][1] > points[j][1]) {
boolean valid = true;
for (int k = 0; k < n; k++) {
if (k != i && k != j &&
points[k][0] >= points[i][0] && points[k][0] <= points[j][0] &&
points[k][1] <= points[i][1] && points[k][1] >= points[j][1]) {
valid = false;
break;
}
}
if (valid) count++;
}
}
}
return count;
}
public static void main(String[] args) {
int[][] points = {{6, 2}, {4, 4}, {2, 6}};
System.out.println(numberOfWays(points));
}
}#include <iostream>
#include <vector>
int numberOfWays(std::vector<std::vector<int>>& points) {
int n = points.size();
int count = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (points[i][0] < points[j][0] && points[i][1] > points[j][1]) {
bool valid = true;
for (int k = 0; k < n; ++k) {
if (k != i && k != j &&
points[k][0] >= points[i][0] && points[k][0] <= points[j][0] &&
points[k][1] <= points[i][1] && points[k][1] >= points[j][1]) {
valid = false;
break;
}
}
if (valid) count++;
}
}
}
return count;
}
int main() {
std::vector<std::vector<int>> points = {{6, 2}, {4, 4}, {2, 6}};
std::cout << numberOfWays(points) << std::endl;
return 0;
}function numberOfWays(points) {
let count = 0;
const n = points.length;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (points[i][0] < points[j][0] && points[i][1] > points[j][1]) {
let valid = true;
for (let k = 0; k < n; k++) {
if (k !== i && k !== j &&
points[k][0] >= points[i][0] && points[k][0] <= points[j][0] &&
points[k][1] <= points[i][1] && points[k][1] >= points[j][1]) {
valid = false;
break;
}
}
if (valid) {
count++;
}
}
}
}
return count;
}
const points = [[6, 2], [4, 4], [2, 6]];
console.log(numberOfWays(points));#include <stdio.h>
int numberOfWays(int points[][2], int n) {
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (points[i][0] < points[j][0] && points[i][1] > points[j][1]) {
int valid = 1;
for (int k = 0; k < n; k++) {
if (k != i && k != j &&
points[k][0] >= points[i][0] && points[k][0] <= points[j][0] &&
points[k][1] <= points[i][1] && points[k][1] >= points[j][1]) {
valid = 0;
break;
}
}
if (valid) count++;
}
}
}
return count;
}
int main() {
int points[3][2] = {{6, 2}, {4, 4}, {2, 6}};
printf("%d\n", numberOfWays(points, 3));
return 0;
}using System;
using System.Collections.Generic;
class Program {
static int NumberOfWays(int[][] points) {
int n = points.Length;
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (points[i][0] < points[j][0] && points[i][1] > points[j][1]) {
bool valid = true;
for (int k = 0; k < n; k++) {
if (k != i && k != j &&
points[k][0] >= points[i][0] && points[k][0] <= points[j][0] &&
points[k][1] <= points[i][1] && points[k][1] >= points[j][1]) {
valid = false;
break;
}
}
if (valid) count++;
}
}
}
return count;
}
static void Main() {
int[][] points = { new int[] { 6, 2 }, new int[] { 4, 4 }, new int[] { 2, 6 } };
Console.WriteLine(NumberOfWays(points));
}
}The Python implementation iterates over pairs of points, checking that they can form upper-left and lower-right corners of a rectangle without enclosing other points. The function finally returns a count of valid solutions.
The complexity is O(n^3) due to the triple nested loops making evaluations on each point's involvement for every pair. Space complexity is O(1) as no extra structures are retained.
Approach 2: Optimized Approach with Sorting
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.
def number_of_ways(points):
points.sort()
n = len(points)
count = 0
for i in range(n):
for j in range(i+1, n):
if points[i][1] > points[j][1]:
valid = True
for k in range(i+1, j):
if points[k][1] >= points[j][1] and points[k][0] >= points[i][0]:
valid = False
break
if valid:
count += 1
return count
points = [[6, 2], [4, 4], [2, 6]]
print(number_of_ways(points))import java.util.Arrays;
public class AliceBobFence {
public static int numberOfWays(int[][] points) {
Arrays.sort(points, (a, b) -> (a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]));
int count = 0;
int n = points.length;
for (int i = 0; i < n; ++i) {
for (int j = i+1; j < n; ++j) {
if (points[i][1] > points[j][1]) {
boolean valid = true;
for (int k = i+1; k < j; ++k) {
if (points[k][1] >= points[j][1] && points[k][0] >= points[i][0]) {
valid = false;
break;
}
}
if (valid) count++;
}
}
}
return count;
}
public static void main(String[] args) {
int[][] points = {{6, 2}, {4, 4}, {2, 6}};
System.out.println(numberOfWays(points));
}
}#include <iostream>
#include <vector>
#include <algorithm>
bool comparison(const std::vector<int>& a, const std::vector<int>& b) {
if (a[0] == b[0])
return a[1] < b[1];
return a[0] < b[0];
}
int numberOfWays(std::vector<std::vector<int>>& points) {
std::sort(points.begin(), points.end(), comparison);
int count = 0;
int n = points.size();
for (int i = 0; i < n; ++i) {
for (int j = i+1; j < n; ++j) {
if (points[i][1] > points[j][1]) {
bool valid = true;
for (int k = i+1; k < j; ++k) {
if (points[k][1] >= points[j][1] && points[k][0] >= points[i][0]) {
valid = false;
break;
}
}
if (valid) count++;
}
}
}
return count;
}
int main() {
std::vector<std::vector<int>> points = {{6, 2}, {4, 4}, {2, 6}};
std::cout << numberOfWays(points) << std::endl;
return 0;
}function numberOfWays(points) {
points.sort(([x1, y1], [x2, y2]) => (x1 - x2) || (y1 - y2));
let count = 0;
const n = points.length;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
if (points[i][1] > points[j][1]) {
let valid = true;
for (let k = i + 1; k < j; k++) {
if (points[k][1] >= points[j][1] && points[k][0] >= points[i][0]) {
valid = false;
break;
}
}
if (valid) {
count++;
}
}
}
}
return count;
}
const points = [[6, 2], [4, 4], [2, 6]];
console.log(numberOfWays(points));#include <stdio.h>
#include <stdlib.h>
int cmp(const void* a, const void* b) {
int* pointA = *(int**)a;
int* pointB = *(int**)b;
if (pointA[0] == pointB[0])
return pointA[1] - pointB[1];
return pointA[0] - pointB[0];
}
int numberOfWays(int points[][2], int n) {
int count = 0;
int* pointers[n];
for (int i = 0; i < n; i++) pointers[i] = points[i];
qsort(pointers, n, sizeof(int*), cmp);
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if (pointers[i][1] > pointers[j][1]) {
int valid = 1;
for (int k = i+1; k < j; k++) {
if (pointers[k][1] >= pointers[j][1] && pointers[k][0] >= pointers[i][0]) {
valid = 0;
break;
}
}
if (valid) count++;
}
}
}
return count;
}
int main() {
int points[3][2] = {{6, 2}, {4, 4}, {2, 6}};
printf("%d\n", numberOfWays(points, 3));
return 0;
}using System;
using System.Linq;
public class Program {
public static int NumberOfWays(int[][] points) {
Array.Sort(points, (a, b) => a[0] == b[0] ? a[1].CompareTo(b[1]) : a[0].CompareTo(b[0]));
int count = 0;
int n = points.Length;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (points[i][1] > points[j][1]) {
bool valid = true;
for (int k = i + 1; k < j; k++) {
if (points[k][1] >= points[j][1] && points[k][0] >= points[i][0]) {
valid = false;
break;
}
}
if (valid)
count++;
}
}
}
return count;
}
public static void Main() {
int[][] points = new int[][] { new int[] { 6, 2 }, new int[] { 4, 4 }, new int[] { 2, 6 }};
Console.WriteLine(NumberOfWays(points));
}
}Python implements sorting for structure clarity before a stringent check finding 'down-right' positioning void of any intervening coordinates, spurred by central sort-derived eligibility.
Achieving O(n^2 log n) marks meaningful leverage over O(n^3), capitalizing on ranked positions adjustment for a singular directive pass over eventual times and space-n imprint.
Approach 3: Sorting and Classification
First, we sort the array. Then, we can classify the results based on the properties of a triangle.
- If the sum of the two smaller numbers is less than or equal to the largest number, it cannot form a triangle. Return "Invalid".
- If the three numbers are equal, it is an equilateral triangle. Return "Equilateral".
- If two numbers are equal, it is an isosceles triangle. Return "Isosceles".
- If none of the above conditions are met, it is a scalene triangle. Return "Scalene".
The time complexity is O(1), and the space complexity is O(1).
function numberOfPairs(points: number[][]): number {
points.sort((a, b) => (a[0] === b[0] ? b[1] - a[1] : a[0] - b[0]));
const n = points.length;
let ans = 0;
for (let i = 0; i < n; ++i) {
const [_, y1] = points[i];
let maxY = -Infinity;
for (let j = i + 1; j < n; ++j) {
const [_, y2] = points[j];
if (maxY < y2 && y2 <= y1) {
maxY = y2;
++ans;
}
}
}
return ans;
}func numberOfPairs(points [][]int) (ans int) {
sort.Slice(points, func(i, j int) bool {
return points[i][0] < points[j][0] || points[i][0] == points[j][0] && points[j][1] < points[i][1]
})
for i, p1 := range points {
y1 := p1[1]
maxY := math.MinInt32
for _, p2 := range points[i+1:] {
y2 := p2[1]
if maxY < y2 && y2 <= y1 {
maxY = y2
ans++
}
}
}
return
}impl Solution {
pub fn number_of_pairs(mut points: Vec<Vec<i32>>) -> i32 {
points.sort_by(|a, b| {
if a[0] == b[0] {
b[1].cmp(&a[1])
} else {
a[0].cmp(&b[0])
}
});
let n = points.len();
let mut ans = 0;
for i in 0..n {
let y1 = points[i][1];
let mut max_y = i32::MIN;
for j in (i + 1)..n {
let y2 = points[j][1];
if max_y < y2 && y2 <= y1 {
max_y = y2;
ans += 1;
}
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | The complexity is O(n^3) due to the triple nested loops making evaluations on each point's involvement for every pair. Space complexity is O(1) as no extra structures are retained. |
| Optimized Approach with Sorting | Achieving O(n^2 log n) marks meaningful leverage over O(n^3), capitalizing on ranked positions adjustment for a singular directive pass over eventual times and space-n imprint. |
| Sorting and Classification | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair + Interior Check | O(n^3) | O(1) | Best for understanding the geometric constraints and validating logic on small inputs |
| Sorting + Controlled Enumeration | O(n^2) | O(1) | Preferred solution for interviews and competitive programming with moderate input sizes |
Frequently asked questions
Is Find the Number of Ways to Place People II easy or hard?
LeetCode classifies this problem as Hard because the geometric constraint is subtle and the naive solution is inefficient. Recognizing that sorting and maintaining a blocking y boundary eliminates the inner validation loop is the key difficulty.
Find the Number of Ways to Place People II Python/Java solution
Python and Java implementations typically follow the same pattern: sort the coordinate array, iterate each point as a potential top-left corner, and track a running maximum y value while scanning candidates to the right. The optimized implementation runs in O(n^2) time.
How to solve Find the Number of Ways to Place People II in O(n^2)?
First sort all points by x coordinate in ascending order and by y in descending order for ties. For each point treated as the top-left corner, scan points to the right and track the maximum y encountered that is still below the starting point. Count a pair only when the candidate's y is within bounds and larger than the current blocking value.
What is the best approach for Find the Number of Ways to Place People II?
The most effective approach sorts points by x ascending and y descending, then scans possible pairs while tracking the highest valid y encountered so far. This avoids checking every interior point explicitly and reduces the complexity to O(n^2) time with O(1) extra space.
Is Find the Number of Ways to Place People II asked at Google/Amazon/Meta?
Geometry and coordinate-pair counting problems like this frequently appear in interviews at companies such as Google, Amazon, and Meta. They test sorting strategies, spatial reasoning, and the ability to optimize naive enumeration approaches.
What data structure is used in Find the Number of Ways to Place People II?
The problem primarily uses arrays to store coordinates and relies on sorting combined with simple variable tracking during iteration. No advanced data structures are required beyond ordered traversal of the sorted points.
What is the time complexity of Find the Number of Ways to Place People II?
The brute force solution runs in O(n^3) time because it checks every pair and scans all remaining points for conflicts. The optimized solution sorts the points and performs a quadratic scan, resulting in O(n^2) time and constant extra space.