> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Brightest Position on Street Python Solution

> Tested Python solution for LeetCode 2021 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 2021, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Ordered Set](/catalog/topics/ordered-set), [Prefix Sum](/catalog/topics/prefix-sum), [Sorting](/catalog/topics/sorting). [View on LeetCode](https://leetcode.com/problems/brightest-position-on-street/description/).

Generate this problem as a practice environment: tested reference solution, 18 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 2021   # by problem number
lcpy gen -s brightest_position_on_street   # by problem name
```

## Problem

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] = [position_i, range_i]` indicates that there is a street lamp at position `position_i` that lights up the area from `[position_i - range_i, position_i + range_i]` (**inclusive**).

The **brightness** of a position `p` is defined as the number of street lamps 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.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2021/09/28/image-20210928155140-1.png)

```
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.
```

```
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.
```

```
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 \<= 10^5
* lights\[i].length == 2
* -10^8 \<= position\_i \<= 10^8
* 0 \<= range\_i \<= 10^8

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/brightest_position_on_street/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/brightest_position_on_street/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n log n)
    # Space: O(n)
    def brightest_position(self, lights: list[list[int]]) -> int:
        diff: dict[int, int] = {}
        for pos, rng in lights:
            diff[pos - rng] = diff.get(pos - rng, 0) + 1
            diff[pos + rng + 1] = diff.get(pos + rng + 1, 0) - 1

        best = 0
        brightness = 0
        best_pos = 0
        for point in sorted(diff):
            brightness += diff[point]
            if brightness > best:
                best = brightness
                best_pos = point
        return best_pos
```

## Complexity

| Time | Space |
| - | - |
| O(n log n) | O(n) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.