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.
We can consider the range illuminated by each street light as an interval, with the left endpoint l = position_i - range_i and the right endpoint r = position_i + range_i. We can use the idea of a difference array. For each interval [l, r], we add 1 to the value at position l and subtract 1 from the value at position r + 1. We use a hash table to maintain the change value at each position.
Then we traverse each position in ascending order, calculate the brightness s at the current position. If the previous maximum brightness mx < s, then update the maximum brightness mx = s and record the current position ans = i.
Finally, return ans.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of lights.
Python
Java
C++
Go
JavaScript
| 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 |
Brightest Position On Street • Owen Wu • 1,213 views views
Watch 1 more video solutions →Practice Brightest Position on Street with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor