Max Consecutive Ones III

MEDIUM

Description

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 <= 10⁵
nums[i] is either 0 or 1.
0 <= k <= nums.length

Approaches

Checkout 2 different approaches to solve Max Consecutive Ones III. Click on different approaches to view the approach and algorithm in detail.

Brute Force Approach

This approach involves checking every possible contiguous subarray within the given array. For each subarray, we count the number of zeros. If the count is within the allowed limit k, we consider its length as a potential answer and update our maximum length found so far.

Algorithm

Initialize a variable maxLength to 0 to store the length of the longest valid subarray found.
Use a nested loop structure. The outer loop with index i will determine the starting point of a subarray.
The inner loop with index j will determine the ending point of the subarray, starting from i.
For each subarray defined by [i, j], maintain a count of zeros, zeroCount.
If nums[j] is 0, increment zeroCount.
If zeroCount is less than or equal to k, the current subarray is valid. Calculate its length j - i + 1 and update maxLength = max(maxLength, j - i + 1).
If zeroCount exceeds k, the subarray is invalid. Since any further extension of this subarray (by increasing j) will also be invalid, we can break the inner loop as an optimization.
After checking all possible starting points i, return maxLength.

We use two nested loops to define the start and end of each subarray. The outer loop iterates through all possible start indices i, and the inner loop iterates through all possible end indices j starting from i.

For each subarray nums[i...j], we maintain a count of zeros. If the number of zeros in the current subarray is less than or equal to k, it's a valid subarray. We calculate its length (j - i + 1) and update the maximum length if this subarray is longer than any valid one found previously.

If the number of zeros exceeds k, we can stop extending the current subarray (by breaking the inner loop) because any longer subarray starting at i will also have more than k zeros. This process is repeated for all possible starting positions i.

class Solution {
    public int longestOnes(int[] nums, int k) {
        int maxLength = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int zeroCount = 0;
            for (int j = i; j < n; j++) {
                if (nums[j] == 0) {
                    zeroCount++;
                }
                if (zeroCount <= k) {
                    maxLength = Math.max(maxLength, j - i + 1);
                } else {
                    // Optimization: if zero count exceeds k, no need to extend this subarray
                    break; 
                }
            }
        }
        return maxLength;
    }
}

Complexity Analysis

Time Complexity: O(N^2), where N is the number of elements in `nums`. The two nested loops lead to a quadratic runtime, as in the worst case, we might check all N*(N+1)/2 subarrays.Space Complexity: O(1), as we only use a few variables to store counts and indices, requiring constant extra space.

Pros and Cons

Pros:

Simple to understand and implement.
Directly translates the problem statement into a straightforward solution.

Cons:

Highly inefficient for large input sizes due to its quadratic time complexity.
Will likely result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for the given constraints.

Code Solutions

Checking out 3 solutions in different languages for Max Consecutive Ones III. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Max Consecutive Ones III

Algorithms:

Binary Search

Patterns:

Sliding WindowPrefix Sum

Data Structures:

Array

Companies:

Expedia |SAP |Walmart Labs |Yandex |