Max Consecutive Ones II - Practice Coding Problems

Max Consecutive Ones II - Problem

Given a binary array nums, return the maximum number of consecutive 1's in the array if you can flip at most one 0.

You are allowed to flip at most one 0 to 1 to maximize the length of consecutive ones.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,0,1,1,0]

› Output: 4

💡 Note: Flip the first zero: [1,1,1,1,0] gives 4 consecutive 1's. Or flip the last zero: [1,0,1,1,1] gives 3 consecutive 1's. Maximum is 4.

Example 2 — All Ones

$ Input: nums = [1,1,1]

› Output: 3

💡 Note: Already all 1's, no flip needed. Length is 3.

Example 3 — Single Zero

$ Input: nums = [1,0,1]

› Output: 3

💡 Note: Flip the zero: [1,1,1] gives 3 consecutive 1's.

Constraints

1 ≤ nums.length ≤ 10⁵
nums[i] is either 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input Array

Binary array with 0's and 1's

Find Best Flip

Identify optimal zero to flip for maximum consecutive 1's

Output Length

Return maximum possible consecutive 1's

Key Takeaway

🎯 Key Insight: Use sliding window to maintain at most one zero, maximizing consecutive 1's efficiently

Asked in

G Google 35 f Facebook 28 a Amazon 22

The key insight is to use a sliding window that maintains at most one zero. The optimal approach uses two pointers to expand and contract the window, ensuring we never have more than one zero inside. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try Flipping Each Zero	O(n²)	O(1)	Try flipping each 0 to 1 and find the maximum consecutive 1's
Sliding Window - At Most One Zero	O(n)	O(1)	Maintain a window with at most one 0, expand and shrink as needed
Dynamic Programming - Track State	O(n)	O(n)	Track maximum length ending at each position with and without flip

Brute Force - Try Flipping Each Zero — Algorithm Steps

Step 1: Find maximum consecutive 1's without flipping
Step 2: For each 0, flip it temporarily
Step 3: Calculate consecutive 1's with this flip
Step 4: Track maximum length

Visualization

Tap to expand

Step-by-Step Walkthrough

Original Array

Find consecutive 1's without flipping

Try Flipping Each 0

Temporarily flip each 0 to 1

Calculate Maximum

Track best result across all attempts

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int n) {
    int maxLen = 0;
    
    // Case 1: No flip needed
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (nums[i] == 1) {
            count++;
            if (count > maxLen) maxLen = count;
        } else {
            count = 0;
        }
    }
    
    // Case 2: Try flipping each 0
    for (int i = 0; i < n; i++) {
        if (nums[i] == 0) {
            nums[i] = 1;
            
            count = 0;
            int tempMax = 0;
            for (int j = 0; j < n; j++) {
                if (nums[j] == 1) {
                    count++;
                    if (count > tempMax) tempMax = count;
                } else {
                    count = 0;
                }
            }
            
            if (tempMax > maxLen) maxLen = tempMax;
            nums[i] = 0;
        }
    }
    
    return maxLen;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n positions, we scan the array to count consecutive 1's

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

28.5K Views

Medium-High Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try Flipping Each Zero — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler