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] <= 105To 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.
Java
C++
Go
TypeScript
Top K Frequent Elements - Bucket Sort - Leetcode 347 - Python • NeetCode • 665,789 views views
Watch 9 more video solutions →Practice Count Positions on Street With Required Brightness with our built-in code editor and test cases.
Practice on FleetCode