Watch 2 video solutions for Brightest Position on Street, a medium level problem involving Array, Prefix Sum, Ordered Set. This walkthrough by Owen Wu has 1,213 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
A perfectly straight street is represented by a number line. The street has street lamp(s) on it and is represented by a 2D integer array lights. Each lights[i] = [positioni, rangei] indicates that there is a street lamp at position positioni that lights up the area from [positioni - rangei, positioni + rangei] (inclusive).
The brightness of a position p is defined as the number of street lamp that light up the position p.
Given lights, return the brightest position on the street. If there are multiple brightest positions, return the smallest one.
Example 1:
Input: lights = [[-3,2],[1,2],[3,3]] Output: -1 Explanation: The first street lamp lights up the area from [(-3) - 2, (-3) + 2] = [-5, -1]. The second street lamp lights up the area from [1 - 2, 1 + 2] = [-1, 3]. The third street lamp lights up the area from [3 - 3, 3 + 3] = [0, 6]. Position -1 has a brightness of 2, illuminated by the first and second street light. Positions 0, 1, 2, and 3 have a brightness of 2, illuminated by the second and third street light. Out of all these positions, -1 is the smallest, so return it.
Example 2:
Input: lights = [[1,0],[0,1]] Output: 1 Explanation: The first street lamp lights up the area from [1 - 0, 1 + 0] = [1, 1]. The second street lamp lights up the area from [0 - 1, 0 + 1] = [-1, 1]. Position 1 has a brightness of 2, illuminated by the first and second street light. Return 1 because it is the brightest position on the street.
Example 3:
Input: lights = [[1,2]] Output: -1 Explanation: The first street lamp lights up the area from [1 - 2, 1 + 2] = [-1, 3]. Positions -1, 0, 1, 2, and 3 have a brightness of 1, illuminated by the first street light. Out of all these positions, -1 is the smallest, so return it.
Constraints:
1 <= lights.length <= 105lights[i].length == 2-108 <= positioni <= 1080 <= rangei <= 108Problem Overview: Each street lamp lights an interval [position - range, position + range]. Multiple lamps can overlap. The task is to find the street coordinate with the highest total brightness, returning the smallest position if several share the same brightness.
Approach 1: Brute Force Interval Counting (O(n * R) time, O(1) space)
For every lamp, explicitly mark every integer position inside its lighting interval and count how many lamps affect that position. After processing all lamps, scan the positions to find the maximum brightness. This approach is easy to reason about but becomes infeasible when ranges are large because the street coordinates can grow to millions or billions. It’s mainly useful for understanding the interval overlap concept before optimizing.
Approach 2: Difference Array + Sorting (Sweep Line) (O(n log n) time, O(n) space)
Instead of updating every position in an interval, record only where brightness changes. For a lamp covering [l, r], add +1 at l and -1 at r + 1. Store these updates in a hash table or ordered map keyed by coordinate. After collecting all events, sort the keys and sweep from left to right while maintaining a running prefix sum. The running value represents current brightness. Track the coordinate where this prefix sum reaches its maximum.
This technique is a classic sweep line built on a difference array. The key insight: interval updates can be compressed into boundary events, and the true values are reconstructed with a prefix sum. Because only lamp boundaries are stored, the algorithm avoids iterating across huge coordinate ranges. Sorting the boundary points gives O(n log n) complexity while keeping memory proportional to the number of lamps.
The solution combines concepts from Array, Prefix Sum, and Ordered Set style sweep-line processing. It’s the standard technique for interval overlap problems such as maximum active events or meeting room usage.
Recommended for interviews: The sweep line using a difference array and sorted coordinates is the expected solution. It demonstrates that you recognize interval overlap patterns and can reduce range updates to boundary events. Mentioning the brute force approach first shows understanding, but implementing the prefix-sum sweep line proves algorithmic maturity.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Interval Counting | O(n * R) | O(1) | Small coordinate ranges where iterating every position is feasible |
| Difference Array + Hash Map + Sorting (Sweep Line) | O(n log n) | O(n) | General case with large coordinates; efficient interval overlap tracking |