What is going wrong in this longest subarray of 1s after deleting one element

Question

I'm trying to solve 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.

Thought process

Apply sliding window mechanism with i and j at the start of the array:

• if array[j] is not 0 we keep incrementing j because it's safe to
• if array[j] is 0 and it's the first time 0, we still increment j because it's safe to, and increment count0
• if array[j] is 0 and it's the second time 0, if array[i] is 0, then we decrease the count and increase i
• if array[j] is 0 and it's the second time 0, if array[i] is not 0, then we just increase i

My Code

class Solution:
    def longestSubarrayOf1s(self, array):
        i,j = 0,0
        N = len(array)
        toReturn,count0,curr_count=0,0,0
        while j < N:
            if array[j] == 1:
                j+=1
            else:
                if count0 == 0:
                    j+=1
                    count0+=1
                else:
                    if array[i] == 0:
                        i+=1
                        count0-=1
                    else:
                        i+=1
            print('i am updating my max answer to ', j-i, 'in the window of ', i, j)
            toReturn = max(toReturn, j-i)
        return toReturn

Testing arrays

[1,1,1] #expected 2
[1,1,0,1] #expected 3
[0,1,1,1,0,1,1,0,1] #expected 5

Problem

My code does not return any correct answers. For the three test cases listed above, it returns 3, 4 and 6.

What is my mistake?

Answer 1

Your algorithm is fine, but the challenge says you should return the size (of the longest non-empty subarray containing only 1's) in the resulting array. You've returned the size it has in the original array. As one item needs to be deleted in the found subarray, you should return one less than you currently do:

toReturn = max(toReturn, j-i - 1)  # One less!

You could speed up the code a bit by avoiding to have i step up with only steps of 1. Since you already know it has to continue doing that until a zero is encountered, and you have already encountered that zero before with the j index, you could just keep track of that index when you encounter it with j and have i "jump" to that saved index in one go.

For arrays where the zeroes frequency is significantly less than the frequency of 1, you'll benefit from using the index method to find where the next zero sits.

Here is an implementation of that idea:

class Solution:
    def longestSubarray(self, array: List[int]) -> int:
        n = len(array)
        i = -1 # Index of a zero that is imagined in front of the array
        array.append(0)  # Add a dummy zero at the end
        j = array.index(0)
        toReturn = j - 1
        while j < n:  # As long as there are more zeroes...
            k = j  # Keep track of the current zero
            j = array.index(0, k + 1)  # ...and find the next one
            toReturn = max(toReturn, j - i - 2)
            i = k  # Have i "jump" to the next zero after it.
        return toReturn