Show problems as
Classic problem #2021MediumArraySortingPrefix SumOrdered Set

Brightest Position on Street

Real-world version: Brightest Spot on the Walkway
Tracked in this browser only
Read Brightest Position on Street on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A walkway is marked off with whole-number coordinates that run in both directions from zero. Lamps are described by lights, where lights[i] = [position_i, range_i] means lamp i stands at coordinate position_i and throws light on every whole-number coordinate from position_i - range_i through position_i + range_i, both ends included.

The brightness of a coordinate is the number of lamps whose light reaches it. Return the coordinate with the greatest brightness. If several coordinates share the greatest brightness, return the smallest of them.

Examples

Example 1

Input
lights = [[4, 2], [6, 2], [5, 0]]
Output
5

The first lamp lights 2 through 6, the second lights 4 through 8 and the third lights only 5. Coordinate 5 is reached by all three, so its brightness is 3 and no coordinate can beat that.

Example 2

Input
lights = [[0, 2], [4, 2]]
Output
2

One lamp lights -2 through 2 and the other lights 2 through 6. Coordinate 2 is the only one reached by both, so its brightness is 2.

Example 3

Input
lights = [[0, 1], [3, 1]]
Output
-1

The lamps light -1 through 1 and 2 through 4, and they never overlap, so the greatest brightness is 1 and it is shared by six coordinates. The smallest of them is -1.

Constraints

  • 1 <= lights.length <= 10^5
  • lights[i].length == 2
  • -10^8 <= position_i <= 10^8
  • 0 <= range_i <= 10^8

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def brightest_position(lights: list[list[int]]) -> int:
Java
public int brightestPosition(int[][] lights)

More on the same topics