Skip to content

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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;
}

Comments