Flip String to Monotone Increasing
MedPrompt
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.
Example 1:
Input: s = "00110"
Output: 1
Explanation: We flip the last digit to get 00111.Example 2:
Input: s = "010110"
Output: 2
Explanation: We flip to get 011111, or alternatively 000111.Example 3:
Input: s = "00011000"
Output: 2
Explanation: We flip to get 00000000.
Constraints:
1 <= s.length <= 105s[i]is either'0'or'1'.
Approaches
3 approaches with complexity analysis and trade-offs.
A monotone increasing binary string has a structure of some number of 0s followed by some number of 1s. This implies there's a "split point" where the 0s end and the 1s begin. A brute-force approach is to try every possible split point, calculate the number of flips needed for that specific split, and then find the minimum among all possibilities.
Algorithm
- Initialize
min_flipsto a very large number. - Get the length of the string,
n. - Loop
ifrom0ton. Thisirepresents the split point where0s end and1s begin. - Inside the loop, initialize
current_flips = 0. - Calculate flips for the prefix
s[0...i-1]to become all0s. This is done by iterating fromj = 0toi-1and counting the number of'1's. - Calculate flips for the suffix
s[i...n-1]to become all1s. This is done by iterating fromj = iton-1and counting the number of'0's. - Update
min_flips = min(min_flips, current_flips). - After the outer loop finishes,
min_flipswill hold the minimum number of flips required.
Walkthrough
The algorithm iterates through every possible index i from 0 to n (where n is the string length) as the potential split point. For each i, the string is conceptually divided into a prefix s[0...i-1] and a suffix s[i...n-1]. To make the string monotone increasing with this split, the prefix must consist entirely of 0s, and the suffix must consist entirely of 1s. The cost (number of flips) for this split is the count of 1s in the prefix plus the count of 0s in the suffix. We calculate this cost for every possible i and maintain the minimum cost found. The edge cases i=0 (target string is all 1s) and i=n (target string is all 0s) are naturally handled by the loops.
class Solution { public int minFlipsMonoIncr(String s) { int n = s.length(); int minFlips = Integer.MAX_VALUE; // Iterate through all possible split points for (int i = 0; i <= n; i++) { int currentFlips = 0; // Flips for prefix s[0...i-1] to be all '0's for (int j = 0; j < i; j++) { if (s.charAt(j) == '1') { currentFlips++; } } // Flips for suffix s[i...n-1] to be all '1's for (int j = i; j < n; j++) { if (s.charAt(j) == '0') { currentFlips++; } } minFlips = Math.min(minFlips, currentFlips); } return minFlips; }}Complexity
Time
O(n^2) - The outer loop runs `n+1` times. For each iteration, the inner loops scan the entire string to count flips, taking O(n) time. This results in a quadratic time complexity.
Space
O(1) - We only use a few variables to store counts and the minimum value, regardless of the input string size.
Trade-offs
Pros
Simple to understand and implement.
Correctly solves the problem for small inputs.
Cons
Highly inefficient due to nested loops.
Will result in a 'Time Limit Exceeded' error on platforms like LeetCode for the given constraints.
This approach optimizes the brute-force method by avoiding redundant calculations. Instead of recounting the number of 1s in the prefix and 0s in the suffix for each split point, we can precompute these values. We use a prefix sum array to store the number of 1s up to each index and a suffix sum array to store the number of 0s from each index to the end.
Algorithm
- Get the length of the string,
n. - Create a
prefixOnesarray of sizen+1.prefixOnes[i]will store the count of1s ins[0...i-1]. - Populate
prefixOnesby iterating from left to right:prefixOnes[i] = prefixOnes[i-1] + (s.charAt(i-1) == '1' ? 1 : 0). - Create a
suffixZerosarray of sizen+1.suffixZeros[i]will store the count of0s ins[i...n-1]. - Populate
suffixZerosby iterating from right to left:suffixZeros[i] = suffixZeros[i+1] + (s.charAt(i) == '0' ? 1 : 0). - Initialize
min_flipsto a large value (e.g.,n). - Iterate
ifrom0ton(the split point). - For each
i, the cost isprefixOnes[i] + suffixZeros[i]. - Update
min_flips = min(min_flips, cost). - Return
min_flips.
Walkthrough
The cost for a split at index i is the sum of (number of '1's in s[0...i-1]) and (number of '0's in s[i...n-1]). We can precompute these counts to make the calculation for each split point an O(1) operation.
First, we create a prefixOnes array. prefixOnes[i] stores the total count of 1s in the substring s[0...i-1]. This array can be filled in a single pass from left to right.
Second, we create a suffixZeros array. suffixZeros[i] stores the total count of 0s in the substring s[i...n-1]. This array is filled in a single pass from right to left.
Once both arrays are populated, we can iterate through all possible split points i from 0 to n. For each i, the total flips required is simply prefixOnes[i] + suffixZeros[i]. We find the minimum value among all these sums.
class Solution { public int minFlipsMonoIncr(String s) { int n = s.length(); int[] prefixOnes = new int[n + 1]; for (int i = 0; i < n; i++) { prefixOnes[i + 1] = prefixOnes[i] + (s.charAt(i) == '1' ? 1 : 0); } int[] suffixZeros = new int[n + 1]; for (int i = n - 1; i >= 0; i--) { suffixZeros[i] = suffixZeros[i + 1] + (s.charAt(i) == '0' ? 1 : 0); } int minFlips = Integer.MAX_VALUE; for (int i = 0; i <= n; i++) { minFlips = Math.min(minFlips, prefixOnes[i] + suffixZeros[i]); } return minFlips; }}Complexity
Time
O(n) - The solution involves three separate passes over the string (or arrays of its size), each taking linear time. The overall complexity is O(n) + O(n) + O(n) = O(n).
Space
O(n) - We use two arrays, `prefixOnes` and `suffixZeros`, each of size `n+1`, to store the precomputed counts.
Trade-offs
Pros
Efficient with a linear time complexity.
Guaranteed to pass within the time limits for the given constraints.
Cons
Uses extra space proportional to the input size, which might be a concern for very large inputs under strict memory constraints.
This is the most optimal approach, solving the problem in a single pass with constant extra space. It uses a dynamic programming-like logic. As we iterate through the string, we maintain a running count of the minimum flips required to make the prefix seen so far monotone.
Algorithm
- Initialize two integer variables,
flips = 0andones = 0. - Iterate through each character
cof the input strings. - If
cis'1':- Increment the
onescounter.
- Increment the
- If
cis'0':- We have two choices to keep the prefix monotone: flip this
0to1(cost:flips + 1) or keep it as0and flip all previous1s (cost:ones). - Update
flipsto the minimum of these two options:flips = min(flips + 1, ones).
- We have two choices to keep the prefix monotone: flip this
- After the loop completes,
flipsholds the minimum number of flips for the entire string to be monotone increasing. - Return
flips.
Walkthrough
We can solve this problem by iterating through the string just once. We maintain two key variables:
ones: This counter keeps track of the number of1s we have encountered so far in the string.flips: This variable stores the minimum number of flips required to make the prefix of the string processed so far (s[0...i]) monotone increasing.
As we iterate through the string character by character:
- If the character is a
'1', we simply increment theonescount. The current value offlipsis still valid because we can append a1to an already monotone prefix without needing more flips. - If the character is a
'0', we face a choice. To make the current prefixs[0...i]monotone, we can either: a) Flip this'0'to a'1'. The cost for this is the minimum flips for the previous prefix (s[0...i-1]) plus one for the current flip. This isflips + 1. b) Keep this'0'as a'0'. For the prefix to remain monotone and end in0, it must be composed entirely of0s. This means we must flip all the1s we've seen so far. The cost for this isones.
We should choose the option with the minimum cost. Therefore, we update flips = Math.min(flips + 1, ones). After iterating through the entire string, the final value of flips is the minimum number of flips for the whole string.
class Solution { public int minFlipsMonoIncr(String s) { int flips = 0; int ones = 0; for (char c : s.toCharArray()) { if (c == '1') { ones++; } else { // Option 1: Flip this '0' to '1'. Total flips = flips + 1. // Option 2: Keep this '0'. All previous '1's must be flipped. Total flips = ones. flips = Math.min(flips + 1, ones); } } return flips; }}Complexity
Time
O(n) - We perform a single pass through the input string, making the time complexity linear with respect to the string's length.
Space
O(1) - We only use two integer variables (`flips` and `ones`), so the space usage is constant.
Trade-offs
Pros
Optimal solution with O(n) time and O(1) space complexity.
Very concise and efficient implementation.
Cons
The logic, while concise, can be less intuitive to derive compared to the prefix sum approach.
Solutions
Solution
class Solution { public int minFlipsMonoIncr ( String s ) { int n = s . length (); int [] left = new int [ n + 1 ]; int [] right = new int [ n + 1 ]; int ans = Integer . MAX_VALUE ; for ( int i = 1 ; i <= n ; i ++) { left [ i ] = left [ i - 1 ] + ( s . charAt ( i - 1 ) == '1' ? 1 : 0 ); } for ( int i = n - 1 ; i >= 0 ; i --) { right [ i ] = right [ i + 1 ] + ( s . charAt ( i ) == '0' ? 1 : 0 ); } for ( int i = 0 ; i <= n ; i ++) { ans = Math . min ( ans , left [ i ] + right [ i ]); } return ans ; } }/** * @param {string} s * @return {number} */ var minFlipsMonoIncr = function ( s,) { const n = s.length; let presum = new Array(n + 1).fill(0); for (let i = 0; i < n; ++i) { presum[i + 1] = presum[i] + (s[i] == " 1 "); } let ans = presum[n]; for (let i = 0; i < n; ++i) { ans = Math.min(ans, presum[i] + n - i - (presum[n] - presum[i])); } return ans;};class Solution { public: int minFlipsMonoIncr ( string s ) { int n = s . size (); vector < int > left ( n + 1 , 0 ), right ( n + 1 , 0 ); int ans = INT_MAX ; for ( int i = 1 ; i <= n ; ++ i ) { left [ i ] = left [ i - 1 ] + ( s [ i - 1 ] == '1' ); } for ( int i = n - 1 ; i >= 0 ; -- i ) { right [ i ] = right [ i + 1 ] + ( s [ i ] == '0' ); } for ( int i = 0 ; i <= n ; i ++ ) { ans = min ( ans , left [ i ] + right [ i ]); } return ans ; } };class Solution : def minFlipsMonoIncr ( self , s : str ) -> int : n = len ( s ) left , right = [ 0 ] * ( n + 1 ), [ 0 ] * ( n + 1 ) ans = 0x3F3F3F3F for i in range ( 1 , n + 1 ): left [ i ] = left [ i - 1 ] + ( 1 if s [ i - 1 ] == '1' else 0 ) for i in range ( n - 1 , - 1 , - 1 ): right [ i ] = right [ i + 1 ] + ( 1 if s [ i ] == '0' else 0 ) for i in range ( 0 , n + 1 ): ans = min ( ans , left [ i ] + right [ i ]) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.