Count Positions on Street With Required Brightness - Solution & Explanation
Problem Statement
You are given an integer n. A perfectly straight street is represented by a number line ranging from 0 to n - 1. You are given a 2D integer array lights representing the street lamp(s) on the street. Each lights[i] = [positioni, rangei] indicates that there is a street lamp at position positioni that lights up the area from [max(0, positioni - rangei), min(n - 1, positioni + rangei)] (inclusive).
The brightness of a position p is defined as the number of street lamps that light up the position p. You are given a 0-indexed integer array requirement of size n where requirement[i] is the minimum brightness of the ith position on the street.
Return the number of positions i on the street between 0 and n - 1 that have a brightness of at least requirement[i].
Example 1:
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). - The second street lamp lights up the area from [max(0, 2 - 1), min(n - 1, 2 + 1)] = [1, 3] (inclusive). - The third street lamp lights up the area from [max(0, 3 - 2), min(n - 1, 3 + 2)] = [1, 4] (inclusive). - Position 0 is covered by the first street lamp. It is covered by 1 street lamp which is greater than requirement[0]. - Position 1 is covered by the first, second, and third street lamps. It is covered by 3 street lamps which is greater than requirement[1]. - Position 2 is covered by the second and third street lamps. It is covered by 2 street lamps which is greater than requirement[2]. - Position 3 is covered by the second and third street lamps. It is covered by 2 street lamps which is less than requirement[3]. - Position 4 is covered by the third street lamp. It is covered by 1 street lamp which is equal to requirement[4]. Positions 0, 1, 2, and 4 meet the requirement so we return 4.
Example 2:
Input: n = 1, lights = [[0,1]], requirement = [2] Output: 0 Explanation: - The first street lamp lights up the area from [max(0, 0 - 1), min(n - 1, 0 + 1)] = [0, 0] (inclusive). - Position 0 is covered by the first street lamp. It is covered by 1 street lamp which is less than requirement[0]. - We return 0 because no position meets their brightness requirement.
Constraints:
1 <= n <= 1051 <= lights.length <= 1050 <= positioni < n0 <= rangei <= 105requirement.length == n0 <= requirement[i] <= 105
Approach Overview
Problem Overview: You are given a street with n positions. Each lamp illuminates a range around its position, increasing brightness by 1 for every covered index. An array requirement defines the minimum brightness needed at each position. The task is to count how many positions meet or exceed their required brightness after all lamps are applied.
Approach 1: Direct Simulation (Brute Force) (Time: O(n * m), Space: O(n))
The most straightforward approach simulates every lamp's effect directly. For each lamp, compute its illumination range [max(0, pos - range), min(n-1, pos + range)] and increment brightness for every position in that interval. After processing all lamps, iterate through the brightness array and count indices where brightness[i] >= requirement[i]. This approach is easy to implement but inefficient when many lamps cover large ranges because each lamp may update up to O(n) positions.
Approach 2: Difference Array + Prefix Sum (Time: O(n + m), Space: O(n))
A more efficient solution uses the difference array technique from Prefix Sum. Instead of updating every position in a lamp's range, mark only the boundaries. For a lamp covering [l, r], increment diff[l] and decrement diff[r + 1]. After processing all lamps, compute the prefix sum over diff to reconstruct the final brightness at each position. This converts many range updates into constant-time operations.
The key insight: each lamp contributes +1 brightness to a continuous interval. Difference arrays allow you to represent these interval updates without touching every element. Once the prefix sum is built, compare each computed brightness value with requirement[i] and count valid positions. This method leverages properties of Array processing and cumulative sums to reduce complexity dramatically.
Recommended for interviews: The difference array + prefix sum solution is the expected approach. Brute force demonstrates baseline reasoning but scales poorly. Interviewers typically look for the interval-update optimization using prefix sums because it reduces the complexity from O(n * m) to O(n + m) and shows strong understanding of range update techniques.
Solution
To add a value v to a continuous interval [i, j] simultaneously, we can use a difference array.
We define an array d of length n + 1. For each streetlight, we calculate its left boundary i = max(0, p - r) and right boundary j = min(n - 1, p + r), then add 1 to d[i] and subtract 1 from d[j + 1].
Next, we perform a prefix sum operation on d. For each position i, if the prefix sum of d[i] is greater than or equal to requirement[i], it means that the position meets the requirement, and we increment the answer by one.
Finally, return the answer.
The time complexity is O(n), and the space complexity is O(n), where n is the number of streetlights.
Code
Python
Java
C++
Go
TypeScript
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Simulation (Brute Force) | O(n * m) | O(n) | Useful for understanding the problem or when lamp ranges are extremely small |
| Difference Array + Prefix Sum | O(n + m) | O(n) | Best for large inputs with many range updates |
Video Solution
Leetcode 2237. Count Positions on Street With Required Brightness (1d difference array) • LetsCode • 214 views views
Frequently Asked Questions
Is Count Positions on Street With Required Brightness easy or hard?
Count Positions on Street With Required Brightness Python/Java solution
How to solve Count Positions on Street With Required Brightness in O(n)?
What is the best approach for Count Positions on Street With Required Brightness?
Is Count Positions on Street With Required Brightness asked at Google/Amazon/Meta?
What data structure is used in Count Positions on Street With Required Brightness?
What is the time complexity of Count Positions on Street With Required Brightness?
Ready to solve this problem?
Practice Count Positions on Street With Required Brightness with our built-in code editor and test cases.
Practice on FleetCode