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

Description Hints 3 Solution Video 22:44

3964. Minimum Lights to Illuminate a Road

Medium37.8% acceptance

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

Topics

Array Prefix Sum

Hints open one at a time

Hint 1

First mark all positions already visible from the existing working bulbs.

Hint 2

Then scan the road from left to right. Whenever you find the first invisible position i, install a new bulb as far right as possible while still covering i.

Hint 3

Since each additional bulb covers distance 1, the best position is usually i + 1, unless it goes out of bounds. After placing it, skip all positions it covers.

22:44

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def minLights(self, lights: list[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[0,0,0,0]

Input

[0,0,0,2,0]

Your code is saved on this device.Solution