Prerequisites
Before attempting this problem, you should be comfortable with:
- Arrays - Understanding how to traverse and manipulate array elements
- Sliding Window Technique - Maintaining a dynamic window over a contiguous subarray while tracking specific conditions
- Two Pointers - Using left and right pointers to efficiently process subarrays without nested iteration
- Prefix Sum - Precomputing cumulative sums to enable O(1) range queries
- Binary Search - Finding target values or boundaries in sorted data in O(log n) time
1. Brute Force
Intuition
The most straightforward approach is to check every possible starting position and see how far we can extend while flipping at most k zeros. For each starting index, we move forward and count zeros. Once the count exceeds k, we stop and record the window length. This method explores all contiguous subarrays but performs redundant work by rescanning overlapping regions.
Algorithm
- Initialize
resto store the maximum length found. - For each starting index
l, set a zero countercntto0and expand with pointerr:- If the current element is
0andcntalready equalsk, stop expanding. - Otherwise, if the element is
0, incrementcnt. - Move
rforward.
- If the current element is
- After the inner loop, update
reswithr - l. - Return
resafter checking all starting positions.
Time & Space Complexity
- Time complexity:
- Space complexity:
2. Binary Search + Prefix Sum
Intuition
We can precompute a prefix sum array that counts zeros up to each index. For any subarray from l to r, the number of zeros is simply prefix[r + 1] - prefix[l]. This allows us to quickly check if a window is valid (contains at most k zeros). For each starting position, we binary search for the farthest ending position where the zero count stays within the limit. This avoids the linear scan of the brute force approach.
Algorithm
- Build a prefix sum array where
prefix[i]stores the count of zeros innums[0..i-1]. - For each starting index
l, binary search for the largestrsuch thatprefix[r + 1] - prefix[l] <= k. - Update
reswithr - l(the window length). - Return
resafter processing all starting positions.
class Solution:
def longestOnes(self, nums: List[int], k: int) -> int:
prefix = [0]
for num in nums:
prefix.append(prefix[-1] + (1 if num == 0 else 0))
res = 0
for l in range(len(nums)):
low, high = l, len(nums)
while low < high:
mid = (low + high) // 2
if prefix[mid + 1] - prefix[l] <= k:
low = mid + 1
else:
high = mid
res = max(res, low - l)
return resTime & Space Complexity
- Time complexity:
- Space complexity:
3. Sliding Window
Intuition
A sliding window provides the optimal approach. We maintain a window that can contain at most k zeros. As we expand the right boundary, we decrement k for each zero encountered. When k goes negative, the window has too many zeros, so we shrink from the left until the window is valid again. The maximum window size seen during this process is our answer. Each element is processed at most twice, yielding linear time complexity.
Algorithm
- Initialize
l(left pointer) andres(result) to0. - Iterate through the array with
r(right pointer):- If
nums[r]is0, decrementk. - While
k < 0(window is invalid):- If
nums[l]is0, incrementk(restore the flip allowance). - Move
lforward.
- If
- Update
reswithr - l + 1.
- If
- Return
res.
Time & Space Complexity
- Time complexity:
- Space complexity:
Common Pitfalls
Modifying k Without Restoring It
When using k directly as a counter (decrementing when encountering zeros), remember that this mutates the input parameter. If you need to use k again later or if the problem requires preserving it, use a separate variable. Additionally, when shrinking the window, you must restore k by incrementing it when a zero leaves the window.
Incorrect Window Shrinking Condition
The window should shrink when k < 0, meaning we have flipped more zeros than allowed. A common mistake is using k == 0 as the shrinking condition, which prevents the window from ever containing k zeros. The window is valid as long as k >= 0; only shrink when it becomes negative.
Forgetting to Handle Edge Cases
When k equals or exceeds the number of zeros in the array, the answer is simply the length of the entire array. While the sliding window approach handles this naturally, the brute force approach might have issues if not carefully implemented. Also, handle the case when the array is empty or contains only ones.