LeetCode: Max Consecutive Ones III

Posted on August 10, 2019July 26, 2020 by braindenny

Max Consecutive Ones III

Similar Problems:

Given an array A of 0s and 1s, we may change up to K values from 0 to 1.

Return the length of the longest (contiguous) subarray that contains only 1s.

Example 1:

Input: A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
Output: 6
Explanation: 
[1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1.  The longest subarray is underlined.

Example 2:

Input: A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
Output: 10
Explanation: 
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1.  The longest subarray is underlined.

Note:

1 <= A.length <= 20000
0 <= K <= A.length
A[i] is 0 or 1

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution:

// https://code.dennyzhang.com/max-consecutive-ones-iii
// Basic Ideas: sliding window + greedy
//
//   The window will never become smaller
//   Notice: what if the result would be 0?
//
// Complexity: Time O(n), Space O(1)
func longestOnes(A []int, K int) int {
    // A[i...j]
    i, j:=0, 0
    for ; j<len(A); j++ {
        if A[j] == 0 {
            // use a quota
            K--
        }
        if K<0 {
            // Need to try to release a quota
            if A[i] == 0 {
                K++
            }
            i++
        }

    }
    return j-i
}

Solution

// https://code.dennyzhang.com/max-consecutive-ones-iii
// Basic Ideas: sliding window + greedy
//
//   The window will never become smaller
//   Notice: what if the result would be 0?
//
// Complexity: Time O(n), Space O(1)
func longestOnes(A []int, K int) int {
    res := 0
    // A[i...j]
    i:=0
    for j:=0; j<len(A); j++ {
        if A[j] == 0 {
            // use a quota
            K--
        }
        if K>=0 {
            // find a candidate
            if j+1-i > res {
                res = j+1-i
            }
        } else {
            // move the left pointer
            if A[i] == 0 {
                K++
            }
            i++
        }
    }
    return res
}

Post Views: 0