Find Closest Person

Find Closest Person

What is this problem about?

The Find Closest Person coding problem typically involves a row of seats or a 1D grid where some seats are occupied and others are empty. You are given the location of an empty seat and need to find the distance to the nearest person (occupied seat). Alternatively, you might be asked to find an empty seat that maximizes the distance to the nearest person.

Why is this asked in interviews?

Meta and Amazon use this problem to test your ability to calculate distances in a linear space efficiently. It evaluation your proficiency with Array interview patterns, specifically involving Multi-pass scans or Two Pointers. It mimics real-world scenarios like social distancing or resource allocation in a distributed system.

Algorithmic pattern used

This problem is best solved using a Prefix and Suffix Scan.

1. Iterate from left to right to find the distance to the nearest person on the left.
2. Iterate from right to left to find the distance to the nearest person on the right.
3. For each seat, the distance to the "closest person" is the minimum of these two values. If the goal is to maximize this distance, you track the global maximum of these minimums.

Example explanation

Seats: [1, 0, 0, 0, 1] (1 = person, 0 = empty)

1. Left scan: [0, 1, 2, 3, 0] (distance from left-most person).
2. Right scan: [0, 3, 2, 1, 0] (distance from right-most person).
3. Minimums: [0, 1, 2, 1, 0]. The middle seat (index 2) is the farthest from anyone, with a "closest person distance" of 2.

Common mistakes candidates make

• $O(N^2)$ brute force: For every empty seat, scanning the whole row to find people.
• Boundary conditions: Not handling cases where there is no person to the left (e.g., seats at the very start of the row) or no person to the right.
• Distance definition: Confusing "number of seats between" with "difference in indices."

Interview preparation tip

"Closest element" problems in 1D arrays are often solved by two passes (left-to-right and right-to-left). This is a foundational Prefix Sum interview pattern variation that avoids the need for complex search algorithms.