How hard is LeetCode 2021. Brightest Position on Street?

LeetCode 2021. Brightest Position on Street is rated Medium on LeetCode.

What is the time complexity of LeetCode 2021. Brightest Position on Street?

The Python solution on this page runs in O(n \times \log n).

What is the space complexity of LeetCode 2021. Brightest Position on Street?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 2021. Brightest Position on Street cover?

LeetCode 2021. Brightest Position on Street is tagged Array, Ordered Set, Prefix Sum and Sorting on LeetCode.

Is LeetCode 2021. Brightest Position on Street a premium problem?

Yes. LeetCode 2021. Brightest Position on Street is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Brightest Position on Street — LeetCode 2021 Python Solution

MediumLeetCode PremiumArrayOrdered SetPrefix SumSorting

Problem: #2021
Pattern: Prefix Sum
Reading time: 3 min
Source: leetcode.com

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

Example

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

Python solution

Python

class Solution:
    def brightestPosition(self, lights: List[List[int]]) -> int:
        d = defaultdict(int)
        for i, j in lights:
            l, r = i - j, i + j
            d[l] += 1
            d[r + 1] -= 1
        ans = s = mx = 0
        for k in sorted(d):
            s += d[k]
            if mx < s:
                mx = s
                ans = k
        return ans

Complexity

Measure	Complexity
Time	O(n \times \log n)
Space	O(n) auxiliary

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 2021. Brightest Position on Street is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Prefix Sum.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2021. Brightest Position on Street?: LeetCode 2021. Brightest Position on Street is rated Medium on LeetCode.
What is the time complexity of LeetCode 2021. Brightest Position on Street?: The Python solution on this page runs in O(n \times \log n).
What is the space complexity of LeetCode 2021. Brightest Position on Street?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 2021. Brightest Position on Street cover?: LeetCode 2021. Brightest Position on Street is tagged Array, Ordered Set, Prefix Sum and Sorting on LeetCode.
Is LeetCode 2021. Brightest Position on Street a premium problem?: Yes. LeetCode 2021. Brightest Position on Street is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.