3025. Find the Number of Ways to Place People I - Solution

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] = [x_i, y_i].

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).

Return the count.

Example 1:

Input: points = [[1,1],[2,2],[3,3]]

Output: 0

Explanation:

There is no way to choose A and B so A is on the upper left side of B.

Example 2:

Input: points = [[6,2],[4,4],[2,6]]

Output: 2

Explanation:

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.

Example 3:

Input: points = [[3,1],[1,3],[1,1]]

Output: 2

Explanation:

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.

Approach overview

Problem Overview: You are given coordinates of people on a 2D grid. A valid pair forms a rectangle where one person acts as the top‑left corner and another as the bottom‑right corner. The pair is valid only if no other person lies inside or on the boundary of that rectangle. The task is to count how many such pairs exist.

Approach 1: Naive Brute Force (O(n^3) time, O(1) space)

The direct approach is to enumerate every pair of points (i, j). Treat i as the top‑left candidate and j as the bottom‑right candidate, which requires x_i ≤ x_j and y_i ≥ y_j. For every valid pair, iterate through all remaining points and check whether any point lies inside the rectangle defined by these two corners. If a third point satisfies x_i ≤ x_k ≤ x_j and y_j ≤ y_k ≤ y_i, the pair is invalid. This approach relies purely on enumeration and is useful for understanding the geometric constraint, but the extra scan for each pair leads to O(n^3) time.

Approach 2: Optimized Sorting and Sweep Line Technique (O(n^2) time, O(1) space)

A more efficient strategy avoids repeatedly scanning all points. First sort the points by x ascending and by y descending when x values tie. This ordering allows you to process potential top‑left candidates while sweeping to the right. For each point i, iterate through points j > i. If y_j ≤ y_i, the pair could form a valid rectangle. While scanning, maintain the highest y value encountered that is still below y_i. If y_j is greater than this tracked boundary, the rectangle between i and j remains empty and the pair is counted. This technique relies on ordered traversal using sorting and a geometric sweep similar to a geometry sweep‑line algorithm, reducing redundant interior checks.

Recommended for interviews: Start with the brute force pair enumeration to demonstrate you understand the rectangle constraint. Then move to the sorted sweep approach. Interviewers typically expect the optimized solution because it removes the expensive third loop and uses ordering to implicitly enforce the empty‑rectangle condition.

Approach 1: Naive Brute Force

The simplest approach involves checking every possible pair of points to see if they meet the criteria: one point must be in the 'upper left' of another and no other point should lie within the rectangle they form. This approach leverages nested loops to iterate through the list and check each pair of points.

Python

from typing import List

def countWays(points: List[List[int]]) -> int:
    n = len(points)
    count = 0
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            if points[i][0] < points[j][0] and points[i][1] > points[j][1]:
                valid = True
                for k in range(n):
                    if k == i or k == j:
                        continue
                    if 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(countWays(points))

Java

import java.util.List;

public class Solution {
    public int countWays(List<int[]> points) {
        int n = points.size();
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                if (points.get(i)[0] < points.get(j)[0] && points.get(i)[1] > points.get(j)[1]) {
                    boolean valid = true;
                    for (int k = 0; k < n; k++) {
                        if (k == i || k == j) continue;
                        if (points.get(k)[0] > points.get(i)[0] && points.get(k)[0] < points.get(j)[0] &&
                            points.get(k)[1] < points.get(i)[1] && points.get(k)[1] > points.get(j)[1]) {
                            valid = false;
                            break;
                        }
                    }
                    if (valid) count++;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        List<int[]> points = List.of(new int[]{6, 2}, new int[]{4, 4}, new int[]{2, 6});
        int result = sol.countWays(points);
        System.out.println(result);
    }
}

C++

#include <vector>
using namespace std;

int countWays(vector<vector<int>>& points) {
    int n = points.size(), count = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == j) continue;
            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) continue;
                    if (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() {
    vector<vector<int>> points = {{6, 2}, {4, 4}, {2, 6}};
    int result = countWays(points);
    return 0;
}

JavaScript

function countWays(points) {
    let count = 0;
    const n = points.length;

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (i === j) continue;
            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) continue;
                    if (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(countWays(points));

#include <stdio.h>

int countWays(int points[][2], int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            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) continue;
                    if (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[][2] = {{6, 2}, {4, 4}, {2, 6}};
    int result = countWays(points, 3);
    printf("%d\n", result);
    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int CountWays(List<int[]> points) {
        int n = points.Count;
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                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) continue;
                        if (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() {
        List<int[]> points = new List<int[]> { new int[] { 6, 2 }, new int[] { 4, 4 }, new int[] { 2, 6 } };
        Solution sol = new Solution();
        int result = sol.CountWays(points);
        Console.WriteLine(result);
    }
}

In this Python solution, comprehensive iterations are used through nested loops to find qualifying pairs, while checking against points within the rectangle, using typical Python list indexing to manage coordinates.

Complexity

Time Complexity: O(n^3) since every point pair is checked thoroughly.
Space Complexity: O(1) as no additional structures are needed apart from indexes.

Try this approach in the editor

Approach 2: Optimized Sorting and Sweep Line Technique

We can optimize the brute force approach by sorting the points and using a sweep line technique. By sorting points either by x or y coordinates, and then processing them in a specific order, we can reduce unnecessary checks. This approach uses a line sweep to maintain set of 'active' points that determine valid pairs as we iterate over the points.

Python

from typing import List

def countWays(points: List[List[int]]) -> int:
    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]:
                        valid = False
                        break
                if valid:
                    count += 1
    return count

points = [[6, 2], [4, 4], [2, 6]]
print(countWays(points))

Java

import java.util.*;

public class Solution {
    public int countWays(List<int[]> points) {
        points.sort((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        int n = points.size();
        int count = 0;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (points.get(i)[1] > points.get(j)[1]) {
                    boolean valid = true;
                    for (int k = i + 1; k < j; k++) {
                        if (points.get(k)[1] > points.get(j)[1]) {
                            valid = false;
                            break;
                        }
                    }
                    if (valid) count++;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        List<int[]> points = Arrays.asList(new int[]{6, 2}, new int[]{4, 4}, new int[]{2, 6});
        Solution sol = new Solution();
        System.out.println(sol.countWays(points));
    }
}

C++

#include <vector>
#include <algorithm>
using namespace std;

int countWays(vector<vector<int>>& points) {
    sort(points.begin(), points.end()); // Sort by x, then y
    int n = points.size();
    int count = 0;

    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]) {
                        valid = false;
                        break;
                    }
                }
                if (valid) count++;
            }
        }
    }
    return count;
}

int main() {
    vector<vector<int>> points = {{6, 2}, {4, 4}, {2, 6}};
    int result = countWays(points);
    return 0;
}

JavaScript

function countWays(points) {
    points.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]);
    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]) {
                        valid = false;
                        break;
                    }
                }
                if (valid) count++;
            }
        }
    }
    return count;
}

const points = [[6, 2], [4, 4], [2, 6]];
console.log(countWays(points));

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    int *point1 = (int *)a;
    int *point2 = (int *)b;
    // Sort by x, then by y
    if (point1[0] == point2[0])
        return point1[1] - point2[1];
    return point1[0] - point2[0];
}

int countWays(int points[][2], int n) {
    qsort(points, n, 2 * sizeof(int), compare);

    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (points[i][1] > points[j][1]) {
                int valid = 1;
                for (int k = i + 1; k < j; k++) {
                    if (points[k][1] > points[j][1]) {
                        valid = 0;
                        break;
                    }
                }
                if (valid) count++;
            }
        }
    }
    return count;
}

int main() {
    int points[][2] = {{6, 2}, {4, 4}, {2, 6}};
    int result = countWays(points, 3);
    printf("%d\n", result);
    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int CountWays(List<int[]> points) {
        points.Sort((a, b) => a[0] == b[0] ? a[1].CompareTo(b[1]) : a[0].CompareTo(b[0]));
        int n = points.Count;
        int count = 0;

        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]) {
                            valid = false;
                            break;
                        }
                    }
                    if (valid) count++;
                }
            }
        }
        return count;
    }

    public static void Main() {
        List<int[]> points = new List<int[]> { new int[] { 6, 2 }, new int[] { 4, 4 }, new int[] { 2, 6 } };
        Solution sol = new Solution();
        Console.WriteLine(sol.CountWays(points));
    }
}

Here, Python's list.sort() aids in overarching point order as we scan and weed out internal unfit members amongst possibilities.

Complexity

Time Complexity: O(n^2 log n) due to input sorting.
Space Complexity: O(1) for just indexes and flags use.

Try this approach in the editor

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).

TypeScript

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
}

Rust

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
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Naive Brute Force	Time Complexity: O(n^3) since every point pair is checked thoroughly. Space Complexity: O(1) as no additional structures are needed apart from indexes.
Optimized Sorting and Sweep Line Technique	Time Complexity: O(n^2 log n) due to input sorting. Space Complexity: O(1) for just indexes and flags use.
Sorting and Classification	–

Complexity analysis

Approach	Time	Space	When to Use
Naive Brute Force Pair Enumeration	O(n^3)	O(1)	Useful for understanding the geometric constraint and validating logic for small inputs.
Sorting + Sweep Line	O(n^2)	O(1)	Preferred approach for interviews and competitive programming. Sorting removes the need to check every interior point.

Frequently asked questions

Is Find the Number of Ways to Place People I easy or hard?

The problem is rated Medium on LeetCode. The brute force logic is straightforward, but recognizing that sorting and a sweep-line constraint can remove the expensive third loop requires stronger algorithmic intuition.

Find the Number of Ways to Place People I Python/Java solution

Most implementations follow the same structure: sort the list of coordinate pairs, then run nested loops to sweep potential rectangles while maintaining a boundary value. The logic translates directly across Python, Java, C++, and C# because it relies only on sorting and iteration.

How to solve Find the Number of Ways to Place People I in O(n^2)?

Sort all coordinates by x ascending and by y descending for ties. For each point as the potential top-left corner, sweep through points to its right. Track the highest y encountered that is still below the starting point's y. Count a pair only when the new point's y is below the start but above the blocking boundary, ensuring no interior point exists.

What is the best approach for Find the Number of Ways to Place People I?

The most effective approach sorts the points by x ascending and y descending, then uses a sweep to evaluate valid top-left and bottom-right pairs. While scanning to the right, track the highest y that blocks rectangles. This avoids checking every interior point and reduces the complexity to O(n^2) after sorting.

Is Find the Number of Ways to Place People I asked at Google/Amazon/Meta?

Problems combining geometry, sorting, and pair enumeration are common in interviews at large tech companies. Variants of this pattern appear in Google and Amazon interview prep because they test spatial reasoning and the ability to optimize brute force checks using ordering.

What data structure is used in Find the Number of Ways to Place People I?

The solution mainly relies on arrays to store coordinates and sorting to order them. The optimized algorithm uses a sweep-line style traversal with a few scalar variables to track boundaries instead of additional data structures.

What is the time complexity of Find the Number of Ways to Place People I?

The brute force solution runs in O(n^3) because every pair of points requires scanning all remaining points to check if the rectangle is empty. The optimized solution sorts the points and performs a quadratic sweep, resulting in O(n^2) time and O(1) extra space.

Find the Number of Ways to Place People I solution and explanation

The problem

Approach overview

Approach 1: Naive Brute Force

Approach 2: Optimized Sorting and Sweep Line Technique

Approach 3: Sorting and Classification

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find the Number of Ways to Place People I solution and explanation

The problem

Approach overview

Approach 1: Naive Brute Force

Approach 2: Optimized Sorting and Sweep Line Technique

Approach 3: Sorting and Classification

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems