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.

Count Positions on Street With Required Brightness — LeetCode 2237 Python Solution

MediumLeetCode PremiumArrayPrefix Sum

Problem: #2237
Pattern: 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

Python

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

Measure	Complexity
Time	O(n)
Space	O(n), where n is the number of streetlights auxiliary

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.

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.