Table of Contents
Max Consecutive Ones III
Problem Statement
Given a binary array nums and an integer k, return the maximum number of consecutive 1‘s in the array if you can flip at most k 0‘s.
Example 1:
Input: nums = [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: nums = [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.
Constraints:
1 <= nums.length <= 105nums[i]is either0or1.0 <= k <= nums.length
Golang Solution
func longestOnes(nums []int, k int) int {
// 1. traverse from left to right
// right 0 to n-1
//
// 2. Keep track of total Zeroes
// if value if 0
// zeroCounter++
//
// 3. While zeroCounter greater than k
// move left pointer till it becomes equal to k
// if leftIndex value is 0 then
// reduce zeroCounter--
//
// 4. calculate maxlen = max(maxlen , r-l+1)
n := len(nums)
zeroCounter := 0
maxLen := 0
// left pointer is not moved
// until zeroCounter reached to k
leftIndex := 0
for rightIndex := 0; rightIndex < n; rightIndex++ {
if nums[rightIndex] == 0 {
zeroCounter++
}
for zeroCounter > k {
if nums[leftIndex] == 0 {
zeroCounter--
}
// start moving left pointer as we hit k limit
// also reduce zeroCounter when 0 is encountered
leftIndex++
}
maxLen = max(maxLen, rightIndex-leftIndex+1)
}
return maxLen
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
Output
Input
nums = [1,1,1,0,0,0,1,1,1,1,0]
k = 2
Output
6
Input
nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]
k = 3
Output
10Please visit https: https://codeandalgo.com for more such contents
Leave a Reply