168. Drop One, Keep Ones
A row of lamps is described by the array bits, where 1 means a lamp is on and 0 means it is off. A technician must remove exactly one lamp from the row, and the lamps on both sides of the removed one close up the gap and become neighbors.
After the removal, the technician looks for the longest unbroken stretch of lamps that are all on. Return the length of the longest stretch of consecutive 1 values that can be left in the row after deleting exactly one element. If no such stretch exists, return 0. You must delete one element even if the row is already all ones.
Example 1
- Input:
- bits = [1,1,0,1,1,1,0,1]
- Output:
- 5
- Explanation:
Deleting the 0 at index 2 joins the runs 1,1 and 1,1,1 into a run of 5 ones, and no other deletion does better, so the answer is 5.
Example 2
- Input:
- bits = [1,1,1]
- Output:
- 2
- Explanation:
The row is all ones, but one element must still be deleted, which leaves a run of 2.
Example 3
- Input:
- bits = [0,0,0]
- Output:
- 0
- Explanation:
There are no ones at all, so whatever is deleted, no run of ones exists and the answer is 0.
Constraints
1 ≤ bits.length ≤ 105
bits[i] is 0 or 1
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)