Count positions on street with required brightness

Array Prefix Sum

63.0% acceptance

Mar 31, 2026

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].

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

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![0i32; n + 1];
    for light in &lights {
      let pos = light[0] as usize;
      let range = light[1] as usize;
      let left = pos.saturating_sub(range);
      let right = std::cmp::min(pos + range, n - 1);
      diff[left] += 1;
      if right + 1 <= n {
        diff[right + 1] -= 1;
      }
    }
    let mut brightness = 0i32;
    let mut count = 0;
    for i in 0..n {
      brightness += diff[i];
      if brightness >= requirement[i] {
        count += 1;
      }
    }
    count
  }
}