Find the Integer Point Covered by the Most Street Lamps
Company: Capital One
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
A street is modeled as a number line. You are given `lights`, where `lights[i] = [position_i, range_i]` describes a street lamp at integer coordinate `position_i` that lights every point from `position_i - range_i` to `position_i + range_i`, both ends included.
The brightness of a point `p` is the number of lamps that light `p`. Return the brightest point on the street. If several points share the maximum brightness, return the smallest of them.
### Function Signature
```python
def brightest_position(lights: list[list[int]]) -> int:
```
### Rules
- Consider integer points only.
- Each lamp lights the closed interval `[position_i - range_i, position_i + range_i]`, so both endpoints count.
- A lamp with `range_i = 0` lights only its own position.
- Several lamps may stand at the same position, and each of them counts separately.
- There is at least one lamp, so the maximum brightness is at least 1 and the answer always exists.
### Constraints
- `1 <= len(lights) <= 10^5`
- `-10^8 <= position_i <= 10^8`
- `0 <= range_i <= 10^8`
- Every lit point lies within `[-2 * 10^8, 2 * 10^8]`, which fits in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: lights = [[0, 2], [5, 1], [3, 1]]
Output: 2
```
The lamps light `[-2, 2]`, `[4, 6]` and `[2, 4]`. Point `2` is lit by the first and third lamps and point `4` by the second and third, so both have brightness 2; no point is lit by all three. The smaller of the two is `2`.
**Example 2**
```text
Input: lights = [[1, 0], [-1, 0]]
Output: -1
```
Each lamp lights only its own position, so points `-1` and `1` both have brightness 1, and `-1` is smaller.
**Example 3**
```text
Input: lights = [[10, 5], [0, 3], [8, 1]]
Output: 7
```
The lamps light `[5, 15]`, `[-3, 3]` and `[7, 9]`. Points `7`, `8` and `9` are lit by two lamps, the maximum, and `7` is the smallest of them.
Overview: Street lamps on a number line each light a closed interval around their position; return the integer point lit by the most lamps, choosing the smallest coordinate on ties. Tests coverage counting over a wide coordinate range and correct handling of inclusive endpoints.
A street is modeled as a number line. You are given `lights`, where `lights[i] = [position_i, range_i]` describes a street lamp at integer coordinate `position_i` that lights every integer point from `position_i - range_i` to `position_i + range_i`, both ends included.
The brightness of a point `p` is the number of lamps that light `p`. Return the brightest point on the street. If several points share the maximum brightness, return the smallest of them.
### Rules
- Consider integer points only.
- Each lamp lights the closed interval `[position_i - range_i, position_i + range_i]`, so both endpoints count.
- A lamp with `range_i = 0` lights only its own position.
- Several lamps may stand at the same position, and each of them counts separately.
- There is at least one lamp, so the maximum brightness is at least 1 and the answer always exists.
### Constraints
- `1 <= len(lights) <= 10^5`
- `-10^8 <= position_i <= 10^8`
- `0 <= range_i <= 10^8`
- Every lit point lies within `[-2 * 10^8, 2 * 10^8]`, which fits in a 32-bit signed integer. No input or output value exceeds 2^31 - 1 in magnitude, so `int` is sufficient in Java and C++.
### Example 1
```text
Input: lights = [[0, 2], [5, 1], [3, 1]]
Output: 2
```
The lamps light `[-2, 2]`, `[4, 6]` and `[2, 4]`. Point `2` is lit by the first and third lamps and point `4` by the second and third, so both have brightness 2; no point is lit by all three. The smaller of the two is `2`.
### Example 2
```text
Input: lights = [[10, 5], [0, 3], [8, 1]]
Output: 7
```
The lamps light `[5, 15]`, `[-3, 3]` and `[7, 9]`. Points `7`, `8` and `9` are lit by two lamps, the maximum, and `7` is the smallest of them.
Implement `brightest_position(lights)`, which returns the answer as an integer.
Constraints
- 1 <= len(lights) <= 10^5
- lights[i] = [position_i, range_i]
- -10^8 <= position_i <= 10^8
- 0 <= range_i <= 10^8
- Every lit point lies within [-2 * 10^8, 2 * 10^8], which fits in a 32-bit signed integer.
Examples
Input: ([[0, 2], [5, 1], [3, 1]],)
Expected Output: 2
Explanation: Source example 1: points 2 and 4 both reach brightness 2 and nothing is brighter; the smaller, 2, wins.
Input: ([[1, 0], [-1, 0]],)
Expected Output: -1
Explanation: Source example 2: two range-0 lamps tie at brightness 1; -1 is the smaller point.
Hints
- The coordinates span up to 4 * 10^8 + 1 integer points, so examining every point one by one is too slow; think about which points could possibly be the smallest brightest point.
- Both endpoints of every lamp's interval are lit: an interval ending at x and another starting at x overlap at x, while one starting at x + 1 does not.
- When several points tie for the maximum brightness the smallest must be returned, so a later point with equal brightness must never replace an earlier answer.