Knowledge Guide
Home › DSA › Sliding Window

medium Max Consecutive Ones III

Problem Statement

Given a binary array nums containing only 0 and 1 and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.

Examples

Example 1:

Example 2:

Example 3:

Constraints:

Try it yourself

Try solving this question here:

✅ Solution Max Consecutive Ones III

Problem Statement

Given a binary array nums containing only 0 and 1 and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.

Examples

Example 1:

  • Input: nums = [1, 0, 0, 1, 1, 0, 1, 1], k = 2
  • Expected Output: 6
  • Justification: By flipping 0 at the second and fifth index in the list, we get [1, 0, 1, 1, 1, 1, 1, 1], which has 6 consecutive 1s.

Example 2:

  • Input: nums = [1, 0, 1, 1, 0, 0, 1, 1], k = 1
  • Expected Output: 4
  • Justification: By flipping 0 at 1st index, we get [1, 1, 1, 1, 0, 1, 1, 1], with a maximum of 4 consecutive 1s.

Example 3:

  • Input: nums = [1, 0, 0, 1, 1, 0, 1], k = 3
  • Expected Output: 7
  • Justification: By flipping all three zeros, we get [1, 1, 1, 1, 1, 1, 1], which has 7 consecutive 1s.

Constraints:

  • 1 <= nums.length <= 105
  • nums[i] is either 0 or 1.
  • 0 <= k <= nums.length

Solution

To solve this problem, we'll use a sliding window approach. We'll keep a window of 1s that we expand as long as the number of 0s within the window doesn't exceed k. If the number of 0s exceeds k, we'll move the start of the window forward to reduce the number of 0s. This approach ensures that we always have the longest possible window of 1s by changing at most k 0s to 1s.

This approach works effectively because it processes each element in the list once, ensuring that the algorithm runs in linear time. By keeping track of the count of 0s within the current window, we can dynamically adjust the window size to maximize the sequence of consecutive 1s.

Step-by-step Algorithm

  1. Initialization:

    • Initialize two pointers left and right to 0.
    • Initialize max_length to 0 to keep track of the maximum length of consecutive 1s found.
    • Initialize zero_count to 0 to keep track of the number of 0s in the current window.

  2. Expand the window:

    • While right is less than the length of the list nums:
      • If the element at nums[right] is 0, increment zero_count by 1.
      • While zero_count exceeds k (i.e., more than k 0s in the current window):
        • If the element at nums[left] is 0, decrement zero_count by 1.
        • Move the left pointer to the right by 1.
      • Update max_length to be the maximum of its current value and the length of the current window (right - left + 1).
      • Move the right pointer to the right by 1.

  3. Return the result:

    • After the loop ends, return max_length as the result.

Algorithm Walkthrough

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

  1. Initialization:

    • left = 0
    • right = 0
    • max_length = 0
    • zero_count = 0

  2. First Iteration (right = 0):

    • nums[0] is 1.
    • zero_count remains 0.
    • max_length is updated to 1 (window: [1]).
    • Increment right to 1.

  3. Second Iteration (right = 1):

    • nums[1] is 0.
    • Increment zero_count to 1.
    • max_length is updated to 2 (window: [1, 0]).
    • Increment right to 2.

  4. Third Iteration (right = 2):

    • nums[2] is 0.
    • Increment zero_count to 2.
    • max_length is updated to 3 (window: [1, 0, 0]).
    • Increment right to 3.

  5. Fourth Iteration (right = 3):

    • nums[3] is 1.
    • zero_count remains 2.
    • max_length is updated to 4 (window: [1, 0, 0, 1]).
    • Increment right to 4.

  6. Fifth Iteration (right = 4):

    • nums[4] is 1.
    • zero_count remains 2.
    • max_length is updated to 5 (window: [1, 0, 0, 1, 1]).
    • Increment right to 5.

  7. Sixth Iteration (right = 5):

    • nums[5] is 0.
    • Increment zero_count to 3.
    • zero_count exceeds k, so start adjusting left:
      • nums[0] is 1, zero_count remains 3, increment left to 1.
      • nums[1] is 0, decrement zero_count to 2, increment left to 2.
    • max_length remains 5 (window: [0, 1, 1, 0]).
    • Increment right to 6.

  8. Seventh Iteration (right = 6):

    • nums[6] is 1.
    • zero_count remains 2.
    • max_length is updated to 5 (window: [0, 1, 1, 0, 1]).
    • Increment right to 7.

  9. Eighth Iteration (right = 7):

    • nums[7] is 1.
    • zero_count remains 2.
    • max_length is updated to 6 (window: [0, 1, 1, 0, 1, 1]).
    • Increment right to 8, which ends the loop as right equals the length of nums.

  10. Return Result:

    • The final value of max_length is 6.
Image
Image

Code

java
class Solution {

  public int longestOnes(int[] nums, int k) {
    int left = 0, right = 0;
    int max_length = 0;
    int zero_count = 0;

    // Use sliding window to find the longest sequence of 1s with at most k 0s flipped
    while (right < nums.length) {
      // If current element is 0, increase zero_count
      if (nums[right] == 0) {
        zero_count++;
      }

      // If zero_count exceeds k, move left pointer to maintain at most k zeros in window
      while (zero_count > k) {
        if (nums[left] == 0) {
          zero_count--;
        }
        left++;
      }

      // Update max_length if current window is longer
      max_length = Math.max(max_length, right - left + 1);
      right++;
    }

    return max_length;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    System.out.println(
      sol.longestOnes(new int[] { 1, 0, 0, 1, 1, 0, 1, 1 }, 2)
    ); // 6
    System.out.println(
      sol.longestOnes(new int[] { 1, 0, 1, 1, 0, 0, 1, 1 }, 1)
    ); // 4
    System.out.println(sol.longestOnes(new int[] { 1, 0, 0, 1, 1, 0, 1 }, 3)); // 7
  }
}

Complexity Analysis

Time Complexity:

  • The algorithm uses a sliding window approach with two pointers (left and right), which traverse the array only once. Hence, the overall time complexity is , where n is the length of the array.

Space Complexity:

  • The algorithm uses a constant amount of extra space (only a few integer variables), so the space complexity is .
🤖 Don't fully get this? Learn it with Claude

Stuck on Max Consecutive Ones III? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Max Consecutive Ones III** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Max Consecutive Ones III** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Max Consecutive Ones III**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Max Consecutive Ones III**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Maximum Number of Vowels in a SubsLongest Subarray of 1's After Dele →