Longest Subarray of 1's After Deleting One Element - Video Solutions

Problem Overview: You receive a binary array and must delete exactly one element. After the deletion, return the length of the longest contiguous subarray containing only 1s. The challenge is maximizing the length while handling the single allowed deletion efficiently.

Approach 1: Sliding Window with Variables (O(n) time, O(1) space)

This approach uses the classic sliding window technique. Maintain two pointers left and right and track how many zeros exist inside the window. Expand the window by moving right. When more than one zero appears, shrink the window by moving left until only one zero remains. Since deleting one element effectively allows one zero inside the window, the maximum valid window length minus one represents the answer. The array is scanned once, making this approach linear and memory efficient.

Approach 2: Prefix Sum and Single Pass (O(n) time, O(n) space)

This method precomputes consecutive runs of ones using prefix-style arrays. One array stores the number of consecutive 1s ending at each index from the left, while another stores consecutive 1s starting from each index from the right. When a 0 appears, you simulate deleting it by combining the left and right counts: left[i-1] + right[i+1]. This effectively merges two blocks of ones separated by a zero. The algorithm performs a single pass to build the arrays and another to compute the best merge. It uses extra memory but clearly demonstrates the structure of the problem using ideas similar to dynamic programming over an array.

Recommended for interviews: The sliding window solution is what interviewers typically expect. It shows you understand how to maintain constraints dynamically while scanning the array once. The prefix approach demonstrates solid reasoning about prefix states and segment merging, but the sliding window version is simpler, uses constant space, and is easier to implement under interview pressure.