Longest Subarray of 1's After Deleting One Element

Master this topic with zero to advance depth.

Longest Subarray of 1's After Deleting One Element

Given a binary array nums, you must delete exactly one element. Return the maximum number of consecutive 1's remaining.

Visual Representation

nums = [1, 1, 0, 1]

[1, 1, 0, 1]
      ^ Delete this 0
Remaining: [1, 1, 1] -> Len 3

Sliding Window Rule:
Window must contain at most ONE zero.
Final Result = WindowSize - 1

Medium

Examples

Input: nums = [1,1,0,1]
Output: 3

Approach 1

Level I: Brute Force

Intuition

Iterate through every element in the array. For each element, assume it is the one being deleted, and then find the longest contiguous block of 1's that can be formed using the remaining elements.

Thought Process

Iterate through each index i from 0 to n-1.
Simulate deleting nums[i].
After 'deletion', find the longest sequence of 1's in the remaining array.
Track the maximum length found across all possible deletions.

⏱ O(N^2)💾 O(N) to store the modified array, or O(1) if logic is careful.

Detailed Dry Run

Deleting Index	Resulting Array	Max 1s	Result
0	[1, 0, 1]	1	1
1	[1, 0, 1]	1	1
2	[1, 1, 1]	3	3
3	[1, 1, 0]	2	3

java

public class Main {
    public static int longestSubarray(int[] nums) {
        int maxLen = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int currentLen = 0, bestInThisCase = 0;
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                if (nums[j] == 1) {
                    currentLen++;
                    bestInThisCase = Math.max(bestInThisCase, currentLen);
                } else {
                    currentLen = 0;
                }
            }
            maxLen = Math.max(maxLen, bestInThisCase);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 0, 1};
        System.out.println(longestSubarray(nums)); // 3
    }
}

Approach 2

Level III: Optimal (Sliding Window)

Intuition

Thought Process

This is equivalent to 'Max Consecutive Ones III' with k = 1. We find the longest window with at most one zero. Since we must delete one element, the result is always WindowSize - 1.

Patterns

Variable Window: Expand as long as zeros $\le 1$ .
Constraint: If zeros > 1, shrink from left.

⏱ O(N)💾 O(1)

Detailed Dry Run

R	Num	Zeros	Window Size	Result
0	1	0	1	0
1	1	0	2	1
2	0	1	3	2
3	1	1	4	3 (MAX)

java

public class Main {
    public static int longestSubarray(int[] nums) {
        int left = 0, zeros = 0, maxLen = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] == 0) zeros++;
            while (zeros > 1) {
                if (nums[left] == 0) zeros--;
                left++;
            }
            // The window length is (right - left + 1)
            // We MUST delete one element, so result is (windowLen - 1)
            maxLen = Math.max(maxLen, right - left);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(longestSubarray(new int[]{1, 1, 0, 1})); // 3
    }
}

⚠️ Common Pitfalls & Tips

If the array consists only of 1's, the result should be N - 1, not N. Don't forget that one deletion is MANDATORY.

← Previous QuestionMaximum Points You Can Obtain from Cards

Next Question →Minimum Operations to Reduce X to Zero

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.