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

1. Question

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

Example 3:

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

2. Thoughts

given nums = [0,1,1,1,0,1,1,0,1]
1) iterate through nums, untill finding 0
2) if find 0, remember 0's place, and calculate local sum up to there
3) do so, and calculate global max

3. Tips learned

4. My solution

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        local_max = global_max = i = 0
        last_zero = -1
        for i in range(len(nums)):
            # is 1
            if nums[i] == 1:
                local_max += 1
            # is 0
            else:
                global_max = max(global_max, local_max)
                if last_zero != -1:
                    local_max = i - last_zero - 1
                last_zero = i

        global_max = max(global_max, local_max)
        # No zero exists
        if last_zero == -1:
            global_max -= 1

        return global_max

81/81 cases passed (398 ms)
Your runtime beats 87.99 % of python3 submissions
Your memory usage beats 56.03 % of python3 submissions (19 MB)

5. AI Solution and Improvements

Your code is a reasonable solution to the problem. However, there are several ways to make it more Pythonic and potentially more efficient.

1. You can use enumerate to loop over both the index and the value in the array.
2. You can get rid of some redundant logic and variables like i.

Here's a Pythonic version of your code with these suggestions applied:

        local_max = global_max = 0
        last_zero = -1
        for i,num in enumerate(nums):
            # is 1
            if num == 1:
                local_max += 1
            # is 0
            else:
                global_max = max(global_max, local_max)
                if last_zero != -1:
                    local_max = i - last_zero - 1
                last_zero = i

        global_max = max(global_max, local_max)
        # No zero exists
        if last_zero == -1:
            global_max -= 1

        return global_max

Regarding algorithmic efficiency, your solution runs in O(n) time complexity, which is optimal for this problem since you have to examine each element in the array at least once. Therefore, there's no need for a different algorithm for the sake of performance.

55/55 cases passed (492 ms)
Your runtime beats 90.78 % of python3 submissions
Your memory usage beats 56.03 % of python3 submissions (17.5 MB)