Longest Subarray of 1’s After Deleting One Element

Explore Solutions in Other Languages

Problem Description

Ah, the classic dilemma of finding the longest subarray of 1’s after deleting just one element. It’s like trying to find the longest stretch of uninterrupted Netflix binge-watching after your roommate decides to hog the remote. You know you can only kick them out (delete one element) once, but you want to maximize your viewing pleasure (the length of 1’s).

In this problem, you are given an array of integers consisting of 0’s and 1’s. Your task is to find the length of the longest contiguous subarray that contains only 1’s after you delete one element (which can be either a 0 or a 1).

Code Solution


class Solution:
    def longestSubarray(self, nums: list[int]) -> int:
        ans = 0
        zeros = 0
        l = 0
        for r, num in enumerate(nums):
            if num == 0:
                zeros += 1
            while zeros == 2:
                if nums[l] == 0:
                    zeros -= 1
                l += 1
            ans = max(ans, r - l)
        return ans

Approach Explanation

The approach used in the code is a sliding window technique. We maintain a window defined by two pointers, l (left) and r (right). As we iterate through the array with the right pointer, we count the number of zeros. If we encounter two zeros, we increment the left pointer until we have at most one zero in our window. This way, we can calculate the maximum length of the subarray of 1’s that can be achieved by deleting one element.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n)
Space Complexity	O(1)

Real-World Example

Imagine you’re at a party, and you’re trying to find the longest time you can spend with your friends (1’s) before you have to deal with that one annoying person (0) who keeps interrupting. You can only ask them to leave once, so you want to maximize your fun time with your friends. This problem is just like that—finding the longest stretch of good times after dealing with one interruption.