Count Positions on Street With Required Brightness

Problem

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 positionsi on the street between0 andn - 1 _that have abrightness _ofat least requirement[i].

Examples

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 <= 10^5
• 1 <= lights.length <= 10^5
• 0 <= positioni < n
• 0 <= rangei <= 10^5
• requirement.length == n
• 0 <= requirement[i] <= 10^5

Solution

Method 1 – Prefix Sum (Difference Array)

Intuition

To efficiently compute the brightness at each position, we use a difference array to mark the effect of each lamp's range, then take a prefix sum to get the brightness at each position. This allows us to process all lamps in O(n + m) time.

Approach

1. Initialize a difference array of size n+1 to 0.
2. For each lamp [pos, rng]:
   1. Add 1 at max(0, pos - rng).
   2. Subtract 1 at min(n, pos + rng + 1).
3. Compute the prefix sum to get the brightness at each position.
4. For each position i, if brightness[i] >= requirement[i], increment the answer.
5. Return the answer.

Code

C++

class Solution {
public:
    int meetRequirement(int n, vector<vector<int>>& lights, vector<int>& requirement) {
        vector<int> diff(n+1, 0);
        for (auto& l : lights) {
            int lft = max(0, l[0] - l[1]), rgt = min(n-1, l[0] + l[1]);
            diff[lft]++;
            if (rgt+1 < n) diff[rgt+1]--;
        }
        int ans = 0, cur = 0;
        for (int i = 0; i < n; ++i) {
            cur += diff[i];
            if (cur >= requirement[i]) ans++;
        }
        return ans;
    }
};

Go

func meetRequirement(n int, lights [][]int, requirement []int) int {
    diff := make([]int, n+1)
    for _, l := range lights {
        lft := l[0] - l[1]
        if lft < 0 { lft = 0 }
        rgt := l[0] + l[1]
        if rgt >= n { rgt = n-1 }
        diff[lft]++
        if rgt+1 < n { diff[rgt+1]-- }
    }
    ans, cur := 0, 0
    for i := 0; i < n; i++ {
        cur += diff[i]
        if cur >= requirement[i] { ans++ }
    }
    return ans
}

Java

class Solution {
    public int meetRequirement(int n, int[][] lights, int[] requirement) {
        int[] diff = new int[n+1];
        for (int[] l : lights) {
            int lft = Math.max(0, l[0] - l[1]), rgt = Math.min(n-1, l[0] + l[1]);
            diff[lft]++;
            if (rgt+1 < n) diff[rgt+1]--;
        }
        int ans = 0, cur = 0;
        for (int i = 0; i < n; i++) {
            cur += diff[i];
            if (cur >= requirement[i]) ans++;
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun meetRequirement(n: Int, lights: Array<IntArray>, requirement: IntArray): Int {
        val diff = IntArray(n+1)
        for (l in lights) {
            val lft = maxOf(0, l[0] - l[1])
            val rgt = minOf(n-1, l[0] + l[1])
            diff[lft]++
            if (rgt+1 < n) diff[rgt+1]--
        }
        var ans = 0; var cur = 0
        for (i in 0 until n) {
            cur += diff[i]
            if (cur >= requirement[i]) ans++
        }
        return ans
    }
}

Python

class Solution:
    def meetRequirement(self, n: int, lights: list[list[int]], requirement: list[int]) -> int:
        diff = [0] * (n+1)
        for pos, rng in lights:
            lft = max(0, pos - rng)
            rgt = min(n-1, pos + rng)
            diff[lft] += 1
            if rgt+1 < n:
                diff[rgt+1] -= 1
        ans = cur = 0
        for i in range(n):
            cur += diff[i]
            if cur >= requirement[i]:
                ans += 1
        return ans

Rust

impl Solution {
    pub fn meet_requirement(n: i32, lights: Vec<Vec<i32>>, requirement: Vec<i32>) -> i32 {
        let n = n as usize;
        let mut diff = vec![0; n+1];
        for l in &lights {
            let lft = l[0] - l[1];
            let lft = if lft < 0 { 0 } else { lft } as usize;
            let rgt = l[0] + l[1];
            let rgt = if rgt >= n as i32 { n as i32 - 1 } else { rgt } as usize;
            diff[lft] += 1;
            if rgt+1 < n { diff[rgt+1] -= 1; }
        }
        let mut ans = 0;
        let mut cur = 0;
        for i in 0..n {
            cur += diff[i];
            if cur >= requirement[i] { ans += 1; }
        }
        ans as i32
    }
}

TypeScript

class Solution {
    meetRequirement(n: number, lights: number[][], requirement: number[]): number {
        const diff = Array(n+1).fill(0);
        for (const [pos, rng] of lights) {
            const lft = Math.max(0, pos - rng);
            const rgt = Math.min(n-1, pos + rng);
            diff[lft]++;
            if (rgt+1 < n) diff[rgt+1]--;
        }
        let ans = 0, cur = 0;
        for (let i = 0; i < n; i++) {
            cur += diff[i];
            if (cur >= requirement[i]) ans++;
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n + m), where n is the number of positions and m is the number of lights.
• 🧺 Space complexity: O(n), for the difference array.