2021. Brightest Position on Street π
Description
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 <= 105
lights[i].length == 2
-108 <= positioni <= 108
0 <= rangei <= 108
Solutions
Solution 1: Difference Array + Hash Table + Sorting
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
.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
|