Flip String to Monotone Increasing - Practice Coding Problems

Flip String to Monotone Increasing - Problem

A binary string is monotone increasing if it consists of some number of 0's (possibly none), followed by some number of 1's (also possibly none).

You are given a binary string s. You can flip s[i] changing it from 0 to 1 or from 1 to 0.

Return the minimum number of flips to make s monotone increasing.

Input & Output

Example 1 — Basic Case

$ Input: s = "10011"

› Output: 1

💡 Note: We can flip s[1] = '0' to get "11011", then flip s[2] = '0' to get "11111". Total: 2 flips. Or we can flip s[0] = '1' to get "00011" which is monotone increasing. Total: 1 flip (optimal).

Example 2 — Already Monotone

$ Input: s = "00111"

› Output: 0

💡 Note: String is already monotone increasing (0s followed by 1s), so no flips needed.

Example 3 — All Same Characters

$ Input: s = "1111"

› Output: 0

💡 Note: All 1s is monotone increasing, so no flips needed.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input String

Binary string "10011" that needs to be monotone

Find Optimal Split

Determine best position to separate 0s and 1s

Monotone Result

Flip minimum characters to achieve 0s followed by 1s

Key Takeaway

🎯 Key Insight: At each '0', choose between flipping it to '1' or flipping all previous '1's to '0's - take the minimum cost option.

Asked in

G Google 35 f Facebook 28 a Amazon 22 M Microsoft 18

The key insight is that at each position with a '0', we have two choices: flip it to '1' or flip all previous '1's to '0's. The optimal approach uses dynamic programming to track the minimum flips needed, making the best choice at each step. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Try All Split Points	O(n²)	O(1)	Try every possible split point between 0s and 1s
Dynamic Programming (Optimal)	O(n)	O(1)	Track minimum flips while scanning left to right
Prefix Sum Optimization	O(n)	O(n)	Precompute prefix sums to calculate costs in O(1)

Try All Split Points — Algorithm Steps

Step 1: Try each split position from 0 to n
Step 2: Count 1s before split (need to flip to 0)
Step 3: Count 0s after split (need to flip to 1)
Step 4: Sum the costs and track minimum

Visualization

Tap to expand

Step-by-Step Walkthrough

Split at position 0

All characters become 1s

Split at position i

Characters before i become 0s, after i become 1s

Split at end

All characters become 0s

Code -

solution.c — C

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

int solution(char* s) {
    int n = strlen(s);
    int minFlips = INT_MAX;
    
    // Try each split position (0 to n)
    for (int split = 0; split <= n; split++) {
        int flips = 0;
        
        // Count 1s before split (flip to 0)
        for (int i = 0; i < split; i++) {
            if (s[i] == '1') {
                flips++;
            }
        }
        
        // Count 0s after split (flip to 1)
        for (int i = split; i < n; i++) {
            if (s[i] == '0') {
                flips++;
            }
        }
        
        if (flips < minFlips) {
            minFlips = flips;
        }
    }
    
    return minFlips;
}

int main() {
    char s[100001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0; // Remove newline
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Outer loop for n+1 split positions, inner loop scans n characters

⚠ Quadratic Growth

Space Complexity

O(1)

Only uses constant extra variables for counting

✓ Linear Space

87.0K Views

Medium Frequency

~25 min Avg. Time

2.2K 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

Try All Split Points — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler