https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element

One way to deal this problem is dynamic programming. Let dp[i][0] be the length of longest subarray of ones, such that it ends at point i. Let dp[i][1] be the length longest subarray, which has one zero and ends at point i. Let us traverse through our nums and update our dp table, we have two options:

  1. dp[0][0] = 1 if nums[0] = 1 and 0 in opposite case.
  2. If nums[i] = 1, than to update dp[i][0] we just need to look into dp[i-1][0] and add one, the same true is for dp[i][1].
  3. If nums[i] = 0, than dp[i][0] = 0, we need to interrupt our sequence without zeroes. dp[i][1] = dp[i-1][0], because we we added 0 and number of 1 is still i-1.

Let us go through example [1,0,1,1,0,0,1,1,0,1,1,1]: then we have the following dp table:

1 0 1 2 0 0 1 2 0 1 2 3
0 1 2 3 2 0 1 2 2 3 4 5

Complexity: time and space is O(n), because we iterate over our table dp once. Space can be reduced to O(1) because we only look into the previous column of our table.

Extension and follow-up. Note, that this solution can be easily extended for the case, when we need to delete k elements instead of one, with time complexity O(nk) and space complexity O(k).

Other solutions. This problem can be solved with sliding window technique as well, or we can evaluate sizes of groups of 0’s and 1’s and then choose two group of 1’s, such that it has group of 0’s with only one element between them.

class Solution:
    def longestSubarray(self, nums):
        n = len(nums)
        if sum(nums) == n: return n - 1
        
        dp = [[0] * 2 for _ in range(n)]
        dp[0][0] = nums[0]
        
        for i in range(1, n):
            if nums[i] == 1:
                dp[i][0], dp[i][1] = dp[i-1][0] + 1, dp[i-1][1] + 1
            else:
                dp[i][0], dp[i][1] = 0, dp[i-1][0]
        
        return max([i for j in dp for i in j])

If you like the solution, you can upvote it on leetcode discussion section: Problem 1493