Find the Integer Point Covered by the Most Street Lamps

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

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

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

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

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.

Brightest Point Under Overlapping Street Lamps

Hints

1. 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.
2. 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.
3. 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.

Approach

Treat every lamp as the closed interval [position - range, position + range]. Record a +1 change at its left end and a -1 change at position + range + 1, the first point after its right end; lamps that share a coordinate simply accumulate into the same change entry, so duplicate lamps count separately. Visit the distinct change coordinates in increasing order while keeping a running sum. Invariant: after applying every change at coordinate x, the running sum equals the brightness of every integer point from x up to, but not including, the next change coordinate, because brightness can only change where some interval starts or just past where one ends. Therefore the maximum brightness is attained at some visited coordinate, and the smallest point that attains it is the first visited coordinate whose running sum reaches that maximum. Replacing the best answer only on a strictly greater sum keeps that earliest coordinate, which implements the smallest-point tie-break; a later region with equal brightness never replaces it. Placing the -1 at position + range + 1 makes both endpoints count: an interval ending at x and another starting at x are both counted at x, while an interval starting at x + 1 has its +1 cancel the -1 at x + 1 and never overlaps. Edge cases: a single lamp returns position - range; a range-0 lamp lights exactly its own position; the running sum is at least 1 at the first coordinate, so an answer always exists. All coordinates stay within [-2 * 10^8, 2 * 10^8 + 1], so 32-bit integers suffice in every language.

• Time complexity: O(n log n)
• Space complexity: O(n)