# Longest Subarray of 1's After Deleting One Element
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element)
Canonical: https://scaleengineer.com/dsa/problems/longest-subarray-of-1's-after-deleting-one-element
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Tinkoff](https://scaleengineer.com/companies/tinkoff), [Yandex](https://scaleengineer.com/companies/yandex), [VK](https://scaleengineer.com/companies/vk)
---
## 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 <= 105`
* `nums[i]` is either `0` or `1`.

# Approaches
## Brute Force Simulation
This approach directly simulates the process described in the problem. It iterates through each element of the array, considering it for deletion. For each potential deletion, it scans the rest of the array to find the length of the longest subarray of consecutive 1s. The maximum length found across all possible deletions is the final answer.
**Time:** O(N^2), where N is the length of `nums`. The outer loop runs N times, and for each iteration, the inner loop also runs N times. · **Space:** O(1) extra space, as we are not creating new arrays but using indices to simulate deletion.
**Pros:** Simple to understand and implement.; Directly follows the logic of the problem statement.
**Cons:** Highly inefficient for large inputs due to its quadratic time complexity.; Will likely result in a 'Time Limit Exceeded' error on competitive programming platforms for the given constraints.
### Explanation
The brute-force method involves a nested loop structure. The outer loop selects an element to delete, and the inner loop calculates the longest run of 1s in the resulting array. This process is repeated for every element in the input array. While straightforward and easy to understand, its performance degrades significantly as the size of the input array increases.

```java
class Solution {
    public int longestSubarray(int[] nums) {
        int n = nums.length;
        int maxLength = 0;

        for (int i = 0; i < n; i++) {
            // Simulate deleting nums[i]
            int currentLength = 0;
            int maxInTemp = 0;
            for (int j = 0; j < n; j++) {
                if (i == j) continue; // Skip the deleted element

                if (nums[j] == 1) {
                    currentLength++;
                } else {
                    maxInTemp = Math.max(maxInTemp, currentLength);
                    currentLength = 0;
                }
            }
            maxInTemp = Math.max(maxInTemp, currentLength);
            maxLength = Math.max(maxLength, maxInTemp);
        }
        return maxLength;
    }
}
```
### Algorithm
1. Initialize a variable `maxLength` to 0.
2. Iterate through each index `i` from 0 to `n-1`, where `n` is the length of `nums`.
3. For each `i`, simulate the deletion of `nums[i]`.
4. Find the length of the longest subarray of 1s in the array after the simulated deletion.
   a. Initialize `currentLength = 0` and `maxInTemp = 0`.
   b. Iterate through the array from `j = 0` to `n-1`.
   c. If `j` is the index to be deleted (`j == i`), skip it.
   d. If `nums[j]` is 1, increment `currentLength`.
   e. If `nums[j]` is 0, it breaks the sequence of 1s. Update `maxInTemp = Math.max(maxInTemp, currentLength)` and reset `currentLength` to 0.
   f. After the inner loop, perform one final update: `maxInTemp = Math.max(maxInTemp, currentLength)`.
5. Update the overall `maxLength` with the result from the current deletion: `maxLength = Math.max(maxLength, maxInTemp)`.
6. After iterating through all possible deletions, return `maxLength`.

## Dynamic Programming with Pre-computation
A more optimized approach involves pre-calculating information to avoid redundant computations. We can determine, for each position, the length of consecutive 1s ending just before it and starting just after it. By deleting a `0` at a given position, we can merge these two segments of 1s. The maximum possible merged length is our answer.
**Time:** O(N), as it involves three separate linear passes over the array. · **Space:** O(N), for the `left` and `right` arrays used for pre-computation.
**Pros:** Much more efficient than the brute-force approach with linear time complexity.; The logic is systematic and breaks the problem down into smaller, pre-computable parts.
**Cons:** Requires extra space proportional to the input size, which might be a concern for very large inputs under strict memory constraints.
### Explanation
This method uses a dynamic programming-like strategy. We use two auxiliary arrays, `left` and `right`. `left[i]` stores the length of the consecutive sequence of 1s ending at index `i`, and `right[i]` stores the length of the consecutive sequence of 1s starting at index `i`. After populating these two arrays in two separate linear passes, we can find the solution in a third pass. For each index `i` where `nums[i]` is 0, we can find the length of the resulting subarray of 1s by summing `left[i-1]` and `right[i+1]`. We take the maximum of these sums over all possible `0`s to delete. A special case is when the array contains no zeros; in this scenario, we must delete a 1, so the answer is simply the array length minus one.

```java
class Solution {
    public int longestSubarray(int[] nums) {
        int n = nums.length;
        int[] left = new int[n];
        int[] right = new int[n];

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

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

        int maxLength = 0;
        boolean hasZero = false;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                hasZero = true;
                int leftOnes = (i > 0) ? left[i - 1] : 0;
                int rightOnes = (i < n - 1) ? right[i + 1] : 0;
                maxLength = Math.max(maxLength, leftOnes + rightOnes);
            }
        }

        return hasZero ? maxLength : n - 1;
    }
}
```
### Algorithm
1. Create two integer arrays, `left` and `right`, of the same size as `nums`.
2. Populate the `left` array: Iterate from left to right. `left[i]` will store the count of consecutive 1s ending at index `i`. If `nums[i]` is 0, `left[i]` is 0. Otherwise, `left[i] = (i > 0 ? left[i-1] : 0) + 1`.
3. Populate the `right` array: Iterate from right to left. `right[i]` will store the count of consecutive 1s starting at index `i`. If `nums[i]` is 0, `right[i]` is 0. Otherwise, `right[i] = (i < n-1 ? right[i+1] : 0) + 1`.
4. Initialize `maxLength = 0` and a boolean `hasZero = false`.
5. Iterate through the array from `i = 0` to `n-1`. If `nums[i]` is 0, it means we can potentially merge the subarray of 1s to its left and the one to its right.
   a. Set `hasZero = true`.
   b. Calculate the length of the left part: `leftOnes = (i > 0) ? left[i-1] : 0`.
   c. Calculate the length of the right part: `rightOnes = (i < n-1) ? right[i+1] : 0`.
   d. Update `maxLength = Math.max(maxLength, leftOnes + rightOnes)`.
6. After the loop, if `hasZero` is true, it means we found at least one 0 and `maxLength` holds the answer. If `hasZero` is false, it means the array consists of all 1s. Since we must delete one element, the answer is `n-1`.

## Optimal Sliding Window
The most efficient solution uses the sliding window technique. The goal is to find the longest subarray that contains at most one zero. We maintain a window of elements, expand it to the right, and shrink it from the left whenever the condition (at most one zero) is violated. The size of this window minus one gives a candidate for the answer.
**Time:** O(N), because each element is visited at most twice (once by the `right` pointer and once by the `left` pointer). · **Space:** O(1), as we only use a few constant extra variables for pointers and counts.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1).; It's a generalizable pattern applicable to many subarray problems.
**Cons:** The logic, while efficient, can be slightly less intuitive to grasp on the first look compared to more direct methods.
### Explanation
We use two pointers, `left` and `right`, to define the boundaries of our sliding window. We expand the window by moving `right`. We keep a count of zeros within the current window. If the count of zeros exceeds one, we must shrink the window from the left by moving the `left` pointer forward until the zero count is back to one. At each step, the window `[left, right]` is the longest subarray ending at `right` with at most one zero. The length of the subarray of 1s we can form from this window is its size minus one (for the single element we must delete). The size of the window is `right - left + 1`, so the length of the 1s subarray is `right - left`. We continuously update a `maxLength` variable with the maximum `right - left` value seen. This single-pass approach is optimal in both time and space.

```java
class Solution {
    public int longestSubarray(int[] nums) {
        int n = nums.length;
        int left = 0;
        int zeroCount = 0;
        int maxLength = 0;

        for (int right = 0; right < n; right++) {
            if (nums[right] == 0) {
                zeroCount++;
            }

            // Shrink the window until it has at most one zero
            while (zeroCount > 1) {
                if (nums[left] == 0) {
                    zeroCount--;
                }
                left++;
            }

            // The current window is [left, right] and contains at most one zero.
            // The length of the subarray of 1s we can form is window_size - 1.
            // window_size = right - left + 1.
            // So, length of 1s = (right - left + 1) - 1 = right - left.
            maxLength = Math.max(maxLength, right - left);
        }

        return maxLength;
    }
}
```
### Algorithm
1. Initialize `left = 0`, `zeroCount = 0`, and `maxLength = 0`.
2. Use a `right` pointer to iterate through the array from `0` to `n-1`, expanding a window `[left, right]`.
3. If `nums[right]` is 0, increment `zeroCount`.
4. The window is valid as long as it contains at most one zero (`zeroCount <= 1`). If `zeroCount` becomes greater than 1, the window is invalid.
5. Shrink the window from the left by incrementing the `left` pointer until the window is valid again. While shrinking, if `nums[left]` is a 0, decrement `zeroCount`.
6. For each valid window `[left, right]`, it represents a subarray with at most one 0. If we delete one element from this window, the longest possible subarray of 1s has length `(right - left + 1) - 1`, which simplifies to `right - left`.
7. Update `maxLength = Math.max(maxLength, right - left)`.
8. After the `right` pointer has traversed the entire array, `maxLength` will hold the answer.

# Solutions
### Java

```java
class Solution {
public
  int longestSubarray(int[] nums) {
    int n = nums.length;
    int[] left = new int[n];
    int[] right = new int[n];
    for (int i = 1; i < n; ++i) {
      if (nums[i - 1] == 1) {
        left[i] = left[i - 1] + 1;
      }
    }
    for (int i = n - 2; i >= 0; --i) {
      if (nums[i + 1] == 1) {
        right[i] = right[i + 1] + 1;
      }
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      ans = Math.max(ans, left[i] + right[i]);
    }
    return ans;
  }
}

```

### Python

```python
class Solution:
    def longestSubarray(self, nums: List[int]) -> int: n = len(nums) left = [0] * n right = [0] * n for i in range(1, n): if nums[i - 1] == 1: left[i] = left[i - 1] + 1 for i in range(n - 2, - 1, - 1): if nums[i + 1] == 1: right[i] = right[i + 1] + 1 return max(a + b for a, b in zip(left, right))

```

### CPP

```cpp
class Solution {
public:
  int longestSubarray(vector<int> &nums) {
    int n = nums.size();
    vector<int> left(n);
    vector<int> right(n);
    for (int i = 1; i < n; ++i) {
      if (nums[i - 1] == 1) {
        left[i] = left[i - 1] + 1;
      }
    }
    for (int i = n - 2; ~i; --i) {
      if (nums[i + 1] == 1) {
        right[i] = right[i + 1] + 1;
      }
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      ans = max(ans, left[i] + right[i]);
    }
    return ans;
  }
};

```