Light the Whole Street With Fewest Bulbs
Updated
Problem statement
A street has n positions in a row, numbered 0 to n - 1, with one bulb at each position. street[i] = 1 means the bulb at position i works, and street[i] = 0 means it is broken. A working bulb that is switched on lights its own position and every position up to k steps to its left and to its right: positions i - k to i + k that exist. A broken bulb gives no light, but its position still has to be lit.
This problem has two parts, answered by one number:
- Can the whole street be lit, even with every working bulb switched on? If not, return
-1. - If it can, return the fewest working bulbs that must be switched on so that every position is lit.
Function
minBulbs(street: int[], k: int) → intExamples
Example 1
street = [0,0,1,0,1,1,0,0,1,0]k = 2return = 3Working bulbs stand at positions 2, 4, 5 and 8, and each lights 2 steps to each side. The bulb at 2 lights 0 to 4, and the bulb at 8 lights 6 to 9, leaving position 5 dark; the bulb at 5 lights 3 to 7, which fills the gap. So 3 bulbs (2, 5, 8) light the whole street. Two cannot: only the bulb at 2 reaches position 0 and only the bulb at 8 reaches position 9, and those two leave 5 dark. The answer is 3.
Example 2
street = [1,0,0,0,0,1]k = 1return = -1The bulb at position 0 lights positions 0 and 1, and the bulb at position 5 lights 4 and 5. Positions 2 and 3 stay dark even with every working bulb on, so the street cannot be lit: the answer is -1.
Example 3
street = [1,1,1]k = 0return = 3With k = 0 a bulb lights only its own position, so every position needs its own working bulb, and all three must be on.
Constraints
1 <= street.length <= 10^4- each
street[i]is0or1 0 <= k <= street.length
More Adobe Phone Screen questions
- Evaluate a Parenthesized Integer ExpressionPHONE SCREEN · Seen Oct 2026
- All Elements of Two BSTs in OrderPHONE SCREEN · Seen Aug 2026
- Rotate an Array In PlaceOA · PHONE SCREEN · Seen Aug 2026
- Binary Tree Level-Order Traversal by LevelsPHONE SCREEN · ONSITE INTERVIEW · Seen Aug 2026
- Count Occurrences in a Sorted ArrayPHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2026
- Count Pairs with Absolute Difference KPHONE SCREEN · Seen Jul 2026
- Count Subsets with Sum KPHONE SCREEN · Seen Jul 2026
- Numbers with Exactly Three DivisorsPHONE SCREEN · Seen Jul 2026
- Sum of Even Nodes on a Path in a Numbered Binary TreePHONE SCREEN · Seen Jul 2026
- Largest Value in Every Sliding WindowPHONE SCREEN · Seen Jul 2026
Similar questions at other companies
- Tennis Court SchedulingAtlassian · PHONE SCREEN · ONSITE INTERVIEWAtlassian interview questions
- Jump GamePaytm · PHONE SCREENPaytm interview questions
- Maximum Number of Events That Can Be AttendedByteDance · PHONE SCREENByteDance interview questions
- Remove the Fewest Magic BeansThe D.E. Shaw Group · PHONE SCREENThe D.E. Shaw Group interview questions
- Gas Station CircuitAngel One · PHONE SCREEN
- Aggressive CowsAmazon · PHONE SCREEN
- Minimum Cost for a Target WeightPace Stock Broking Services · PHONE SCREEN
- Defer Expenses to Preserve BalanceDRW · PHONE SCREENDRW interview questions
- Container With Most WaterEPAM · PHONE SCREENEPAM interview questions
- Task Scheduler with CooldownTeradata · PHONE SCREEN
Interview reports that mention this question
Adobe interview experiences
- Adobe Web, QA, DevOps, ML Roles: 13 Experiences (Part 3 of 3)
- Adobe SWE Interviews, Level Unknown: 25 Experiences (Part 2 of 3)
- Adobe Interviews, Level Unknown: 38 Experiences (Part 1 of 3)
- Adobe New Grad MTS Interview Questions: 7 Experiences
- Adobe ML/Research Intern Interviews: 12 Experiences (Part 4 of 4)