Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1004.html

Level

Medium

Description

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

Solution

Loop over the array and store the start index of the subarray and the number of zeros in the subarray.

Initially, the start index start is 0, and the number of zeros zerosCount is 0. For each index i from 0 to A.length - 1, if A[i] == 0, then increase zerosCount by 1. As long as zerosCount <= K, all zeros met so far can be changed to ones. If at one step zerosCount > K, then move start forward until the number of zeros in the subarray (from index start to index i) is not more than K. At each index i, update the max consecutive ones using i - start + 1. Finally, return the max consecutive ones.

Code

  • 
public class Max_Consecutive_Ones_III {
    class Solution {
        public int longestOnes(int[] nums, int k) {
            int res = 0, zero = 0, left = 0;

            for (int right = 0; right < nums.length; ++right) {
                if (nums[right] == 0) ++zero;
                while (zero > k) {
                    if (nums[left++] == 0) --zero;
                }
                res = Math.max(res, right - left + 1);
            }

            return res;
        }
    }
}


############

class Solution {
    public int longestOnes(int[] nums, int k) {
        int l = 0, r = 0;
        while (r < nums.length) {
            if (nums[r++] == 0) {
                --k;
            }
            if (k < 0 && nums[l++] == 0) {
                ++k;
            }
        }
        return r - l;
    }
}

  • // OJ: https://leetcode.com/problems/max-consecutive-ones-iii/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int longestOnes(vector<int>& A, int k) {
        int i = 0, j = 0, cnt = 0, N = A.size(), ans = 0;
        while (j < N) {
            cnt += A[j++] == 0;
            while (cnt > k) cnt -= A[i++] == 0;
            ans = max(ans, j - i);
        }
        return ans;
    }
};

  • class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        res, zero, left = 0, 0, 0

        for right in range(len(nums)):
            if nums[right] == 0:
                zero += 1
            while zero > k:
                if nums[left] == 0:
                    zero -= 1
                left += 1
            res = max(res, right - left + 1)

        return res


class Solution_followup:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:

        res, left, k = 0, 0, 1
        q = deque()

        for right in range(len(nums)):
            if nums[right] == 0:
                q.append(right)
            if len(q) > k:
                left = q.popleft() + 1
            res = max(res, right - left + 1) # max-check every for iteration
            
        return res

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        l = r = -1
        while r < len(nums) - 1:
            r += 1
            if nums[r] == 0:
                k -= 1
            if k < 0:
                l += 1
                if nums[l] == 0:
                    k += 1
        return r - l

############

# 1004. Max Consecutive Ones III
# https://leetcode.com/problems/max-consecutive-ones-iii/

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        n = len(nums)
        i = 0
        
        for j in range(n):
            if nums[j] == 0:
                k -= 1
            
            if k < 0:
                if nums[i] == 0:
                    k += 1
                
                i += 1
        
        return j - i + 1


  • func longestOnes(nums []int, k int) int {
	l, r := -1, -1
	for r < len(nums)-1 {
		r++
		if nums[r] == 0 {
			k--
		}
		if k < 0 {
			l++
			if nums[l] == 0 {
				k++
			}
		}
	}
	return r - l
}

  • function longestOnes(nums: number[], k: number): number {
    const n = nums.length;
    let l = 0;
    for (const num of nums) {
        if (num === 0) {
            k--;
        }
        if (k < 0 && nums[l++] === 0) {
            k++;
        }
    }
    return n - l;
}


  • impl Solution {
    pub fn longest_ones(nums: Vec<i32>, mut k: i32) -> i32 {
        let n = nums.len();
        let mut l = 0;
        for num in nums.iter() {
            if num == &0 {
                k -= 1;
            }
            if k < 0 {
                if nums[l] == 0 {
                    k += 1;
                }
                l += 1;
            }
        }
        (n - l) as i32
    }
}

All Problems

All Solutions