Find the Number of Ways to Place People I - Video Solutions

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.