Minimum Lights to Illuminate a Road - Video Solutions
Leetcode 3964 | Minimum Lights to Illuminate a Road | Greedy | Biweekly contest 185
Minimum Lights to Illuminate a Road - Video Solution
Watch 4 video solutions for Minimum Lights to Illuminate a Road, a medium level problem involving Array, Prefix Sum. This walkthrough by CodeWithMeGuys has 271 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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, wherev > 0, there is a working bulb at positionithat illuminates every position frommax(0, i - v)tomin(n - 1, i + v), inclusive. - If
lights[i] = 0, there is no working bulb at positioni.
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 <= 1050 <= 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.
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 |