MediumNo. 2021LeetCode Premium
Brightest Position on Street — LeetCode 2021 Python Solution
- Pattern
- Prefix Sum
- Topics
- Array, Ordered Set, Prefix Sum, Sorting
- 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
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 ansComplexity
- Time
- O(n × log n)
- Space · auxiliary
- O(n)
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.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 2731 | Movement of Robots | Medium |
| 2017 | Grid Game | Medium |
| 0238 | Product of Array Except Self | Medium |
| 0303 | Range Sum Query - Immutable | Easy |
| 0304 | Range Sum Query 2D - Immutable | Medium |
| 0724 | Find Pivot Index | Easy |
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 × 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.