LC-1493 Medium LeetCode

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

Array Dynamic Programming Sliding Window

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 69% Topics: Array, Dynamic Programming, Sliding Window

Reading material

Arrays & Hashing 12 min 1-D Dynamic Programming 16 min Sliding Window 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

class Solution(object):
    def longestSubarray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        count, left = 0, 0
        for right in xrange(len(nums)):
            count += (nums[right] == 0)
            if count >= 2:
                count -= (nums[left] == 0)
                left += 1
        return (right-left+1)-1


# Time:  O(n)
# Space: O(1)
class Solution2(object):
    def longestSubarray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        result, count, left = 0, 0, 0
        for right in xrange(len(nums)):
            count += (nums[right] == 0)
            while count >= 2:
                count -= (nums[left] == 0)
                left += 1
            result = max(result, right-left+1)
        return result-1

Solution from kamyu104/LeetCode-Solutions · MIT