Find the smallest position lit by the most street lamps
Company: Quora
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
Street lamps stand along a straight street, modeled as a number line. Each lamp lights a closed stretch of the street centered on the lamp. Find the position lit by the greatest number of lamps; if several positions tie, return the smallest one.
### Function Signature
```python
def brightest_position(lamps: list[list[int]]) -> int:
```
### Rules
- `lamps[i] = [position, radius]` lights every point `x` with `position - radius <= x <= position + radius`; both ends are included.
- The brightness of a point is the number of lamps that light it. Lamps may overlap, and several lamps may stand at the same position.
- Return the smallest integer `x` whose brightness equals the maximum brightness over all points of the street. Every lit stretch starts and ends on an integer, so the maximum is always reached at an integer.
### Constraints
- `1 <= len(lamps) <= 10^5`
- `-10^8 <= position <= 10^8`
- `0 <= radius <= 10^8`
### Examples
**Example 1**
```text
Input: lamps = [[0, 1], [3, 2], [2, 1]]
Output: 1
```
The lamps light `[-1, 1]`, `[1, 5]` and `[1, 3]`. Position 1 is lit by all three, and no other position is.
**Example 2**
```text
Input: lamps = [[5, 0], [1, 1], [8, 1]]
Output: 0
```
The stretches `[5, 5]`, `[0, 2]` and `[7, 9]` do not overlap, so the maximum brightness is 1, and the smallest point with brightness 1 is 0.
**Example 3**
```text
Input: lamps = [[1, 1], [4, 2], [10, 1], [12, 1]]
Output: 2
```
The stretches are `[0, 2]`, `[2, 6]`, `[9, 11]` and `[11, 13]`. Because both ends are included, position 2 is lit by two lamps, and so is position 11. The smaller of the two is 2.
Overview: Each street lamp lights a closed stretch of a number line around its position. Return the position lit by the most lamps, choosing the smallest one when several tie. The problem tests interval overlap counting, inclusive boundaries and scaling to a hundred thousand lamps with large coordinates.
Read the full Quora Software Engineer interview experience this question came from
Street lamps stand along a straight street, modeled as a number line. Each lamp lights a closed stretch of the street centered on the lamp.
You are given `lamps`, where `lamps[i] = [position, radius]`. That lamp lights every point `x` with `position - radius <= x <= position + radius`; both ends are included, so a lamp with radius `0` lights exactly its own position.
The **brightness** of a point is the number of lamps that light it. Lamps may overlap, and several lamps may stand at the same position.
Return the smallest integer `x` whose brightness equals the maximum brightness over all points of the street. Every lit stretch starts and ends on an integer, so the maximum is always reached at an integer. Because `lamps` is never empty, the maximum brightness is at least 1.
### Example 1
```text
Input: lamps = [[0, 1], [3, 2], [2, 1]]
Output: 1
```
The lamps light `[-1, 1]`, `[1, 5]` and `[1, 3]`. Position 1 is lit by all three, and no other position is.
### Example 2
```text
Input: lamps = [[1, 1], [4, 2], [10, 1], [12, 1]]
Output: 2
```
The stretches are `[0, 2]`, `[2, 6]`, `[9, 11]` and `[11, 13]`. Because both ends are included, position 2 is lit by two lamps, and so is position 11. The smaller of the two is 2.
### Constraints
- `1 <= len(lamps) <= 10^5`
- `-10^8 <= position <= 10^8`
- `0 <= radius <= 10^8`
Every stretch endpoint and the returned value lie in `[-2 * 10^8, 2 * 10^8]`, so no value exceeds `2^31 - 1` and a signed 32-bit integer is enough.
Constraints
- 1 <= len(lamps) <= 10^5
- lamps[i] = [position, radius]
- -10^8 <= position <= 10^8
- 0 <= radius <= 10^8
- Every stretch endpoint and the answer lie in [-2 * 10^8, 2 * 10^8], so all values fit in a signed 32-bit integer (none exceeds 2^31 - 1)
Examples
Input: ([[7, 0]],)
Expected Output: 7
Explanation: Minimum valid: one lamp with radius 0 lights only position 7.
Input: ([[-3, 4]],)
Expected Output: -7
Explanation: Single lamp with radius > 0 lights [-7, 1]; every lit point ties at brightness 1, so the negative left end -7 is returned.
Hints
- Both ends of every stretch are lit, so a stretch that ends at a point and another that starts at that same point both light it.
- Brightness only changes at points where some stretch begins or just after one ends; between such points it stays the same.
- When several separate parts of the street tie for the maximum, return the smallest integer point among all of them, which need not be any lamp's position.