Find the Number of Ways to Place People I

Find the Number of Ways to Place People I

1. What is this problem about?

The Find the Number of Ways to Place People I interview question is a 2D geometry and counting task. You are given the coordinates of $N$ people on a plane. You need to find the number of ways to pick a pair of people, $(A, B)$, such that person $A$ can be the top-left corner and person $B$ can be the bottom-right corner of a rectangle. A critical constraint is that no other person should be inside or on the boundary of this rectangle.

2. Why is this asked in interviews?

Companies like Meta and Google use the Find the Number of Ways to Place People I coding problem to assess a candidate's ability to handle spatial constraints and sorting logic. It tests your familiarity with Sorting interview patterns and Enumeration. It evaluates if you can systematically check conditions without redundant calculations, even in a medium-sized dataset.

3. Algorithmic pattern used

This problem utilizes Sorting and Nested Enumeration.

• Coordinate Sorting: Sort the people primarily by their X-coordinate (ascending) and secondarily by their Y-coordinate (descending). This order allows you to process potential "top-left" candidates from left to right.
• Validation: For each person $i$ (top-left candidate), iterate through potential "bottom-right" candidates $j$ that appear after $i$ in the sorted list.
• Y-Range Check: A pair $(i, j)$ is valid only if $y_j \leq y_i$. While iterating through candidates for $B$, keep track of the maximum Y-coordinate seen so far that is less than or equal to $y_i$. This helps in quickly validating if any person is "in between."

4. Example explanation

Locations: A(1, 1), B(2, 2), C(3, 3).

• Sort by X: A(1, 1), B(2, 2), C(3, 3).
• Pick top-left $A(1, 1)$. Candidates for bottom-right must have $x \geq 1$ and $y \leq 1$.
• No points satisfy $y \leq 1$ other than $A$ itself.
• Pick top-left $B(2, 2)$. Only $A(1, 1)$ satisfies $y \leq 2$, but $A$ is to the left of $B$. This specific example has no valid rectangles. If we had A(1, 3) and B(2, 1), they would form a valid pair if no point like C(1.5, 2) existed.

5. Common mistakes candidates make

• Ignoring the sorting secondary criteria: Failing to sort by Y correctly can lead to missed pairs or incorrect boundary checks.
• $O(N^3)$ Brute Force: Checking every third point for every pair. For $N=1000$, this will be too slow. The goal is to optimize the inner check.
• Coordinate confusion: Mixing up top-left ($x$ small, $y$ large) and bottom-right ($x$ large, $y$ small) rules.

6. Interview preparation tip

Practice problems involving points on a 2D plane. Often, sorting one dimension reduces the problem to a 1D range problem on the other dimension. Mastering this reduction is key to solving Geometry interview patterns.