Longest Subarray of 1's After Deleting One Element

Longest Subarray of 1's 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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,1,0,1]

› Output: 3

💡 Note: After deleting the element at index 2, we get [1,1,1] which has the longest subarray of 1's with length 3.

Example 2 — All Ones

$ Input: nums = [0,1,1,1,0,1,1,0,1]

› Output: 5

💡 Note: After deleting the element at index 4, we get [0,1,1,1,1,1,0,1] and the longest subarray of 1's is [1,1,1,1,1] with length 5.

Example 3 — All Zeros

$ Input: nums = [1,1,1]

› Output: 2

💡 Note: We must delete one element, so after deleting any element we get [1,1] with length 2.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Array

Binary array with 0's and 1's: [1,1,0,1]

Delete Element

Remove one element (must delete exactly one)

Find Longest

Find longest contiguous subarray of 1's: length 3

Key Takeaway

🎯 Key Insight: Find the longest subarray containing at most one 0, then subtract 1

Asked in

F Facebook 45 a Amazon 38 G Google 32 M Microsoft 28

The key insight is to find the longest subarray with at most one 0, then subtract 1 for the required deletion. The optimal sliding window approach maintains a window with at most one zero and tracks the maximum size. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Two Pass DP	O(n)	O(n)	Calculate prefix and suffix lengths of consecutive 1's
Brute Force	O(n³)	O(1)	Try deleting each element and find longest subarray of 1's
Sliding Window	O(n)	O(1)	Use sliding window to find longest subarray with at most one 0

Two Pass DP — Algorithm Steps

Calculate consecutive 1's ending at each position
Calculate consecutive 1's starting at each position
For each deletion point, sum left[i-1] + right[i+1]

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Left Array

Count consecutive 1's ending at each position

Build Right Array

Count consecutive 1's starting at each position

Combine Results

For each deletion, sum left[i-1] + right[i+1]

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int solution(int* nums, int numsSize) {
    if (numsSize <= 1) return 0;
    
    // Calculate consecutive 1's ending at each position
    int* left = (int*)malloc(numsSize * sizeof(int));
    int count = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == 1) {
            count++;
        } else {
            count = 0;
        }
        left[i] = count;
    }
    
    // Calculate consecutive 1's starting at each position
    int* right = (int*)malloc(numsSize * sizeof(int));
    count = 0;
    for (int i = numsSize - 1; i >= 0; i--) {
        if (nums[i] == 1) {
            count++;
        } else {
            count = 0;
        }
        right[i] = count;
    }
    
    int maxLength = 0;
    // Try deleting each position
    for (int i = 0; i < numsSize; i++) {
        int leftOnes = i > 0 ? left[i - 1] : 0;
        int rightOnes = i < numsSize - 1 ? right[i + 1] : 0;
        maxLength = max(maxLength, leftOnes + rightOnes);
    }
    
    free(left);
    free(right);
    return maxLength;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int size = 0;
    
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] >= '0' && token[0] <= '9') {
            nums[size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    printf("%d\n", solution(nums, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Three linear passes through the array: one for left counts, one for right counts, one for combining

✓ Linear Growth

Space Complexity

O(n)

Two arrays of size n to store prefix and suffix consecutive counts

⚡ Linearithmic Space

78.0K Views

High Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pass DP — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler