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 ().
Outputs:
- An integer representing the length of the longest valid subarray after flipping up to
Kzeros.
Implicit Constraints & Edge Cases:
- The array contains only 0s and 1s (no negatives or other integers).
- If , we are simply finding the max consecutive ones without any flips.
- Since
A.lengthcan be up to 20k, an or even 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 or requires precomputation. Iterating all windows is . Given constraints (), this will likely exceed time limits (usually ~1 second allows 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 time complexity.
Approach
- Initialize
left = 0,zero_count = 0, andmax_len = 0. - Iterate with
rightfrom index 0 to the end of array:- If
A[right] == 0, incrementzero_count.
- If
- Check if we have exceeded our allowed flips (
K). Whilezero_count > K:- Move
leftforward. - Decrement
zero_countonly ifA[left]was a zero (since that’s the one leaving the window).
- Move
- At each valid step, calculate current window size:
right - left + 1. Updatemax_lenwith this value. - Return
max_len.
Complexity Analysis
- Time Complexity: . Both
leftandrightpointers 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: . 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
whileloop 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 because once 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_countstays 0, window grows to full length . Returns . - K equals Array Length: Condition
while zero_count > Knever 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 K. Since we can flip up to K, any subarray with zeros is valid. - Empty/Single Element: Constraints state , so empty array not possible per spec. Single element handled correctly by loop logic (len 0 or 1).