Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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) (as the rectangle shown in the image instead of a line), 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.Problem summary: 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
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Math
[[1,1],[2,2],[3,3]]
[[6,2],[4,4],[2,6]]
[[3,1],[1,3],[1,1]]
rectangle-area)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3027: Find the Number of Ways to Place People II
class Solution {
public int numberOfPairs(int[][] points) {
Arrays.sort(points, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
int ans = 0;
int n = points.length;
final int inf = 1 << 30;
for (int i = 0; i < n; ++i) {
int y1 = points[i][1];
int maxY = -inf;
for (int j = i + 1; j < n; ++j) {
int y2 = points[j][1];
if (maxY < y2 && y2 <= y1) {
maxY = y2;
++ans;
}
}
}
return ans;
}
}
// Accepted solution for LeetCode #3027: Find the Number of Ways to Place People II
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
}
# Accepted solution for LeetCode #3027: Find the Number of Ways to Place People II
class Solution:
def numberOfPairs(self, points: List[List[int]]) -> int:
points.sort(key=lambda x: (x[0], -x[1]))
ans = 0
for i, (_, y1) in enumerate(points):
max_y = -inf
for _, y2 in points[i + 1 :]:
if max_y < y2 <= y1:
max_y = y2
ans += 1
return ans
// Accepted solution for LeetCode #3027: Find the Number of Ways to Place People II
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
}
}
// Accepted solution for LeetCode #3027: Find the Number of Ways to Place People II
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;
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.
Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.