Lv.1arraysliding-windowtwo-pointers
Longest Ones with One Flip
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
Given an array bits of 0s and 1s, you may change at most one 0 into a 1. Return the maximum length of a
contiguous run of 1s afterwards.
Examples
| bits | result |
|---|---|
[1, 0, 1, 1, 0] | 4 |
[1, 1, 1] | 3 |
[0, 0, 0] | 1 |
Example 1 — flipping the 0 at index 1 gives [1, 1, 1, 1, 0].
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(bits: int[]) → int
Constraints
-
bits.length bits[i]is0or1.
Expected complexity
- Time
- O(N)
- Space
- O(1)
Examples
| bits | Expected |
|---|---|
[1,0,1,1,0] | 4 |
[1,1,1] | 3 |
[0,0,0] | 1 |
Hint
Hint
The answer is the longest window containing at most one 0. Grow the right end, count zeros in the window, and move the
left end forward while there are two: because both ends only move forward. Equivalently, remember the current run of
ones and the run just before the last zero. Flipping each zero and rescanning is and exceeds the time limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1062 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 12 | verdict only |
| performance | 60 | 3 | verdict only |