Domain 2MediumMEDIUM

Max Consecutive Ones III

Find the longest subarray of 0s and 1s where at most K zeros are flipped to ones using a sliding window technique for O(N) time complexity.

Domain: medium•Updated: 2026-09-06
#sliding window#two pointers#O(N)#O(1)

Problem Breakdown

We need to find the length of the longest contiguous subarray that contains only 1s after flipping up to K zeros. This is equivalent to finding the maximum window size where the count of zeros does not exceed K.

Inputs:

  • A: List of integers (0 or 1). Length between 1 and 20,000.
  • K: Integer representing the maximum number of flips allowed (0≤K≤A.length0 \le K \le A.length).

Outputs:

  • An integer representing the length of the longest valid subarray after flipping up to K zeros.

Implicit Constraints & Edge Cases:

  • The array contains only 0s and 1s (no negatives or other integers).
  • If K=0K=0, we are simply finding the max consecutive ones without any flips.
  • Since A.length can be up to 20k, an O(N3)O(N^3) or even O(N2)O(N^2) solution will time out on large inputs (e.g., LeetCode’s hidden test cases). We need linear time.

Intuition

Let’s start with a naive approach: iterate through every possible subarray [i, j], count the zeros inside it, and check if count <= K. Counting zeros for each window takes O(N)O(N) or requires precomputation. Iterating all windows is O(N2)O(N^2). Given constraints (N=20kN=20k), this will likely exceed time limits (usually ~1 second allows ≈108\approx 10^8 ops, but Python overhead makes it stricter).

Key Insight: Notice that as we expand the right boundary of our window (right pointer), if the number of zeros exceeds K, we must shrink the window from the left to reduce zero count. We never need to move the left pointer backwards because adding elements only increases or maintains the zero count; removing them decreases it monotonically. This monotonic behavior allows us to use a Sliding Window (Two Pointers) technique where both pointers only increment, resulting in O(N)O(N) time complexity.

Approach

  1. Initialize left = 0, zero_count = 0, and max_len = 0.
  2. Iterate with right from index 0 to the end of array:
    • If A[right] == 0, increment zero_count.
  3. Check if we have exceeded our allowed flips (K). While zero_count > K:
    • Move left forward.
    • Decrement zero_count only if A[left] was a zero (since that’s the one leaving the window).
  4. At each valid step, calculate current window size: right - left + 1. Update max_len with this value.
  5. Return max_len.

Complexity Analysis

  • Time Complexity: O(N)O(N). Both left and right pointers traverse the array at most once from start to finish. Each element is accessed a constant number of times (amortized analysis for the inner while loop).
  • Space Complexity: O(1)O(1). We only use integer variables for counting indices and lengths, regardless of input size.

Solution

def longestOnes(A: list[int], K: int) -> int:
    left = 0
    zero_count = 0
    max_len = 0
    
    # Sliding window expansion with right pointer
    for right in range(len(A)):
        if A[right] == 0:
            zero_count += 1
        
        # Shrink window from the left until we are within K flips limit
        while zero_count > K:
            if A[left] == 0:
                zero_count -= 1
            left += 1
            
        # Update max length found so far
        current_len = right - left + 1
        if current_len > max_len:
            max_len = current_len
            
    return max_len

Edge Cases Handled

  • K=0: The while loop ensures we shrink until zero_count is 0, effectively finding the longest sequence of existing ones.
  • All Zeros with K < N: Window expands to include exactly K zeros then shrinks; returns min⁡(N,K)\min(N, K) because once NN exceeds available flips for a window of all zeros, length is capped by remaining valid windows (e.g., [0,0], K=1 -> len 1).
  • All Ones: zero_count stays 0, window grows to full length NN. Returns NN.
  • K equals Array Length: Condition while zero_count > K never triggers (since max zeros is N <= K if all zeros? No. If array has Zeros and K >= TotalZeros). Window expands fully regardless of content as long as total zeros in window ≤\le K. Since we can flip up to K, any subarray with ≤K\le K zeros is valid.
  • Empty/Single Element: Constraints state 1≤A.length1 \le A.length, so empty array not possible per spec. Single element handled correctly by loop logic (len 0 or 1).