1493.longest-subarray-of-1s-after-deleting-one-element.md

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

Test Cases

Edge / Corner Cases

• All 0's or all 1's.

Input: [0, 0, 0]
Output: 0

Input: [1, 1, 1]
Output: 3 - 1, we must delete one element.

Breakdowns

1. How to find the longest 1's without deletion?

Iterate all elements, and start counting when meeting the first 1's, then update the answer. Or (Optimized) slding window with 1's.

2. How to find the longest 1's that allow only one 0's?

Sliding window with 0's count, expand the window until we have more than one 0's, then shrink the window from the left until 0's count <= 1.

3. How to find the answer for the input: zero 0's, one 0's, two 0's, all 0's?

• zero 0's: return len(s) - 1
• one 0's: return longest - 1
• two 0's: return longest - 1
• all 0's: return 0

Sliding Window

• Window: the longest substring of 1's with at most k == 1 0's. (There is no 0's or one 0's)
• We can track the number of 0's in the window, and shrink the window when the number of 0's is more than 1.
• If there are all 0's in the window, we can return 0, otherwise, we can return the length of the window - 1.

Follow-up: 1004. Max Consecutive Ones III

fun longestSubarray(nums: IntArray): Int {
    var zeroCount = 0
    var left = 0
    var longest = Int.MIN_VALUE
    for (right in nums.indices) {
        if (nums[right] == 0) zeroCount++
        while (zeroCount > 1) {
            if (nums[left] == 0) zeroCount--
            left++
        }
        longest = maxOf(longest, right - left + 1)
    }

    return if (longest == Int.MIN_VALUE) 0 else longest - 1
}

// Or equivalently
fun longestSubarray(nums: IntArray): Int {
    var count0 = 0
    var left = 0
    var ans = 0 // Here we don't have to use Int.MIN_VALUE, if there are all 0's, the answer is always 0.
    for (right in nums.indices) {
        if (nums[right] == 0) count0++
        while (count0 > 1) {
            if (nums[left] == 0) count0--
            left++
        }
        // Here we don't -1, because we have to delete one element.
        ans = maxOf(ans, right - left)
    }
    return ans
}

If the input is all 0's:

        [0, 0]
         L
         R
count0 = 1
answer = 0

// Next iteration by moving `right`
        [0, 0]
         L
            R
count0 = 1  2 // Start to shrink the window
answer = 0

        [0, 0]
            L
            R
count0 = 1  1 // After shrinking the window by moving `left` and updating `count0`
answer = 0  0