Leetcode: Max Consecutive Ones III

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. 1 <= A.length <= 20000
  2. 0 <= K <= A.length
  3. 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:
// Blog link: https://code.dennyzhang.com/max-consecutive-ones-iii
// Basic Ideas: slidewindow
//
// Window: max 0 can't be more than K
//
// Think why the result is j-i, instead of j-i+1
//
// Complexity: Time O(n), Space O(1)
func longestOnes(A []int, K int) int {
    i, j := 0, 0
    for ; j<len(A); j++ {
        if A[j] == 0 { K-- }
        if K<0 {
            if A[i] == 0 { K++ }
            i++
        }
    }
    return j-i
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.