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. Topics: Array, Ordered Set, Prefix Sum, Sorting. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 18 parametrized pytest cases, and a playground notebook:

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

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, full suite in test_solution.py:

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.