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

It is best to use a general solution to deal with this kind of problem. A window [left,right] can be maintained to hold at least k zeros. When it encounters 0, it accumulates the number of zero, and then judges

  • if the number of 0 is greater than k at this time, then shifts the left boundary left to the right,
  • and if the removed nums[left] is 0, then zero decrements by 1.
  • If it is not greater than k, use the number of digits in the window to update res.

Code

Java

  • 
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;
        }
    }
}


  • // 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:
        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

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.

  • class Solution {
    public int longestOnes(int[] A, int K) {
        int max = 0;
        int start = 0;
        int zerosCount = 0;
        int length = A.length;
        for (int i = 0; i < length; i++) {
            int num = A[i];
            if (num == 0)
                zerosCount++;
            while (zerosCount > K) {
                if (A[start] == 0)
                    zerosCount--;
                start++;
            }
            max = Math.max(max, i - start + 1);
        }
        return max;
    }
}

  • // 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:
        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

All Problems

All Solutions