LeetCode 1493: Longest Subarray of 1's After Deleting One Element

Explanation

To solve this problem, we can iterate through the binary array and keep track of the lengths of consecutive sequences of 1's. When we encounter a single 0, we can calculate the length of the combined sequence if we were to remove that 0. We need to handle different cases of 0's occurring at the start, end, or in the middle of the array. The maximum length we find throughout the iteration will be our answer.

Algorithm

1. Initialize variables: countOnes to count consecutive 1's, prevCount to store the previous count, currCount for the current count, and maxLen to store the maximum length found.
2. Iterate through the binary array:
   • If the current element is 1, increment currCount.
   • If the current element is 0:
     • Update maxLen with the maximum of maxLen, prevCount + currCount, and currCount.
     • Update prevCount with currCount.
     • Reset currCount to 0.
3. Update maxLen with the maximum of maxLen, prevCount + currCount, and currCount.
4. Return maxLen.

Time Complexity

The time complexity of this algorithm is O(n) where n is the length of the input array nums.

Space Complexity

The space complexity is O(1) as we are using a constant amount of extra space.

class Solution {
    public int longestSubarray(int[] nums) {
        int countOnes = 0;
        int prevCount = 0;
        int currCount = 0;
        int maxLen = 0;
        
        for (int num : nums) {
            if (num == 1) {
                currCount++;
            } else {
                maxLen = Math.max(maxLen, prevCount + currCount);
                prevCount = currCount;
                currCount = 0;
            }
        }
        
        maxLen = Math.max(maxLen, prevCount + currCount);
        
        return maxLen == nums.length ? maxLen - 1 : maxLen;
    }
}