Introduction

LeetCode 1493: Longest Subarray of 1's After Deleting One Element is a neat sliding window problem that tests your ability to dynamically adjust a window while handling a constraint: deleting exactly one element.

The task is to find the longest subarray of 1's you can get after deleting one element from the array.

This problem is an excellent example of how sliding window with zero counting can convert a potentially brute-force solution into an O(n) linear solution.

If you’d like to try solving the problem first, you can attempt it here:

Try the problem on LeetCode:

https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/

Problem Understanding

You are given:

1. A binary array nums containing only 0’s and 1’s
2. You must delete exactly one element

Your task: Return the length of the longest non-empty subarray of 1’s after deleting one element.

Examples:

A naive approach would try removing each element and scanning for the longest subarray →

1. Time Complexity: O(n²) → too slow for nums.length up to 10⁵
2. Inefficient for large arrays

Key Idea: Sliding Window with At Most One Zero

Notice the following:

1. Deleting one element is equivalent to allowing at most one zero in the subarray
2. We can use a sliding window [i, j] and a counter z for zeros in the window
3. Expand j while z <= 1
4. If z > 1, shrink the window from the left until z <= 1
5. The length of the window (j - i) gives the maximum length of consecutive 1’s after deleting one element

Intuition:

1. Only one zero is allowed in the window because deleting that zero would turn the window into all 1's
2. This converts the problem into a linear sliding window problem with zero counting

Approach (Step-by-Step)

1. Initialize i = 0, j = 0 for window pointers
2. Initialize z = 0 → number of zeros in current window
3. Initialize co = 0 → maximum length of valid subarray
4. Iterate j over nums:
5. If nums[j] == 0, increment z
6. Check z:
7. If z <= 1: window is valid → update co = max(co, j - i)
8. If z > 1: shrink window from i until z <= 1
9. Continue expanding the window
10. Return co as the maximum length after deleting one element

Optimization:

1. Only need one zero counter and window pointers
2. Avoid recomputing subarray lengths repeatedly

Implementation (Java)

Dry Run Example

Input:

Execution:

Output:

Complexity Analysis

1. Time Complexity: O(n) → Each element is visited at most twice (i and j)
2. Space Complexity: O(1) → Only counters and pointers used

Edge Cases Considered

1. Array of all 1’s → must delete one → max length = n - 1
2. Array of all 0’s → return 0
3. Single element arrays → return 0 (because deletion required)
4. Zeros at the start/end of array → handled by sliding window

Sliding Window Pattern Importance

This problem is a great example of sliding window with limited violations:

1. Maintain a window satisfying a constraint (at most one zero)
2. Expand/shrink dynamically
3. Compute max length without scanning all subarrays

It’s directly related to problems like:

1. Max consecutive ones with k flips
2. Longest substring with at most k distinct characters
3. Subarray problems with limited replacements

Conclusion

By tracking zeros with a sliding window, we efficiently find the longest subarray of 1’s after deleting one element in O(n) time.

This pattern is reusable in many binary array and string problems, making it a must-know technique for coding interviews.