1493. Longest Subarray of 1's After Deleting One - Solution

The problem

Given a binary array nums, you should delete one element from it.

Return the size of the longest non-empty subarray containing only 1's in the resulting array. Return 0 if there is no such subarray.

Example 1:

Input: nums = [1,1,0,1]
Output: 3
Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1's.

Example 2:

Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].

Example 3:

Input: nums = [1,1,1]
Output: 2
Explanation: You must delete one element.

Constraints:

1 <= nums.length <= 10⁵
nums[i] is either 0 or 1.

Approach overview

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.

Approach 1: Sliding Window with Variables

This approach uses a sliding window technique with variables to keep track of the count of consecutive 1's before and after a zero. The main idea is to iterate through the array, and whenever you encounter more than one zero, calculate the length of 1's that can be formed by deleting the previous zero, update maximum length as needed, and reset counts.

Python

class Solution:
    def longestSubarray(self, nums):
        max_len = 0
        left = 0
        zero_count = 0

        for right in range(len(nums)):
            if nums[right] == 0:
                zero_count += 1
            while zero_count > 1:
                if nums[left] == 0:
                    zero_count -= 1
                left += 1
            max_len = max(max_len, right - left)
        return max_len

# Usage
# sol = Solution()
# print(sol.longestSubarray([0,1,1,1,0,1,1,0,1]))

Java

class Solution {
    public int longestSubarray(int[] nums) {
        int maxLen = 0, left = 0, zeroCount = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] == 0) zeroCount++;
            while (zeroCount > 1) {
                if (nums[left] == 0) zeroCount--;
                left++;
            }
            maxLen = Math.max(maxLen, right - left);
        }
        return maxLen;
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {0,1,1,1,0,1,1,0,1};
        System.out.println(sol.longestSubarray(nums));
    }
}

C++

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int maxLen = 0, left = 0, right = 0, zeroCount = 0;
        for (right = 0; right < nums.size(); right++) {
            if (nums[right] == 0) zeroCount++;
            while (zeroCount > 1) {
                if (nums[left] == 0) zeroCount--;
                left++;
            }
            maxLen = max(maxLen, right - left);
        }
        return maxLen;
    }
};

// Usage
// Solution().longestSubarray({0,1,1,1,0,1,1,0,1});

JavaScript

const longestSubarray = function(nums) {
    let maxLen = 0, left = 0, zeroCount = 0;
    for (let right = 0; right < nums.length; right++) {
        if (nums[right] === 0) zeroCount++;
        while (zeroCount > 1) {
            if (nums[left] === 0) zeroCount--;
            left++;
        }
        maxLen = Math.max(maxLen, right - left);
    }
    return maxLen;
};

// Usage Example
console.log(longestSubarray([0,1,1,1,0,1,1,0,1]));

#include <stdio.h>

int longestSubarray(int* nums, int numsSize) {
    int maxLen = 0;
    int zeroCount = 0;
    int currentLen = 0, prevLen = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == 1) {
            currentLen++;
        } else {
            maxLen = zeroCount == 0 ? currentLen : max(maxLen, prevLen + currentLen);
            prevLen = currentLen;
            currentLen = 0;
            zeroCount++;
            if (zeroCount > 1) zeroCount = 1;
        }
    }
    maxLen = max(maxLen, prevLen + currentLen);
    return maxLen == numsSize ? maxLen - 1 : maxLen;
}

int main() {
    int nums[] = {0,1,1,1,0,1,1,0,1};
    int size = sizeof(nums)/sizeof(nums[0]);
    printf("%d", longestSubarray(nums, size));
    return 0;
}

public class Solution {
    public int LongestSubarray(int[] nums) {
        int maxLen = 0, left = 0, zeroCount = 0;
        for (int right = 0; right < nums.Length; right++) {
            if (nums[right] == 0) zeroCount++;
            while (zeroCount > 1) {
                if (nums[left] == 0) zeroCount--;
                left++;
            }
            maxLen = Math.Max(maxLen, right - left);
        }
        return maxLen;
    }

    public static void Main(string[] args) {
        Solution sol = new Solution();
        int[] nums = {0,1,1,1,0,1,1,0,1};
        Console.WriteLine(sol.LongestSubarray(nums));
    }
}

The Python code iterates over the array with a window, counting zeros and ensuring the window only contains at most one zero for the desired result. Left pointer is incremented to adjust the window whenever more than one zero is encountered.

Complexity

Time Complexity: O(n), as we traverse the array at most twice.
Space Complexity: O(1), as only a constant amount of extra space is needed.

Try this approach in the editor

Approach 2: Prefix Sum and Single Pass

This approach utilizes prefix sums to keep a cumulative count of 1's encountered and calculates lengths avoiding excessive recalculations. Two arrays store the prefix sum of 1's up to the current element and from the current element to the end, respectively. A single pass is then made to compute the maximum length by checking possible deletions at each zero.

Python

class Solution:
    def longestSubarray(self, nums):
        n = len(nums)
        if n == 0:
            return 0

        prefix = [0] * n
        suffix = [0] * n

        prefix[0] = nums[0]
        for i in range(1, n):
            prefix[i] = prefix[i - 1] + 1 if nums[i] == 1 else 0

        suffix[n - 1] = nums[n - 1]
        for i in range(n - 2, -1, -1):
            suffix[i] = suffix[i + 1] + 1 if nums[i] == 1 else 0

        max_len = 0
        for i in range(n):
            max_len = max(max_len, prefix[i] + (suffix[i + 1] if i + 1 < n else 0))

        return max_len if nums.count(0) > 0 else max_len - 1

# Usage
# sol = Solution()
# print(sol.longestSubarray([0,1,1,1,0,1,1,0,1]))

Java

import java.util.*;

class Solution {
    public int longestSubarray(int[] nums) {
        int n = nums.length;
        int[] prefix = new int[n];
        int[] suffix = new int[n];

        prefix[0] = nums[0];
        for (int i = 1; i < n; i++) {
            prefix[i] = (nums[i] == 1) ? prefix[i - 1] + 1 : 0;
        }

        suffix[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            suffix[i] = (nums[i] == 1) ? suffix[i + 1] + 1 : 0;
        }

        int maxLen = 0;
        for (int i = 0; i < n; i++) {
            maxLen = Math.max(maxLen, prefix[i] + ((i + 1 < n) ? suffix[i + 1] : 0));
        }

        return maxLen == n ? maxLen - 1 : maxLen;
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {0,1,1,1,0,1,1,0,1};
        System.out.println(sol.longestSubarray(nums));
    }
}

C++

#include <vector>
using namespace std;

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        vector<int> prefix(n, 0), suffix(n, 0);

        prefix[0] = nums[0];
        for (int i = 1; i < n; i++) {
            prefix[i] = (nums[i] == 1) ? prefix[i - 1] + 1 : 0;
        }

        suffix[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            suffix[i] = (nums[i] == 1) ? suffix[i + 1] + 1 : 0;
        }

        int maxLen = 0;
        for (int i = 0; i < n; i++) {
            maxLen = max(maxLen, prefix[i] + ((i + 1 < n) ? suffix[i + 1] : 0));
        }

        return maxLen == n ? maxLen - 1 : maxLen;
    }
};

// Usage
// Solution().longestSubarray({0,1,1,1,0,1,1,0,1});

JavaScript

const longestSubarray = function(nums) {
    const n = nums.length;
    if (n <= 1) return 0;

    let prefix = new Array(n).fill(0);
    let suffix = new Array(n).fill(0);

    prefix[0] = nums[0];
    for (let i = 1; i < n; i++) {
        prefix[i] = nums[i] === 1 ? prefix[i - 1] + 1 : 0;
    }

    suffix[n - 1] = nums[n - 1];
    for (let i = n - 2; i >= 0; i--) {
        suffix[i] = nums[i] === 1 ? suffix[i + 1] + 1 : 0;
    }

    let maxLen = 0;
    for (let i = 0; i < n; i++) {
        maxLen = Math.max(maxLen, prefix[i] + (i + 1 < n ? suffix[i + 1] : 0));
    }

    return maxLen === n ? maxLen - 1 : maxLen;
};

// Usage Example
console.log(longestSubarray([0,1,1,1,0,1,1,0,1]));

#include <stdio.h>

int longestSubarray(int* nums, int numsSize) {
    if (numsSize <= 1) return 0;
    int prefix[numsSize];
    int suffix[numsSize];
    int maxLen = 0;

    // Build prefix sums
    prefix[0] = nums[0];
    for (int i = 1; i < numsSize; i++) {
        prefix[i] = (nums[i] == 1) ? prefix[i - 1] + 1 : 0;
    }

    // Build suffix sums
    suffix[numsSize - 1] = nums[numsSize - 1];
    for (int i = numsSize - 2; i >= 0; i--) {
        suffix[i] = (nums[i] == 1) ? suffix[i + 1] + 1 : 0;
    }

    // Calculate maximum length
    for (int i = 0; i < numsSize; i++) {
        maxLen = fmax(maxLen, prefix[i] + ((i + 1 < numsSize) ? suffix[i + 1] : 0));
    }

    return maxLen == numsSize ? maxLen - 1 : maxLen;
}

int main() {
    int nums[] = {0,1,1,1,0,1,1,0,1};
    int size = sizeof(nums)/sizeof(nums[0]);
    printf("%d", longestSubarray(nums, size));
    return 0;
}

public class Solution {
    public int LongestSubarray(int[] nums) {
        int n = nums.Length;
        int[] prefix = new int[n];
        int[] suffix = new int[n];

        prefix[0] = nums[0];
        for (int i = 1; i < n; i++) {
            prefix[i] = (nums[i] == 1) ? prefix[i - 1] + 1 : 0;
        }

        suffix[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            suffix[i] = (nums[i] == 1) ? suffix[i + 1] + 1 : 0;
        }

        int maxLen = 0;
        for (int i = 0; i < n; i++) {
            maxLen = Math.Max(maxLen, prefix[i] + ((i + 1 < n) ? suffix[i + 1] : 0));
        }

        return maxLen == n ? maxLen - 1 : maxLen;
    }

    public static void Main(string[] args) {
        Solution sol = new Solution();
        int[] nums = {0,1,1,1,0,1,1,0,1};
        Console.WriteLine(sol.LongestSubarray(nums));
    }
}

The Python solution tactfully constructs and uses prefix and suffix tables to evaluate each point in the array methodically. It ensures complete use of subsections around a singular potential deletion point.

Complexity

Time Complexity: O(n), involves three clear traversals through the data.
Space Complexity: O(n), owing to the prefix and suffix storage requirements.

Try this approach in the editor

Approach 3: Enumeration

We can enumerate each position i to be deleted, then calculate the number of consecutive 1s on the left and right, and finally take the maximum value.

Specifically, we use two arrays left and right of length n+1, where left[i] represents the number of consecutive 1s ending with nums[i-1], and right[i] represents the number of consecutive 1s starting with nums[i].

The final answer is max_{0 leq i < n} {left[i] + right[i+1]}.

The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array nums.

TypeScript

function longestSubarray(nums: number[]): number {
    const n = nums.length;
    const left: number[] = Array(n + 1).fill(0);
    const right: number[] = Array(n + 1).fill(0);
    for (let i = 1; i <= n; ++i) {
        if (nums[i - 1]) {
            left[i] = left[i - 1] + 1;
        }
    }
    for (let i = n - 1; ~i; --i) {
        if (nums[i]) {
            right[i] = right[i + 1] + 1;
        }
    }
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        ans = Math.max(ans, left[i] + right[i + 1]);
    }
    return ans;
}

func longestSubarray(nums []int) (ans int) {
	n := len(nums)
	left := make([]int, n+1)
	right := make([]int, n+1)
	for i := 1; i <= n; i++ {
		if nums[i-1] == 1 {
			left[i] = left[i-1] + 1
		}
	}
	for i := n - 1; i >= 0; i-- {
		if nums[i] == 1 {
			right[i] = right[i+1] + 1
		}
	}
	for i := 0; i < n; i++ {
		ans = max(ans, left[i]+right[i+1])
	}
	return
}

Rust

impl Solution {
    pub fn longest_subarray(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut left = vec![0; n + 1];
        let mut right = vec![0; n + 1];

        for i in 1..=n {
            if nums[i - 1] == 1 {
                left[i] = left[i - 1] + 1;
            }
        }

        for i in (0..n).rev() {
            if nums[i] == 1 {
                right[i] = right[i + 1] + 1;
            }
        }

        let mut ans = 0;
        for i in 0..n {
            ans = ans.max(left[i] + right[i + 1]);
        }

        ans as i32
    }
}

Try this approach in the editor

Approach 4: Two Pointers

The problem is actually asking us to find the longest subarray that contains at most one 0. The remaining length after deleting one element from this subarray is the answer.

Therefore, we can use two pointers j and i to point to the left and right boundaries of the subarray, initially j = 0, i = 0. In addition, we use a variable cnt to record the number of 0s in the subarray.

Next, we move the right pointer i. If nums[i] = 0, then cnt is incremented by 1. When cnt > 1, we need to move the left pointer j until cnt leq 1. Then, we update the answer, i.e., ans = max(ans, i - j). Continue to move the right pointer i until i reaches the end of the array.

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).

TypeScript

function longestSubarray(nums: number[]): number {
    let [ans, cnt, j] = [0, 0, 0];
    for (let i = 0; i < nums.length; ++i) {
        cnt += nums[i] ^ 1;
        while (cnt > 1) {
            cnt -= nums[j++] ^ 1;
        }
        ans = Math.max(ans, i - j);
    }
    return ans;
}

func longestSubarray(nums []int) (ans int) {
	cnt, j := 0, 0
	for i, x := range nums {
		cnt += x ^ 1
		for ; cnt > 1; j++ {
			cnt -= nums[j] ^ 1
		}
		ans = max(ans, i-j)
	}
	return
}

Rust

impl Solution {
    pub fn longest_subarray(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut ans = 0;
        let mut j = 0;
        let mut cnt = 0;

        for i in 0..n {
            cnt += nums[i] ^ 1;
            while cnt > 1 {
                cnt -= nums[j] ^ 1;
                j += 1;
            }
            ans = ans.max(i - j);
        }

        ans as i32
    }
}

Try this approach in the editor

Approach 5: Two Pointers (Optimization)

In Solution 2, we move the left pointer in a loop until cnt leq 1. Since the problem asks for the longest subarray, it means we don't need to reduce the length of the subarray. Therefore, if cnt \gt 1, we only move the left pointer once, and the right pointer continues to move to the right. This ensures that the length of the subarray does not decrease.

Finally, the answer we return is n - l - 1, where l is the position of the left pointer.

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).

TypeScript

function longestSubarray(nums: number[]): number {
    let [cnt, l] = [0, 0];
    for (const x of nums) {
        cnt += x ^ 1;
        if (cnt > 1) {
            cnt -= nums[l++] ^ 1;
        }
    }
    return nums.length - l - 1;
}

func longestSubarray(nums []int) int {
	cnt, l := 0, 0
	for _, x := range nums {
		cnt += x ^ 1
		if cnt > 1 {
			cnt -= nums[l] ^ 1
			l++
		}
	}
	return len(nums) - l - 1
}

Rust

impl Solution {
    pub fn longest_subarray(nums: Vec<i32>) -> i32 {
        let mut cnt = 0;
        let mut l = 0;

        for &x in &nums {
            cnt += x ^ 1;
            if cnt > 1 {
                cnt -= nums[l] ^ 1;
                l += 1;
            }
        }

        (nums.len() - l - 1) as i32
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Sliding Window with Variables	Time Complexity: O(n), as we traverse the array at most twice. Space Complexity: O(1), as only a constant amount of extra space is needed.
Prefix Sum and Single Pass	Time Complexity: O(n), involves three clear traversals through the data. Space Complexity: O(n), owing to the prefix and suffix storage requirements.
Enumeration	–
Two Pointers	–
Two Pointers (Optimization)	–

Complexity analysis

Approach	Time	Space	When to Use
Sliding Window with Variables	O(n)	O(1)	Best general solution. Optimal for interviews and large arrays due to constant space.
Prefix Sum and Single Pass	O(n)	O(n)	Useful when analyzing contiguous segments or when prefix information simplifies reasoning.

Frequently asked questions

Is Longest Subarray of 1's After Deleting One Element easy or hard?

This problem is rated Medium on LeetCode because it requires recognizing the sliding window pattern and handling the single-deletion constraint correctly. Once the idea of allowing at most one zero in the window is understood, the implementation becomes straightforward.

Longest Subarray of 1's After Deleting One Element Python/Java solution

Python and Java implementations typically use the same sliding window logic with two pointers and a zero counter. Iterate through the array, update the window boundaries when more than one zero appears, and keep track of the maximum length. The algorithm runs in O(n) time and constant space in both languages.

How to solve Longest Subarray of 1's After Deleting One Element in O(n)?

Use a sliding window that allows at most one zero in the current range. Move the right pointer through the array while counting zeros. If more than one zero appears, move the left pointer forward until the window becomes valid again. Track the maximum window length and subtract one to account for the mandatory deletion.

What is the best approach for Longest Subarray of 1's After Deleting One Element?

The sliding window approach is the most efficient and commonly expected solution. Maintain a window that contains at most one zero and expand it using two pointers. When the window contains more than one zero, move the left pointer until the constraint is satisfied again. This produces the longest valid window in O(n) time and O(1) space.

Is Longest Subarray of 1's After Deleting One Element asked at Google/Amazon/Meta?

Variants of this problem appear in interviews at companies like Amazon, Google, and Meta because it tests sliding window reasoning on binary arrays. Interviewers use it to evaluate whether candidates can manage window constraints and compute optimal subarray lengths efficiently.

What data structure is used in Longest Subarray of 1's After Deleting One Element?

The core solution uses a two-pointer sliding window over an array. Only integer counters and indices are required, so no additional data structures such as hash maps or stacks are necessary for the optimal implementation.

What is the time complexity of Longest Subarray of 1's After Deleting One Element?

The optimal solution runs in O(n) time because the array is scanned once using two pointers. Each element enters and leaves the sliding window at most one time. The space complexity is O(1) since only a few variables are used to track pointers and zero counts.

Longest Subarray of 1's After Deleting One Element solution and explanation

The problem

Approach overview

Approach 1: Sliding Window with Variables

Approach 2: Prefix Sum and Single Pass

Approach 3: Enumeration

Approach 4: Two Pointers

Approach 5: Two Pointers (Optimization)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Longest Subarray of 1's After Deleting One Element solution and explanation

The problem

Approach overview

Approach 1: Sliding Window with Variables

Approach 2: Prefix Sum and Single Pass

Approach 3: Enumeration

Approach 4: Two Pointers

Approach 5: Two Pointers (Optimization)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems