Welcome to Subscribe On Youtube

3964. Minimum Lights to Illuminate a Road

Description

You are given an integer array lights of length n, representing positions 0 through n - 1 on a road.

For each position i:

• If lights[i] = v, where v > 0, there is a working bulb at position i that illuminates every position from max(0, i - v) to min(n - 1, i + v), inclusive.
• If lights[i] = 0, there is no working bulb at position i.

A position is visible if it is illuminated by at least one working bulb.

You may install additional bulbs at any positions. Each additional bulb installed at position j illuminates positions from max(0, j - 1) to min(n - 1, j + 1), inclusive.

Return the minimum number of additional bulbs required to make every position on the road visible.

 

Example 1:

Input: lights = [0,0,0,0]

Output: 2

Explanation:

One optimal placement is:

• Install an additional bulb at position 1, illuminating positions [0, 1, 2].
• Install an additional bulb at position 3, illuminating positions [2, 3].

Therefore, the minimum number of additional bulbs required is 2.

Example 2:

Input: lights = [0,0,0,2,0]

Output: 1

Explanation:

• Since lights[3] = 2, the working bulb at position 3 illuminates positions [1, 2, 3, 4].
• Installing an additional bulb at position 1 illuminates positions [0, 1, 2], making every position visible.
• Therefore, the minimum number of additional bulbs required is 1.

 

Constraints:

• 1 <= n == lights.length <= 105
• 0 <= lights[i] <= n

Solutions

Solution 1: Difference Array + Prefix Sum

We notice that for each position $i$, if $lights[i] = v$ where $v > 0$, then position $i$ is illuminated, and the illumination range is $[i - v, i + v]$. We can use a difference array to maintain the illumination range at each position.

We define an array $d$ of length $n$. For each position $i$, if $lights[i] = v$ where $v > 0$, we add $1$ to $d[i - v]$ and subtract $1$ from $d[i + v + 1]$.

Then, we compute the prefix sum of $d$ to obtain the illumination status at each position.

Finally, we traverse $d$, find the length of each consecutive segment of $0$s, and if the length is $k$, we need to install $\lceil \frac{k + 2}{3} \rceil$ lights. We accumulate the answer accordingly.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of street lights.

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public int minLights(int[] lights) {
          int n = lights.length;
          int[] d = new int[n];
  
          for (int i = 0; i < n; i++) {
              int v = lights[i];
              if (v > 0) {
                  int l = Math.max(0, i - v);
                  int r = Math.min(n - 1, i + v);
                  d[l]++;
                  if (r + 1 < n) {
                      d[r + 1]--;
                  }
              }
          }
  
          int s = 0, cnt = 0, ans = 0;
          for (int x : d) {
              s += x;
              if (s == 0) {
                  cnt++;
              } else {
                  ans += (cnt + 2) / 3;
                  cnt = 0;
              }
          }
  
          ans += (cnt + 2) / 3;
          return ans;
      }
  }
  

• class Solution {
  public:
      int minLights(vector<int>& lights) {
          int n = lights.size();
          vector<int> d(n);
  
          for (int i = 0; i < n; ++i) {
              int v = lights[i];
              if (v > 0) {
                  int l = max(0, i - v);
                  int r = min(n - 1, i + v);
                  ++d[l];
                  if (r + 1 < n) {
                      --d[r + 1];
                  }
              }
          }
  
          int s = 0, cnt = 0, ans = 0;
          for (int x : d) {
              s += x;
              if (s == 0) {
                  ++cnt;
              } else {
                  ans += (cnt + 2) / 3;
                  cnt = 0;
              }
          }
  
          ans += (cnt + 2) / 3;
          return ans;
      }
  };
  

• class Solution:
      def minLights(self, lights: list[int]) -> int:
          n = len(lights)
          d = [0] * n
          for i, v in enumerate(lights):
              if v > 0:
                  l = max(0, i - v)
                  r = min(n - 1, i + v)
                  d[l] += 1
                  if r + 1 < n:
                      d[r + 1] -= 1
          s = cnt = 0
          ans = 0
          for x in d:
              s += x
              if s == 0:
                  cnt += 1
              else:
                  ans += (cnt + 2) // 3
                  cnt = 0
          ans += (cnt + 2) // 3
          return ans
  
  

• func minLights(lights []int) int {
  	n := len(lights)
  	d := make([]int, n)
  
  	for i, v := range lights {
  		if v > 0 {
  			l := max(0, i-v)
  			r := min(n-1, i+v)
  			d[l]++
  			if r+1 < n {
  				d[r+1]--
  			}
  		}
  	}
  
  	s, cnt, ans := 0, 0, 0
  	for _, x := range d {
  		s += x
  		if s == 0 {
  			cnt++
  		} else {
  			ans += (cnt + 2) / 3
  			cnt = 0
  		}
  	}
  
  	ans += (cnt + 2) / 3
  	return ans
  }
  
  

• function minLights(lights: number[]): number {
      const n = lights.length;
      const d: number[] = Array(n).fill(0);
  
      for (let i = 0; i < n; i++) {
          const v = lights[i];
          if (v > 0) {
              const l = Math.max(0, i - v);
              const r = Math.min(n - 1, i + v);
              d[l]++;
              if (r + 1 < n) {
                  d[r + 1]--;
              }
          }
      }
  
      let s = 0,
          cnt = 0,
          ans = 0;
      for (const x of d) {
          s += x;
          if (s === 0) {
              cnt++;
          } else {
              ans += Math.floor((cnt + 2) / 3);
              cnt = 0;
          }
      }
  
      ans += Math.floor((cnt + 2) / 3);
      return ans;
  }
  
  

All Problems

All Solutions