Solution For Max Consecutive Ones Iii

Problem Statement:

Given an array A of 0s and 1s, we may change up to K values from 0 to 1.

Return the length of the longest (contiguous) subarray that contains only 1s.

Example:

Input: A = [1,1,1,0,0,0,1,1,1,1,0], K = 2

Output: 6

Explanation:

The longest subarray with only 1s has length 6.

Solution:

The problem is that we need to find the maximum length (contiguous) subarray that contains only 1s after changing at most K values from 0 to 1.

• Traverse through the array and keep track of the number of zeros we have seen so far.
• If the number of zeros is less than or equal to K, we can continue to increase the length of the subarray.
• If we see more than K zeros, we need to decrease the length of the subarray by removing the leftmost zero, keeping track of the number of zeros removed.
• We continue to move the left pointer until we have removed at most K zeros and increase the length of the subarray.

At each step, we keep track of the length of the subarray and return the maximum length seen so far.

Pseudo code:

left = 0
zeros = 0
max_length = 0
for right in range(len(A)):
if A[right] == 0:
zeros += 1
while zeros > K:
if A[left] == 0:
zeros -= 1
left += 1
max_length = max(max_length, right – left + 1)
return max_length

Explanation:

We initialize left pointer to 0, zeros to 0 and max_length to 0.

We loop through the array A, incrementing the right pointer and checking if the element at A[right] is a 0, we increment the zeros count.

If the number of zeros is greater than K, this means that we need to remove zeros from the left of the array until the count of zeros is less than or equal to K.

We do this using a while loop. While the count of zeros is greater than K, we increment the left pointer, and if the element at A[left] is a 0, we decrement the zeros count.

Once zeros count is less than or equal to K, we have a valid subarray. We obtain the length of the subarray by subtracting left from right and adding 1.

We check to see if the new length is greater than the current max_length. If it is, update max_length.

Finally, we return max_length which represents the length of the longest subarray with at most K 0s flipped to 1s.

Time Complexity:

We traverse the array only once. Therefore the time complexity of the algorithm is O(N), where N is the length of the array.

Space Complexity:

We use constant extra space to store the variables zeros, left and max_length. Therefore the space complexity of the algorithm is O(1).

Overall, the solution is efficient and optimal, providing the answer in O(N) time.

Step by Step Implementation For Max Consecutive Ones Iii

class Solution {
    public int findMaxConsecutiveOnes(int[] nums, int k) {
        int max = 0, zero = 0, start = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                zero++;
            }
            while (zero > k) {
                if (nums[start++] == 0) {
                    zero--;
                }
            }
            max = Math.max(max, i - start + 1);
        }
        return max;
    }
}

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        
        # keep track of the longest streak of 1's
        longest_streak = 0
        
        # keep track of the current streak of 1's
        current_streak = 0
        
        # keep track of the number of flips we've used
        num_flips = 0
        
        # scan the array
        for i in range(len(A)):
            
            # if the current element is a 1
            if A[i] == 1:
                
                # increment the current streak
                current_streak += 1
            
            # if the current element is a 0    
            else:
                
                # if we have used up all our flips
                if num_flips == K:
                    
                    # the longest streak ends at the previous index
                    longest_streak = max(longest_streak, current_streak)
                    
                    # the new longest streak starts at the next index
                    current_streak = 0
                    
                    # we've used up our flips, so reset the counter
                    num_flips = 0
                
                # if we haven't used up our flips    
                else:
                    
                    # increment the current streak
                    current_streak += 1
                    
                    # increment the number of flips
                    num_flips += 1
                    
        # update the longest streak    
        longest_streak = max(longest_streak, current_streak)
        
        return longest_streak

var findMaxConsecutiveOnes = function(nums, k) {
    let zeroCount = 0, maxOnesCount = 0, i = 0;
    
    for(let j = 0; j < nums.length; j++) {
        if(nums[j] === 0) {
            zeroCount++;
        }
        
        // whenever the number of zeros exceeds k, we need to remove the leftmost zero from the window
        // and update the count of zeros
        if(zeroCount > k) {
            if(nums[i] === 0) {
                zeroCount--;
            }
            i++;
        }
        
        // update the maximum number of ones in the window
        maxOnesCount = Math.max(maxOnesCount, j - i + 1);
    }
    
    return maxOnesCount;
};

class Solution {
public:
    int findMaxConsecutiveOnes(vector& nums, int k) {
        int max_len = 0;
        int zero_count = 0;
        int start = 0;
        
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 0) {
                zero_count++;
            }
            
            while (zero_count > k) {
                if (nums[start] == 0) {
                    zero_count--;
                }
                start++;
            }
            
            max_len = max(max_len, i - start + 1);
        }
        
        return max_len;
    }
};

public int FindMaxConsecutiveOnes(int[] nums, int k) { // Check for null or empty array if (nums == null || nums.Length == 0) { return 0; } // Initialize variables int maxOnes = 0; int zeroCount = 0; int start = 0; // Iterate through array for (int i = 0; i < nums.Length; i++) { // If current element is a 1, increment maxOnes if (nums[i] == 1) { maxOnes++; } // If current element is a 0, increment zeroCount // and update start if (nums[i] == 0) { zeroCount++; start = i+1; } // If we have more than k zeroes, update maxOnes // and reset variables if (zeroCount > k) { maxOnes = i - start; zeroCount = 0; start = i+1; } } return maxOnes; }