[LeetCode] Longest Subarray of 1's After Deleting One Element

Problem: Given a binary array nums, you should delete one element from it.

Return the size of the longest non-empty subarray containing only 1's in the resulting array. Return 0 if there is no such subarray.

Example:

Input: nums = [1,1,0,1]
Output: 3
Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1's.

Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].

Input: nums = [1,1,1]
Output: 2
Explanation: You must delete one element.

Approach: This problem is similar to problem of maximum number of consecutive 1's in the array if you can flip at most k 0's. Here is k is constant which is 1 so here too we are going to take sliding window approach and answer is the max window size - 1.

Implementation in C#:

    public int LongestSubarray(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length == 0)

        {

            return 0;

        }

        int start = 0, end = 0, k = 1;

        for (; end < length; ++end)

        {

            if (nums[end] == 0)

            {

                --k;

            }

            if (k < 0)

            {

                if (nums[start++] == 0)

                {

                    ++k;

                }

            }

        }

        return end - start - 1;

    }

Complexity: O(n)