Vultr DocsLatest Content

Longest Subarray of 1's After Deleting One Element

Updated on 05 June, 2025
Longest Subarray of 1's After Deleting One Element header image

Problem Statement

In this problem, we are given an array nums consisting entirely of binary digits (0s and 1s). Our task is to remove exactly one element from the array (regardless of its value) and find the length of the longest contiguous subarray made entirely of 1s in the resulting array. If no such subarray exists, the function should return 0. This problem must efficiently handle arrays with up to 100,000 elements, making it crucial to consider efficient algorithms instead of brute-force solutions.

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.

Constraints

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

Approach and Intuition

The challenge is to identify the longest sequence of 1s that can be achieved by removing a single element from the binary sequence. To approach this problem, consider the following steps:

1. Understanding the significance of removing a zero versus a one:

  • Removing a zero potentially connects two separate sequences of ones, potentially increasing the length of a contiguous subarray of ones.
  • Removing a one only decreases the length of a contiguous sequence.

2. Keeping track of sequence lengths:

  • Traverse the array while maintaining information about the sequences of ones and where the zeroes are located. You could use variables to store the length of the current sequence of 1s, the previous sequence of 1s, and the number of 1s since the last zero.
  • You also need to handle the edge cases like start and end sequences of 1s specially since removing elements at the ends has different implications.

3. Calculating the possible maximum:

  • As you identify a zero (which breaks a sequence of ones), calculate what the maximum length of a contiguous sequence would be if that zero were removed. This is done by adding the length of 1s sequences before and after the zero.
  • Keep track of the global maximum length for all identified potential removals.

4. Iterating efficiently:

  • Utilize a single traversal of the array (O(n) complexity), updating sequences and counting lengths as you proceed.
  • This is efficient and avoids the unnecessary re-computation that a naïve method might employ, like considering each possible array resulting from each possible removal.

By systematically tracking sequences of 1s and carefully determining the impact of removing zeroes, this approach efficiently determines the optimal length of a sequence of 1s after one deletion. This strategy directly leverages the structure of contiguous sequences disrupted by zeroes, making it well-suited to large inputs as described in the problem's constraints.

Solutions

  • C++
  • Java
cpp 
class Solution {
public:
    int longestSubarray(vector<int>& arr) {
        int numZeros = 0;
        int maxLen = 0;
        int leftIdx = 0;
        
        for (int rightIdx = 0; rightIdx < arr.size(); rightIdx++) {
            numZeros += (arr[rightIdx] == 0);
                          
            // Adjust the window when more than one zero is inside
            while (numZeros > 1) {
                numZeros -= (arr[leftIdx] == 0);
                leftIdx++;
            }
              
            maxLen = max(maxLen, rightIdx - leftIdx);
        }

        return maxLen;
    }
};

The provided C++ solution efficiently finds the length of the longest subarray consisting of 1's from a given array of integers, after deleting exactly one element (0 or 1). Use a sliding window technique to maintain a window which at most contains one zero.

Here are the essential steps of the solution:

  1. Declare variables to track the number of zeros within the current window (numZeros), the maximum length of subarrays found (maxLen), and the left index of the window (leftIdx).

  2. Iterate through the array using index rightIdx which represents the right boundary of the sliding window.

  3. Increase numZeros if the current element is a zero.

  4. When the count of zeros in the window exceeds one, shift the left boundary of the window (leftIdx) to the right until the window contains at most one zero. Decrease numZeros if a zero is out of the window boundary due to the left index movement.

  5. Calculate and update the maximum subarray length (maxLen) as the width of the window minus one. This ensures we consider the max length after deleting one element.

  6. Continue adjusting the window and updating the lengths until the end of the array is reached.

  7. Return the maximum length found.

This algorithm is efficient and works within a single pass through the array (O(n) complexity), adjusting the window size dynamically based on the count of zero elements. It ensures optimal performance and effectively solves the problem of finding the longest subarray of 1's possible after removing one element.

java 
class Solution {
    public int maxSubarrayWithOneZero(int[] arr) {
        int zeroLimit = 0;
        int maxSubarray = 0;
        int left = 0;
        
        for (int right = 0; right < arr.length; right++) {
            if (arr[right] == 0) zeroLimit++;
                          
            while (zeroLimit > 1) {
                if (arr[left] == 0) zeroLimit--;
                left++;
            }
              
            maxSubarray = Math.max(maxSubarray, right - left);
        }

        return maxSubarray;
    }
}

The provided Java method, maxSubarrayWithOneZero, is designed to find the longest subarray of 1s that can be formed after deleting exactly one 0 from the array.

  • The function accepts an array arr of 0s and 1s and initializes:

    • zeroLimit to track the number of zeroes in the current window.
    • maxSubarray to store the maximum length of the subarray that can be formed.
    • left as a pointer to the start of the window in the array.

  • The algorithm uses a sliding window approach:

    • Traverse each element in the array with a right pointer.
    • If the current element at right is 0, increment zeroLimit.
    • If zeroLimit exceeds 1, which means there are more than one zero in the window, increment the left pointer to shrink the window from the left until zeroLimit is decreased to 1.
    • Continuously update maxSubarray with the maximum length of the current window minus one (since it's inclusive of current zero that potentially could be removed).

  • The function returns the value of maxSubarray which will be the length of the longest possible subarray of 1s achievable by removing one 0.

This method is optimized for efficient scanning of the array, delivering a solution in linear time complexity O(n), where n is the length of the array.

Comments

No comments yet.