Mid/Senior
Brightest Position on Street
A perfectly straight street is represented by a number line. You are given a 2D integer array lights, where lights[i] = [position_i, range_i] means there is a street lamp at position_i that illuminates every integer position from position_i - range_i to position_i + range_i, inclusive.
The brightness of a position is the number of street lamps that illuminate it.
Return the brightest position on the street. If there are multiple positions with the maximum brightness, return the smallest such position.
Your solution should be efficient enough for up to 10^5 lights.
Example 1
Input
lights = [[-3,2],[1,2],[3,3]]Output
-1The maximum brightness is 2, achieved at several positions, and the smallest of them is -1.
Example 2
Input
lights = [[1,0],[0,1]]Output
1Position 1 is illuminated by both lamps, giving it the highest brightness.
Constraints
- 1 <= lights.length <= 10^5
- lights[i].length == 2
- -10^8 <= position_i <= 10^8
- 0 <= range_i <= 10^8
Asked at 7 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.