MediumNo. 2237LeetCode Premium
Count Positions on Street With Required Brightness — LeetCode 2237 Python Solution
- Pattern
- Prefix Sum
- Topics
- Array, Prefix Sum
- Reading time
- 3 min
- Source
- leetcode.com
The problem
You are given an integer n. A perfectly straight street is represented by a number line ranging from 0 to n - 1.
Example
- Input
- n = 5, lights = [[0,1],[2,1],[3,2]], requirement = [0,2,1,4,1]
- Output
- 4
- Explanation
- - The first street lamp lights up the area from [max(0, 0 - 1), min(n - 1, 0 + 1)] = [0, 1] (inclusive).
Python solution
class Solution:
def meetRequirement(
self, n: int, lights: List[List[int]], requirement: List[int]
) -> int:
d = [0] * (n + 1)
for p, r in lights:
i, j = max(0, p - r), min(n - 1, p + r)
d[i] += 1
d[j + 1] -= 1
return sum(s >= r for s, r in zip(accumulate(d), requirement))Complexity
- Time
- O(n)
- Space · auxiliary
- O(n)where n is the number of streetlights
Pattern: Prefix Sum
Precompute running totals once so any range query becomes a single subtraction. LeetCode 2237. Count Positions on Street With Required Brightness 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 |
|---|---|---|
| 2245 | Maximum Trailing Zeros in a Cornered Path | 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 |
| 0798 | Smallest Rotation with Highest Score | Hard |
Frequently asked questions
- How hard is LeetCode 2237. Count Positions on Street With Required Brightness?
LeetCode 2237. Count Positions on Street With Required Brightness is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2237. Count Positions on Street With Required Brightness?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 2237. Count Positions on Street With Required Brightness?
The Python solution on this page uses O(n), where n is the number of streetlights auxiliary space.
- What topics does LeetCode 2237. Count Positions on Street With Required Brightness cover?
LeetCode 2237. Count Positions on Street With Required Brightness is tagged Array and Prefix Sum on LeetCode.
- Is LeetCode 2237. Count Positions on Street With Required Brightness a premium problem?
Yes. LeetCode 2237. Count Positions on Street With Required Brightness is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.