Need explanation on one awesome solution found for Leetcode 1493

Question

I am looking at solutions for LeetCode problem 1493. Longest Subarray of 1's After Deleting One Element:

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 1

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.

Example 2

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].

Constraints:

• 1 <= nums.length <= 105
• nums[i] is either 0 or 1.

I found a super clean solution in the submission pool, which I believe to be beneficial if I can understand how it worked, but I just can't.

class Solution(object):
    def longestSubarray(self, nums):
        ans = 0
        zero = 0
        left = 0
        for i, v in enumerate(nums):
            if v == 0:
                zero += 1
            if zero > 1:
                if nums[left] == 0:
                    zero -= 1
                left += 1
        return i - left

I think, from the return statement, it's clear that left is used to count the zeros from left, and the un-counted 1. I see how it tracks how many unused zeros on the left. But how does it track the 1s that are not included?

And why this algorithm still works for when the longest subarray appears in the middle, as it continues further, passing beyond the longest subarray?

I guess I'm just confused here...

Answer 1

This uses a sliding window technique, where the current window is identified with nums[left:i] at the start of every iteration.

We can identify the following loop invariants, when at the very start of the loop body:

• The size i - left is the size of the largest window in nums[:i] that includes at most one zero. It indicates that we previously encountered (somewhere) a window of the same size that had at most one zero, but we don't track at which index we found it.
• zero represents the number of zeroes in the current window nums[left:i].

The current iteration will add nums[i] to the window, and if that keeps the number of zeroes in that window to at most one, we have a current "winner", and left is not incremented so that the window size increases. Otherwise it is not a winner, and left is incremented, aiming to keep the window size unchanged. During these actions zero is updated to make sure the second invariant is maintained.

After the loop has finished, we need to take the following into account:

We don't have the invariant there, because i did not increase to len(nums), but remains equal to the last index of nums. This is something that is language specific. It happens to work like that in Python, but in other loop constructs or other languages, i could end up as equal to len(nums). Anyway, here value i - left is one less than the "winner" we found. But this is exactly what we needed, because we "...should delete one element from it".

One thing in all this that can be confusing is that the current window does not represent the window of interest, only the size of the window of interest. This algorithm doesn't care about where exactly that optimal window is located. It only looks further to find potential winners that are one unit larger.

To get some insight in how the code runs, it helped me to put this print in the code:

            if zero > 1:
                if nums[left] == 0:
                    zero -= 1
                left += 1
            else:  # We have an improvement!
                print(f"the current winner is window {left}:{i+1}: {nums[left:i+1]}")

I hope this clarifies it.