LeetCode Challenge #1004. Max Consecutive Ones III

Question 16 of 75 - LeetCode Weekly Challenge

LeetCode Challenge #1004. Max Consecutive Ones III

Given a binary array nums and an integer k, return the maximum number of consecutive 1‘s in the array if you can flip at most k 0‘s.

Example 1:

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: [1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Example 2:

Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
Output: 10
Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Constraints:

1 <= nums.length <= 10⁵
nums[i] is either 0 or 1.
0 <= k <= nums.length

Video Solution

C++ Solution

				
					class Solution {
public:
int longestOnes(vector<int>& nums, int k) {

        // Initialize two pointers i and j to represent the start and end of the window
        int i = 0, j = 0;

        // Iterate through the array using the end pointer (j)
        while (j < nums.size()) {

            // If the current element at the end pointer is 0, decrement the allowed flips (k)
            if (nums[j] == 0) {
                k--;
            }

            // If the allowed flips (k) become negative, adjust the window from the start pointer (i)
            if (k < 0) {

                // If the element at the start pointer is 0, increment the allowed flips (k)
                if (nums[i] == 0) {
                    k++;
                }
                // Move the start pointer to the next element
                i++;
            }

            // Move the end pointer to the next element
            j++;
        }

        // The length of the longest subarray is given by the difference between end and start pointers
        return j - i;
    }
};

Code Explanation

The primary objective of this function is to determine the length of the longest subarray in a binary array, represented by ‘nums’, that contains at most ‘k’ zeroes. This problem is solved by using a sliding window approach.

Let’s see the step-by-step approach to the problem:

In this approach, we define ‘i’ and ‘j’ to 0. Where ‘i’ is the starting point of the window and ‘j’ is the ending point of the window.
The solution’s core lies in the ‘while’ loop that continues until the ‘j’ pointer reaches the end of the array.

Within the loop, we check if the (nums[ j ] ==0 ) means if ‘j’ pointer reaches the end of the array. If it is, the variable ‘k’, representing the remaining number of zeroes allowed in the subarray, is decremented.
Also, we check if ‘k’ is not equal to zero or ( k has been exceeded). If so, the window is adjusted by moving the ‘i’ pointer to the right and incrementing ‘k’ if the element at position ‘i’ is 0. Because if ‘i’ is zero that means we have to leave that position that’s why we have incremented ‘k’ here. When we are not doing any replacement we can leave the element.
This process effectively maintains the window with at most ‘k’ zeroes. And because the window is getting smaller as ‘k’ is getting decreased we increment the ‘i’ again. ( i++)
And apart from that, the ‘j’ pointer always advances to the right within the loop, and the function calculates the length of the current subarray as ‘j-i’. This length is continuously updated during the traversal of the array.

After the loop completes, the function returns ‘( j -i )’ the length of the longest subarray containing at most ‘k’ zeroes.

Summary- This problem effectively finds the length of the longest subarray with at most ‘k’ zeroes, showcasing a practical implementation of the sliding window techniques.

Question 16 of 75 - LeetCode Weekly Challenge