Longest Subarray of 1's After Deleting One Element

Medium
247.

Longest Subarray of 1's After Deleting One Element

Longest Subarray of 1's After Deleting One Element is a medium coding problem on arrays, dynamic programming and sliding window, asked in Amazon, Google and Microsoft interviews.

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

Return the size of the longest non-empty subarray of 1s in the resulting array. If no such subarray exists, return 0.

Example 1

Input
nums = [1,1,0,1]
Output
3
Explanation
Deleting the 0 leaves [1,1,1].

Example 2

Input
nums = [0,1,1,1,0,1,1,0,1]
Output
5

Example 3

Input
nums = [1,1,1]
Output
2
Explanation
One element must be deleted even though the array is all 1s.

Constraints

  • 1 <= nums.length <= 40
  • nums[i] is either 0 or 1.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var longestSubarray = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Longest Subarray of 1's After Deleting One Element Solution

Longest Subarray of 1's After Deleting One Element solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Longest Subarray of 1's After Deleting One Element is a medium coding problem on arrays, dynamic programming and sliding window, asked in Amazon, Google and Microsoft interviews.

Problem statement

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

Return the size of the longest non-empty subarray of 1s in the resulting array. If no such subarray exists, return 0.

Example 1

Input: nums = [1,1,0,1]
Output: 3
Explanation: Deleting the 0 leaves [1,1,1].

Example 2

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

Example 3

Input: nums = [1,1,1]
Output: 2
Explanation: One element must be deleted even though the array is all 1s.

Constraints

  • 1 <= nums.length <= 40
  • nums[i] is either 0 or 1.

Hints for Longest Subarray of 1's After Deleting One Element

  1. Hint 1

    Slide a window that is allowed to contain at most one zero.

  2. Hint 2

    The answer for a window is its length minus one — the deleted element, whether it is the zero or a spare 1.

  3. Hint 3

    That - 1 is what makes the all-ones case come out right.

How to solve Longest Subarray of 1's After Deleting One Element

Slide a window containing at most one zero; the answer for a window is its length minus one, since exactly one element must be deleted.

Approach

  1. Expand right; count zeros in the window.
  2. While the window holds more than one zero, advance left (decrementing the count when a zero leaves).
  3. Update the best with right - left (window length minus one).

Why it works

Deleting the single zero in a window leaves a run of length - 1 ones; if the window has no zero, deleting any one element still leaves length - 1. Every longest answer is contained in some such window.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • An all-ones array must return n - 1, which the - 1 handles without a special case.

Reference solution

Python

def longestSubarray(nums) -> int:
    left = zeros = best = 0
    for right, x in enumerate(nums):
        if x == 0:
            zeros += 1
        while zeros > 1:
            if nums[left] == 0:
                zeros -= 1
            left += 1
        best = max(best, right - left)
    return best

Java

public static int longestSubarray(int[] nums) {
    int left = 0, zeros = 0, best = 0;
    for (int right = 0; right < nums.length; right++) {
        if (nums[right] == 0) zeros++;
        while (zeros > 1) {
            if (nums[left] == 0) zeros--;
            left++;
        }
        best = Math.max(best, right - left);
    }
    return best;
}

C++

int longestSubarray(vector<int>& nums) {
    int left = 0, zeros = 0, best = 0;
    for (int right = 0; right < (int) nums.size(); right++) {
        if (nums[right] == 0) zeros++;
        while (zeros > 1) {
            if (nums[left] == 0) zeros--;
            left++;
        }
        best = max(best, right - left);
    }
    return best;
}

JavaScript

var longestSubarray = function(nums) {
    let left = 0, zeros = 0, best = 0;
    for (let right = 0; right < nums.length; right++) {
        if (nums[right] === 0) zeros++;
        while (zeros > 1) {
            if (nums[left] === 0) zeros--;
            left++;
        }
        const len = right - left;
        if (len > best) best = len;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming