Max Consecutive Ones III

Similar Problems:

- Leetcode: Max Consecutive Ones
- Leetcode: Max Consecutive Ones II
- Leetcode: Max Consecutive Ones III
- Leetcode: Minimum Swaps to Group All 1’s Together
- CheatSheet: Leetcode For Code Interview
- Tag: #slidingwindow, #inspiring

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: 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 }