Watch 2 video solutions for Count Positions on Street With Required Brightness, a medium level problem involving Array, Prefix Sum. This walkthrough by LetsCode has 195 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 105Problem 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.
| 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 |