[LeetCode] Max Consecutive Ones III

Problem: 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:

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.

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.

Approach: This is kind of again a sliding window problem but here the window size is not constant. The window size can be expanded till the condition is satisfied which is the window must have at most k 0's.

We can expand the window till the above condition is satisfied i.e. we keep increasing the end but when we see the window has k + 1 0's, we start shrinking the window from the left i.e. we keep increasing start till we get nums[start] = 0. To reduce this iteration we can use queue to store the indices of all 0's so that we can directly jump to back of queue + 1 index to find the next start. At any point of time the current window size would be end - start.

If you see from the above approach we would be able to solve this problem in linear time but we are taking extra storage. Off course we can remove this extra storage but in that case we might end up doing 2 * n steps. Anything else we can do to improve it further? 

Just think whenever current window can be expanded i.e. window has at most k 0's, start doesn't move and in the end the max distance is really end - start. Means in case of k + 1 0's we keep increasing the start and end is anyway alwasy increasing. So even if we don't reach the 0 to shrink the window the size of the remains same till the above condition is not satisfied because we keep incrementing start by 1 at every step.

That's all

Implementation in C#:

With Queue:

    public int LongestOnes(int[] nums, int k)

    {

        int length  = nums?.Length ?? 0;

        if (length == 0)

        {

            return 0;

        }

        Queue<int> zeroIndicesQ = new Queue<int>();

        int maxLength = 0, start = 0;

        bool isFirstZero = true;

        for (int i = 0; i < length; ++i)

        {

            if (nums[i] == 0)

            {

                zeroIndicesQ.Enqueue(i);

                --k;

                if (k < 0)

                {

                    k = 0;

                    maxLength = maxLength < i - start ?

                                i - start :

                                maxLength;

                    start = zeroIndicesQ.Dequeue() + 1;

                }

            }

        }

        return maxLength < length - start ?

               length - start :

               maxLength;

    }

Optimized way:

        public int LongestOnes(int[] nums, int k)

    {

        int length  = nums?.Length ?? 0;

        if (length == 0)

        {

            return 0;

        }

        int start = 0, end = 0;

        for (; end < length; ++end)

        {

            if (nums[end] == 0)

            {

                --k;

            }

            if (k < 0)

            {

                if (nums[start] == 0)

                {

                    ++k;

                }

                ++start;

            }

        }

        return end - start;

    }

Complexity: O(n)