Longest Subarray of Ones After Deleting One Element

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.

Examples

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.

Solution

Method 1 - Sliding Window

This problem can be solved similar to: [Longest Subarray with Ones after Replacement](longest-subarray-with-ones-after-replacement).

Intuition

We want the longest subarray of 1's after deleting one element. By using a sliding window, we can keep at most one zero in the window (which represents the deleted element). We expand the window to the right, and if there are more than one zero, we shrink the window from the left until there is at most one zero. The answer is the largest window size minus one (since we must delete one element).

Approach

1. Use two pointers to represent the window: s (start) and e (end).
2. Keep a count of zeros in the window (numDeletes).
3. For each element, expand the window to the right. If a zero is encountered, increment numDeletes.
4. If numDeletes exceeds 1, move the left pointer s forward until there is at most one zero in the window.
5. Track the maximum window size minus one (since one element must be deleted).
6. Return the result.

Code

C++

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int ans = 0, k = 1, s = 0, numDeletes = 0;
        for (int e = 0; e < nums.size(); ++e) {
            if (nums[e] == 0) numDeletes++;
            while (numDeletes > k) {
                if (nums[s] == 0) numDeletes--;
                s++;
            }
            ans = max(ans, e - s);
        }
        return ans;
    }
};

Go

func longestSubarray(nums []int) int {
    ans, k, s, numDeletes := 0, 1, 0, 0
    for e := 0; e < len(nums); e++ {
        if nums[e] == 0 {
            numDeletes++
        }
        for numDeletes > k {
            if nums[s] == 0 {
                numDeletes--
            }
            s++
        }
        if e-s > ans {
            ans = e - s
        }
    }
    return ans
}

Java

class Solution {
    public int longestSubarray(int[] nums) {
        int ans = 0, k = 1, s = 0, numDeletes = 0;
        for (int e = 0; e < nums.length; e++) {
            if (nums[e] == 0) numDeletes++;
            while (numDeletes > k) {
                if (nums[s] == 0) numDeletes--;
                s++;
            }
            ans = Math.max(ans, e - s);
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun longestSubarray(nums: IntArray): Int {
        var ans = 0
        var k = 1
        var s = 0
        var numDeletes = 0
        for (e in nums.indices) {
            if (nums[e] == 0) numDeletes++
            while (numDeletes > k) {
                if (nums[s] == 0) numDeletes--
                s++
            }
            ans = maxOf(ans, e - s)
        }
        return ans
    }
}

Python

class Solution:
    def longestSubarray(self, nums: list[int]) -> int:
        ans = 0
        k = 1
        s = 0
        numDeletes = 0
        for e in range(len(nums)):
            if nums[e] == 0:
                numDeletes += 1
            while numDeletes > k:
                if nums[s] == 0:
                    numDeletes -= 1
                s += 1
            ans = max(ans, e - s)
        return ans

Rust

impl Solution {
    pub fn longest_subarray(nums: Vec<i32>) -> i32 {
        let (mut ans, k, mut s, mut num_deletes) = (0, 1, 0, 0);
        for e in 0..nums.len() {
            if nums[e] == 0 { num_deletes += 1; }
            while num_deletes > k {
                if nums[s] == 0 { num_deletes -= 1; }
                s += 1;
            }
            ans = ans.max(e - s);
        }
        ans as i32
    }
}

TypeScript

class Solution {
    longestSubarray(nums: number[]): number {
        let ans = 0, k = 1, s = 0, numDeletes = 0;
        for (let e = 0; e < nums.length; e++) {
            if (nums[e] === 0) numDeletes++;
            while (numDeletes > k) {
                if (nums[s] === 0) numDeletes--;
                s++;
            }
            ans = Math.max(ans, e - s);
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n), since each element is visited at most twice (once by e, once by s).
• 🧺 Space complexity: O(1), only a few variables are used.

Method 2 - Track Previous and Current Count of 1s

Intuition

Instead of using a sliding window, we can keep track of the number of consecutive 1s before and after each zero. For every zero, the sum of the number of 1s before and after it gives a candidate answer. If the array contains only 1s, we must delete one element, so the answer is n - 1.

Approach

1. Initialize prevCnt (number of 1s before the last zero), cnt (current count of 1s), and ans (result).
2. Iterate through the array:
   • If the current element is 1, increment cnt.
   • If the current element is 0:
     • Update ans as the maximum of ans and cnt + prevCnt.
     • Set prevCnt to cnt and reset cnt to 0.
3. After the loop, update ans with the last segment.
4. If the array contains only 1s, return n - 1 (since one element must be deleted). Otherwise, return ans.

Code

C++

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int prevCnt = 0, cnt = 0, ans = 0, n = nums.size();
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 1) {
                cnt++;
            } else {
                ans = max(ans, cnt + prevCnt);
                prevCnt = cnt;
                cnt = 0;
            }
        }
        ans = max(ans, cnt + prevCnt);
        return ans == n ? ans - 1 : ans;
    }
};

Go

func longestSubarray(nums []int) int {
    prevCnt, cnt, ans := 0, 0, 0
    n := len(nums)
    for i := 0; i < n; i++ {
        if nums[i] == 1 {
            cnt++
        } else {
            if cnt+prevCnt > ans {
                ans = cnt + prevCnt
            }
            prevCnt = cnt
            cnt = 0
        }
    }
    if cnt+prevCnt > ans {
        ans = cnt + prevCnt
    }
    if ans == n {
        return ans - 1
    }
    return ans
}

Java

class Solution {
    public int longestSubarray(int[] nums) {
        int prevCnt = 0, cnt = 0, ans = 0, n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 1) {
                cnt++;
            } else {
                ans = Math.max(ans, cnt + prevCnt);
                prevCnt = cnt;
                cnt = 0;
            }
        }
        ans = Math.max(ans, cnt + prevCnt);
        return ans == n ? ans - 1 : ans;
    }
}

Kotlin

class Solution {
    fun longestSubarray(nums: IntArray): Int {
        var prevCnt = 0
        var cnt = 0
        var ans = 0
        val n = nums.size
        for (i in nums.indices) {
            if (nums[i] == 1) {
                cnt++
            } else {
                ans = maxOf(ans, cnt + prevCnt)
                prevCnt = cnt
                cnt = 0
            }
        }
        ans = maxOf(ans, cnt + prevCnt)
        return if (ans == n) ans - 1 else ans
    }
}

Python

class Solution:
    def longestSubarray(self, nums: list[int]) -> int:
        prev_cnt = 0
        cnt = 0
        ans = 0
        n = len(nums)
        for v in nums:
            if v == 1:
                cnt += 1
            else:
                ans = max(ans, cnt + prev_cnt)
                prev_cnt = cnt
                cnt = 0
        ans = max(ans, cnt + prev_cnt)
        return ans - 1 if ans == n else ans

Rust

impl Solution {
    pub fn longest_subarray(nums: Vec<i32>) -> i32 {
        let (mut prev_cnt, mut cnt, mut ans) = (0, 0, 0);
        let n = nums.len();
        for &v in &nums {
            if v == 1 {
                cnt += 1;
            } else {
                ans = ans.max(cnt + prev_cnt);
                prev_cnt = cnt;
                cnt = 0;
            }
        }
        ans = ans.max(cnt + prev_cnt);
        if ans == n { (ans - 1) as i32 } else { ans as i32 }
    }
}

TypeScript

class Solution {
    longestSubarray(nums: number[]): number {
        let prevCnt = 0, cnt = 0, ans = 0;
        const n = nums.length;
        for (let i = 0; i < n; i++) {
            if (nums[i] === 1) {
                cnt++;
            } else {
                ans = Math.max(ans, cnt + prevCnt);
                prevCnt = cnt;
                cnt = 0;
            }
        }
        ans = Math.max(ans, cnt + prevCnt);
        return ans === n ? ans - 1 : ans;
    }
}

Complexity

• ⏰ Time complexity: O(n), since we scan the array once.
• 🧺 Space complexity: O(1), only a few variables are used.