3964. Minimum Lights to Illuminate a Road Solution

The problem

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 <= 10⁵
0 <= lights[i] <= n

Approach overview

Problem Overview: You are given a road represented as an array where some positions can host a light. Each light illuminates a fixed range around its position. The task is to choose the minimum number of lights so every road segment is covered, or return -1 if full illumination is impossible.

Approach 1: Brute Force Coverage Simulation (O(n^2) time, O(1) space)

Start from the leftmost dark position and check every candidate light within its coverage window. For each possible light position, simulate turning it on and mark the range it illuminates. Move forward to the next uncovered position and repeat. This approach directly follows the problem definition but repeatedly scans overlapping ranges, which leads to quadratic time in the worst case. It is useful for understanding the coverage rules but becomes slow for large roads.

Approach 2: Greedy Farthest Reach (O(n) time, O(1) space)

The optimal strategy is greedy: always activate the light that covers the current dark position and extends coverage the farthest to the right. When you are at index i, look within the valid window [i - B + 1, i + B - 1] for a working light. Choose the rightmost available light because it maximizes the next illuminated boundary. After turning it on, jump directly to the first position beyond its coverage. This works because any earlier light would produce strictly smaller coverage, which could only increase the total number of lights needed. The algorithm scans the road once while adjusting the search window, making it linear time.

Approach 3: Interval Coverage Interpretation (O(n log n) time, O(n) space)

Each valid light can be viewed as an interval [i - B + 1, i + B - 1]. Generate all such intervals for positions where a light can be installed. Sort intervals by their start point and greedily select the interval that extends coverage the farthest while still covering the current position. This mirrors the classic interval covering problem often seen with greedy algorithms and interval problems. While conceptually clean, sorting adds extra overhead compared with the direct linear scan.

Recommended for interviews: The greedy farthest‑reach solution is what interviewers expect. It demonstrates that you recognize this as a coverage optimization problem similar to interval scheduling. Mentioning the brute force method first shows you understand the constraints, but implementing the O(n) greedy scan over the array demonstrates strong problem‑solving instincts and optimal complexity.

Solution

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 0s, 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.

Python

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

Java

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;
    }
}

C++

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;
    }
};

TypeScript

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;
}

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
}

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Coverage Simulation	O(n^2)	O(1)	Useful for understanding the problem or validating small test cases
Interval Coverage with Sorting	O(n log n)	O(n)	When modeling lights as intervals or explaining greedy interval coverage
Greedy Farthest Reach	O(n)	O(1)	Optimal solution for interviews and production implementations

Frequently asked questions

Is Minimum Lights to Illuminate a Road easy or hard?

The problem is typically rated Medium. The challenge is recognizing the greedy property that choosing the farthest‑reaching light always leads to an optimal solution. Once that insight is clear, the implementation is straightforward.

Minimum Lights to Illuminate a Road Python/Java solution

The standard implementation iterates through the array, finds the rightmost valid lamp in the current coverage window, increments the light count, and jumps forward to the next uncovered index. The same greedy logic translates directly to Python, Java, or C++ with linear time complexity.

How to solve Minimum Lights to Illuminate a Road in O(n)?

Iterate from the leftmost road position and search within the valid lamp window for the rightmost available light. Turn that light on and jump to the first index outside its illumination range. Repeat until the entire road is covered. This greedy jump strategy ensures linear time complexity.

What is the best approach for Minimum Lights to Illuminate a Road?

The optimal method is a greedy farthest‑reach strategy. While scanning the road, choose the rightmost light that still covers the current dark position. This maximizes coverage and minimizes the number of lights required. The approach runs in O(n) time with O(1) extra space.

Is Minimum Lights to Illuminate a Road asked at Google/Amazon/Meta?

Variations of this problem appear in interviews at companies like Amazon and Google because it tests greedy reasoning and interval coverage thinking. Interviewers often frame it as placing minimum lamps, Wi‑Fi routers, or transmitters along a line.

What data structure is used in Minimum Lights to Illuminate a Road?

The problem mainly relies on arrays and greedy scanning. Some explanations model each lamp as an interval and use sorting with interval selection logic, but the optimal solution works directly on the array with index pointers.

What is the time complexity of Minimum Lights to Illuminate a Road?

The optimal greedy solution runs in O(n) time because each road position is processed at most once while extending coverage. Space complexity is O(1) since the algorithm only tracks indices and the current coverage range. Brute force approaches can take O(n^2).

Minimum Lights to Illuminate a Road solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Minimum Lights to Illuminate a Road solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems