Longest subarray contains only 1s

Given an array of integers that contains only 0s and 1s and a positive integer k, you can flip at most k 0s to 1s, return the longest subarray that contains only integer 1 after flipping.

Assumptions:

1. Length of given array is between [1, 20000].

2. The given array only contains 1s and 0s.

3. 0 <= k <= length of given array.

Example 1:

Input: array = [1,1,0,0,1,1,1,0,0,0], k = 2

Output: 7

Explanation: flip 0s at index 2 and 3, then the array becomes [1,1,1,1,1,1,1,0,0,0], so that the length of longest subarray that contains only integer 1 is 7.

Example 2:

Input: array = [1,1,0,0,1,1,1,0,0,0], k = 0

Output: 3

Explanation: k is 0 so you can not flip any 0 to 1, then the length of longest subarray that contains only integer 1 is 3.

High level

if null: return -1 sliding window approach

keep track of current index, current number of 0s, and current length, and global max at each step, increment index by 1

case 1: current is 0 -> shift left window pointer to the right until we "pop" a 0

check current value:

if current == 0: current_zeros += 1

if current_zeros > k: shift the left pointer to the right until current_zeros <= k (in this case, =k)

else

current_max += 1

public class Solution {
  public int longestConsecutiveOnes(int[] nums, int k) {
    if (nums == null) return -1;

    int globalMaxLength = 0;
    int currentLength = 0;
    int currentZeros = 0;

    for (int idx = 0; idx < nums.length; idx++) {
      if (nums[idx] == 0) {
        currentZeros += 1;
        while (currentZeros > k) {
            int leftIdx = idx - currentLength;
            if (nums[leftIdx] == 0) {
              currentZeros -= 1;
            }
            currentLength -= 1;
        }
      }
      currentLength += 1;
      globalMaxLength = Math.max(globalMaxLength, currentLength);
    }
    return globalMaxLength;
  }
}

Last updated

Was this helpful?