Skip to main content
Talentd

Find the Number of Ways to Place People I - Solution & Explanation

MediumArrayMathGeometrySorting20 min readAsked at: Amazon, Meta, Google +1
Practice this problem

Problem Statement

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

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.

This solution checks every pair of points to see if one point is to the upper-left of the other. If it is, it validates that no other point lies within the rectangle formed by the two. This is done using nested loops.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^3) due to the nested loops.
Space Complexity: O(1) as we use constant additional space.

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.

This C implementation leverages the properties of sorted points to reduce checks and focus on possible rectangles dynamically.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2 log n), due to sorting, followed by pairwise examination.
Space Complexity: O(1), maintaining fewer intermediate states.

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

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Naive Brute Force

Time Complexity: O(n^3) due to the nested loops.
Space Complexity: O(1) as we use constant additional space.

Optimized Sorting and Sweep Line Technique

Time Complexity: O(n^2 log n), due to sorting, followed by pairwise examination.
Space Complexity: O(1), maintaining fewer intermediate states.

Sorting and Classification—

Detailed Complexity Analysis

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

Video Solution

Find the Number of Ways to Place People I | 2 Detailed Approaches | Leetcode 3025 | codestorywithMIK • codestorywithMIK • 10,555 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Find the Number of Ways to Place People I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Rectangle Area