1004.max-consecutive-ones-iii.md

1004. Max Consecutive Ones III

Clarification Questions

• What is the possible range of k? Will k be zero?

Test Cases

Normal Cases

Input: nums = [1,1,0,1,1,1], k = 1
Output: 6

Input: nums = [1,1,0,0,1,1,1], k = 1
Output: 4

Edge / Corner Cases

• All are 0s, but k is not zero.

Input: nums = [0,0,0,0,0], k = 4
Output: 4

• k is zero.

Input: nums = [1,1,1,0,1], k = 0
Output: 3

Sliding Window

• Window: the longest substring of 1's with at most k zeros.
• We extend our window and count the 0's, and shrink the window if the number of 0's is greater than k.

fun longestOnes(nums: IntArray, k: Int): Int {
    var left = 0
    var right = 0
    var count0 = 0
    var maxLength = 0
    for (right in nums.indices) {
        if (nums[right] == 0) count0++
        while (count0 > k) {
            if (nums[left] == 0) count0--
            left++
        }
        maxLength = maxOf(maxLength, right - left + 1)
    }
    return maxLength
}

• Time Complexity: O(n).
• Space Complexity: O(1).

Dynamic Programming

TODO: Try to understand the DP solution.

dp[i][k] represents the longest substring of 1's ending at index i with at most k zeros.

And the state transition is:

• If nums[i] == 1, dp[i][k] = dp[i - 1][k] + 1.

• If nums[i] == 0, dp[i][k] = dp[i - 1][k - 1] + 1.

• Time Complexity: O(n * k).