1004. Max Consecutive Ones III
Problem Description
Given an array of binary numbers nums
(i.e., containing only 0
s and 1
s) and an integer k
, the goal is to find the maximum number of consecutive 1
s that can be achieved in the array if you are allowed to flip at most k
0
s to 1
s. A "flip" means changing a 0
to a 1
. The task is to apply these flips in the most optimal way to maximize the length of a continuous segment of 1
s in the array.
For example, if your array is [1,1,0,0,1]
and k
is 1
, the longest sequence of 1
s you can create by flipping at most one 0
is 3
(flip the first 0
and the sequence becomes [1,1,1,0,1]
).
Intuition
The problem hints at a sliding window approach where we iterate over the array while maintaining a window of consecutive numbers which can potentially include up to k
zeroes.
Here's the thinking process behind the solution:
- We aim to find the longest sequence of 1s which may include
k
or fewer flipped 0s. - We initialize two pointers
l
(left) andr
(right) which define the current window. The window starts with no elements (both pointers at-1
). - We iterate through the array with the
r
pointer incremented in each step examining each element. We expand the window by movingr
to the right. - If a
0
is encountered, we decrease the count ofk
because we are envisioning a flip happening here to turn it into a1
for the sake of our current sequence. - If
k
becomes negative, it means our window has too many0
s (more than the allowedk
flips). We need to shrink the window from the left by incrementingl
. Each time we pass a0
while movingl
to the right, we incrementk
back as we are effectively undoing a flip. - Throughout this process, we are implicitly tracking the length of the current window. The maximum length encountered during the iteration is the length of the longest sequence we are looking for.
- The length of the window is always
r - l
, but since our pointers start from-1
, when the right pointer has reached the end of the array (indexlen(nums) - 1
), the window length is simplyr - l
without needing to add one for usual zero-based index arrays.
In the provided code, the final return statement seems incomplete as it doesn't consider the fact that the length of the window should be r - l + 1
. However, considering that the looping mechanism does not immediately stop when k
becomes less than 0
(it needs one more iteration where it could potentially adjust the window size appropriately), the code might yield the correct result through careful pointer manipulation and implicit window size calculation.
Learn more about Binary Search, Prefix Sum and Sliding Window patterns.
Solution Approach
The solution approach uses a two-pointer technique to implement a sliding window algorithm, which is particularly efficient for problems involving contiguous subarrays or subsequences.
Here's a breakdown of the implementation steps and logic:
-
Initialize two pointers,
l
andr
, that will represent the window's left and right boundaries, respectively. The variablesl
andr
both start at-1
because the window is initially empty. -
Iterate over the array with a while loop. The right boundary
r
of the window will increase with each iteration (the window expands to the right) until it reaches the end ofnums
. -
For each number encountered, check if it is a
0
and, if it is, decrementk
. Each timek
is decremented, it's as though we flipped a0
to1
within our current window. We are allowed to have a maximum ofk
such flips. -
When
k
becomes negative (which means the current window has one more0
than allowed), increment the left boundaryl
(the window contracts from the left), and if the leftmost element is a0
, incrementk
again, essentially 'unflipping' that zero. -
The conditional check for
k < 0
doesn't necessarily equate to an else condition following theif nums[r] == 0
; it's a separate check because the sliding window can continue to slide, andk
can go negative at different points in the loop. -
In terms of data structures, the solution does not require anything beyond the basic built-in variables and the array itself. It's the algorithmic pattern (two pointers for the sliding window) that carries the weight of the logic.
-
The length of the window, and thus the maximum number of consecutive
1
's, can always be represented by the differencer - l
. Upon leaving the while loop, sincer
has moved one past the end of the array, the subtraction directly yields the size of the window, without the need for additional adjustment.
It is important to note that the apparent simplicity of the final return r - l
statement may obscure the fact that such a result is valid because of the particular initial conditions for l
and r
and the way the algorithm carefully adjusts the window. An accurate count of the longest stretch of 1
's is maintained throughout the algorithm's execution without a need for an explicit length variable or further calculations.
The code solution effectively exploits the sliding window pattern to perform a single pass through the array, yielding an efficient O(n)
runtime complexity (because each element is visited once) and O(1)
space complexity since no additional data structure is used.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using a small example where the input array is nums = [1, 0, 1, 0, 1, 0, 1]
and k = 2
, meaning we can flip at most 2 0
s to 1
s.
- Initialize two pointers,
l
andr
, to-1
. These will mark the boundaries of our sliding window. - Start iterating over the array. The window will expand as
r
moves to the right. - On each iteration, check each number:
- For
r = 0
,nums[r] = 1
. No action is required since the number is already1
. Window remains the same. - For
r = 1
,nums[r] = 0
. Decrementk
to1
. We're envisioning a flip here so the window can keep growing. - For
r = 2
,nums[r] = 1
. No action, and the window grows further. - For
r = 3
,nums[r] = 0
. Decrementk
to0
. Another envisioned flip and the window continues. - For
r = 4
,nums[r] = 1
. No action required. - For
r = 5
,nums[r] = 0
. Ourk
is now-1
, which means we've exceeded the maximum number of flips permitted. Now we shrink the window froml
.
- For
- While
k
is negative, incrementl
to shrink the window from the left untilk
is no longer negative.- Move
l
from-1
to0
, no change sincenums[0] = 1
. - Move
l
to1
, and sincenums[1] = 0
, incrementk
to0
(unflipping that zero). - The window is still too large (as
k
is0
, not positive), so continue movingl
. - Move
l
to2
. There is no need to adjustk
sincenums[2] = 1
. - Move
l
to3
,k
becomes1
becausenums[3] = 0
, and we 'unflip' it to go back to suit our flip limit.
- Move
- Continue iterating and growing the window to the right.
- For
r = 6
,nums[r] = 1
. No flips needed.
- For
- Iteration ends when
r
has reached the last element.
We've grown and shrunk our window according to the flips we can perform, and we've kept track of the window size implicitly through the difference r - l
. In this example, our largest window size occurs at the end of the iteration: r = 6
, l = 3
, giving us a window length of 6 - 3 = 3
(which is the number of 1
's in a row after flipping at most k
0
's).
So, the maximum number of consecutive 1
s achievable by flipping at most k
0
s is 3
, and the sequence where that happens after flipping is [1, 1, 1, 0, 1, 1, 1]
.
Solution Implementation
1from typing import List
2
3class Solution:
4 def longestOnes(self, nums: List[int], k: int) -> int:
5 # Initialize the left and right pointer to -1
6 left = right = -1
7
8 # Slide the window to the right until the end of the list is reached
9 while right < len(nums) - 1:
10 right += 1 # Move the right pointer to the right
11
12 # If a zero is encountered, decrement k (number of flips allowed)
13 if nums[right] == 0:
14 k -= 1
15
16 # If k is negative, too many zeros have been flipped
17 # thus, move the left pointer to the right
18 if k < 0:
19 left += 1 # Move the left pointer to the right
20
21 # If the left pointer is pointing to a zero, increment k
22 if nums[left] == 0:
23 k += 1
24
25 # The maximum length of subarray with all ones after flipping k zeros is
26 # the difference between the right and left pointers
27 return right - left
28
1class Solution {
2
3 // Method to find the longest continuous segment with '1's after flipping at most 'k' zeroes
4 public int longestOnes(int[] nums, int k) {
5 int left = 0; // Initialize the left pointer of the window
6 int right = 0; // Initialize the right pointer of the window
7 int maxOnesCount = 0; // Variable to store the count of continuous ones
8
9 while (right < nums.length) { // Iterate until the right pointer reaches the end of the array
10 // If the element at the right pointer is 0, we have to use one flip
11 if (nums[right] == 0) {
12 --k;
13 }
14
15 right++; // Move the right pointer to the next element
16
17 // If we have used all our flips, we need to move the left pointer forward to find a new window
18 while (k < 0) {
19 // If we are moving the left pointer over a zero, we can have one more flip available
20 if (nums[left] == 0) {
21 ++k;
22 }
23 left++; // Move the left pointer to the next element
24 }
25
26 // Update the maximum number of continuous ones found
27 maxOnesCount = Math.max(maxOnesCount, right - left);
28 }
29
30 return maxOnesCount; // Return the length of the longest continuous segment of ones possible
31 }
32}
33
1class Solution {
2public:
3 int longestOnes(vector<int>& nums, int k) {
4 int left = 0; // Initialize left pointer
5 int right = 0; // Initialize right pointer
6 int maxOnesLength = 0; // Variable to store the maximum length of subarray
7
8 // Iterate through the array with the right pointer
9 while (right < nums.size()) {
10 // If we encounter a 0, decrement k (the flip count)
11 if (nums[right] == 0) {
12 --k;
13 }
14
15 // Move the right pointer to the next element
16 ++right;
17
18 // If k is negative, it means we've flipped more 0s than allowed
19 while (k < 0) {
20 // If the left element is 0, we increment k
21 // since we are moving past the flipped zero
22 if (nums[left] == 0) {
23 ++k;
24 }
25 // Move the left pointer to the right, effectively shrinking the window
26 ++left;
27 }
28
29 // Update maxOnesLength if the current window is larger
30 maxOnesLength = max(maxOnesLength, right - left);
31 }
32
33 // Return the maximum length of the subarray
34 return maxOnesLength;
35 }
36};
37
1// The function finds the maximum number of consecutive 1's in the array if you
2// can flip at most k 0's to 1's.
3function longestOnes(nums: number[], k: number): number {
4 // Total number of elements in the nums array.
5 const lengthOfNums = nums.length;
6 // Initialize the left pointer for the sliding window.
7 let leftPointer = 0;
8 // Iterate through the nums array.
9 for (const num of nums) {
10 // If we encounter a 0, reduce the count of flips remaining (k).
11 if (num === 0) {
12 k--;
13 }
14 // If k is negative, it means we have flipped more than k 0's.
15 // We need to adjust the leftPointer until k is non-negative.
16 if (k < 0 && nums[leftPointer++] === 0) {
17 // By moving leftPointer forward and encountering a 0, we flip it back to 0 ('unflip'),
18 // thus incrementing k.
19 k++;
20 }
21 }
22 // Calculate the maximum length of consecutive 1's that can be achieved by flipping
23 // at most k 0's. This is done by subtracting the leftPointer from the total length
24 // of the array, which gives us the size of the current window.
25 return lengthOfNums - leftPointer;
26}
27
Time and Space Complexity
The given code snippet uses a sliding window approach to solve the problem of finding the longest subarray with at most k
zeroes that can be flipped to 1
s.
Time Complexity:
The algorithm essentially processes each element of the array twice: once when extending the right end of the window (r
) and once when shifting the left end of the window (l
). This results in a linear pass over the array with n
elements total. The complexity is, therefore, O(n)
, where n
is the number of elements in the input list nums
.
Space Complexity:
The solution uses a few variables to track the indices of the window (l
, r
, and k
) and does not utilize any data structures that scale with the input size. Therefore, the space complexity of this solution is O(1)
as it requires a constant amount of extra space.
Learn more about how to find time and space complexity quickly using problem constraints.
What data structure does Breadth-first search typically uses to store intermediate states?
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
Want a Structured Path to Master System Design Too? Don’t Miss This!
The answer should be 5 in the example, [1, 1, 1, 1, 1, 0, 1]!