Brightest Position on Street

Brightest Position on Street

What is this problem about?

Imagine a street with several street lights. Each light has a position and a range. The "brightness" at any point on the street is the number of lights that cover that point. Given a list of lights, you need to find the smallest coordinate that has the maximum brightness.

Why is this asked in interviews?

This is a standard interval-based problem frequently seen in Amazon and TikTok interviews. it's a great test of your ability to handle coordinate-based data and identify the "Sweep Line" algorithm. It evaluates how you manage events (start and end of light ranges) and how you find the peak of a cumulative distribution.

Algorithmic pattern used

This problem uses the Sweep Line pattern combined with a Prefix Sum (Difference Array) approach. For each light at position $P$ with range $R$, it covers the interval $[P-R, P+R]$. You create "events": a +1 at $P-R$ and a -1 at $P+R+1$. Sort these events by coordinate. Then, iterate through the sorted events, maintaining a running sum (the current brightness). The position where the sum is at its maximum is your answer.

Example explanation

Light 1: Pos 5, Range 2 -> Covers [3, 7] Light 2: Pos 6, Range 1 -> Covers [5, 7] Events:

• 3: +1 (Light 1 starts)
• 5: +1 (Light 2 starts)
• 7+1 (8): -1 (Light 1 ends)
• 7+1 (8): -1 (Light 2 ends)

Sweep:

• At 3: Brightness = 1.
• At 5: Brightness = 2. (Max!)
• At 8: Brightness = 0. The smallest position with max brightness (2) is 5.

Common mistakes candidates make

A frequent mistake is not handling the end of the interval correctly—specifically, the boundary condition of whether the endpoint is inclusive or exclusive. Another error is using a naive $O(N imes R)$ approach (marking every integer in the range), which fails if the ranges are large. The sweep-line approach is $O(N \log N)$ regardless of the range size.

Interview preparation tip

Whenever you see a problem involving overlapping intervals and finding a point of maximum overlap, think "Sweep Line." Sorting the start and end points as events is a powerful technique for these scenarios.