1586. Longest Subarray Of 1S After Deleting One Element¶

LeetCode Problem View on GitHub

1586. Longest Subarray of 1's After Deleting One Element

Medium

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.

Solution¶

class Solution {
    public int longestSubarray(int[] nums) {
        int n = nums.length;
        int start = 0, ans = 0, zeroes = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) zeroes++;
            while (zeroes > 1) {
                if (nums[start] == 0) zeroes--;
                start++;
            }
            ans = Math.max(ans, i - start + 1 - zeroes);
        }
        return ans == n ? ans - 1 : ans;
    }
}

Complexity Analysis¶

• Time Complexity: O(?)
• Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here