Funcia
Lv.1arraysliding-windowtwo-pointers

Longest Ones with One Flip

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
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

bitsresult
[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

  • 1≤1 \le bits.length ≤500,000\le 500{,}000
  • bits[i] is 0 or 1.

Expected complexity

Time
O(N)
Space
O(1)

Examples

bitsExpected
[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: O(N)O(N) 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 O(N2)O(N^2) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251062 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4012verdict only
performance603verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.