Flip String to Monotone Increasing - Solution & Explanation

Q: Is Flip String to Monotone Increasing easy or hard?

Flip String to Monotone Increasing is classified as a Medium problem. The challenge comes from recognizing the optimal greedy dynamic programming strategy instead of trying all possible flips. Once the prefix-based decision logic is understood, the implementation becomes short and efficient.

Q: Flip String to Monotone Increasing Python/Java solution

In Python or Java, the optimal implementation uses two integer variables: one for the number of ones seen so far and one for the minimum flips required. Iterate through the string characters, update counters based on whether the character is '0' or '1', and compute the minimum flips using a simple min operation. The implementation runs in O(n) time and O(1) space.

Q: How to solve Flip String to Monotone Increasing in O(n)?

Iterate through the string while tracking two variables: the number of '1's seen so far and the minimum flips required. When encountering a '0', choose the cheaper option between flipping that '0' to '1' or flipping all previous '1's to '0'. Update the running minimum using min(flips + 1, ones). This single-pass dynamic programming method achieves O(n) time.

Q: What is the best approach for Flip String to Monotone Increasing?

The Dynamic Programming approach is typically the best solution. It scans the string once while maintaining the number of ones seen and the minimum flips required so far. Each time a '0' appears after some '1's, you decide whether to flip the current '0' or flip previous '1's. This achieves O(n) time and O(1) space.

Q: Is Flip String to Monotone Increasing asked at Google/Amazon/Meta?

Flip String to Monotone Increasing appears in interviews at companies that emphasize string processing and dynamic programming patterns. Variations of the problem have been reported in interviews at companies like Amazon, Google, and Meta because it tests greedy reasoning and prefix-based DP optimization.

Q: What data structure is used in Flip String to Monotone Increasing?

The problem mainly relies on string traversal and counting rather than complex data structures. Solutions typically use prefix sum arrays or constant-space counters to track the number of ones and flips. The key technique is dynamic programming on prefixes of the string.

Q: What is the time complexity of Flip String to Monotone Increasing?

The optimal solutions run in O(n) time where n is the length of the string. Both the Prefix Sum method and the Dynamic Programming approach process the string linearly. The prefix sum approach may use O(n) extra space, while the optimized DP solution only uses O(1) space.

MediumString Dynamic Programming16 min readAsked at: Amazon, Meta, IBM +2

Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given a binary string s. The goal is to flip the minimum number of characters so the string becomes monotone increasing—all 0s appear before any 1s. Any character can be flipped (0 → 1 or 1 → 0), and you must return the minimum number of flips required.

Approach 1: Prefix Sum Method (O(n) time, O(n) space)

This approach tries every possible split point where the string transitions from 0s to 1s. For each index i, the left side should contain only 0s and the right side only 1s. Use prefix sums to count how many 1s appear on the left (these must flip to 0) and how many 0s appear on the right (these must flip to 1). Iterate through all split points and compute leftOnes + rightZeros. The minimum across all splits gives the answer. This technique is a classic application of string processing combined with prefix sum counting.

Approach 2: Dynamic Programming (O(n) time, O(1) space)

Track two running values while scanning the string once. Let ones count how many 1s have appeared so far, and flips represent the minimum flips required up to the current position. When you see a 1, simply increment ones because it fits the monotone pattern. When you see a 0, you have two choices: flip this 0 to 1 (cost flips + 1) or flip all previous 1s to 0 (cost ones). Update flips = min(flips + 1, ones). This greedy-style DP keeps the optimal answer for each prefix and avoids storing extra arrays. The technique is common in dynamic programming problems where decisions depend on previous states.

Recommended for interviews: The Dynamic Programming approach is usually what interviewers expect. It processes the string in one pass, uses constant space, and shows you can convert a global constraint into incremental decisions. The prefix sum approach is still valuable because it demonstrates clear reasoning about split points and counting, but the DP solution shows stronger optimization skills.

Approach 1: Prefix Sum Method

This approach utilizes prefix sums to calculate the minimum number of flips required to make a binary string monotone increasing. The idea is to traverse the string while maintaining a prefix count of '1's and suffix count of '0's. For each position i, calculate how many flips would be necessary to make all characters before i '0' + make all characters from i '1'.

This solution iterates through the string and calculates prefix sums for '1's. Then it computes the potential flips required at each breakpoint to make the string monotone increasing and returns the minimum.

Code

Python C++Java C#JavaScript

Python

C++

Java

JavaScript

Complexity

Time Complexity: O(n) where n is the length of the string.
Space Complexity: O(n) due to the prefix ones array.

Try this approach in the editor →

Approach 2: Dynamic Programming

This approach leverages dynamic programming to find the minimum flips. Two states are maintained for any position: one representing the minimal flips to have a monotone ending with '0' and the other with '1'. Update these states as we traverse the string.

The dynamic programming approach maintains two counters that track the minimal flips for maintaining monotonic sequences. As the string is parsed, appropriate states are updated.

Code

Python C++Java C#JavaScript

Python

C++

Java

JavaScript

Complexity

Time Complexity: O(n) as we traverse across the string once.
Space Complexity: O(1) since only fixed states are maintained.

Try this approach in the editor →

Approach 3: Prefix Sum + Enumeration

First, we count the number of '0's in string s, denoted as tot. We define a variable ans for the answer, initially set ans = tot, which represents the number of flips to change all '0's to '1's.

Then, we can enumerate each position i, change all '1's to the left of position i (including i) to '0', and change all '0's to the right of position i to '1'. We calculate the number of flips in this case, which is i + 1 - cur + tot - cur, where cur represents the number of '0's to the left of position i (including i). We update the answer ans = min(ans, i + 1 - cur + tot - cur).

Finally, return the answer ans.

The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).

Code

Python Java C++Go TypeScript JavaScript

Python

Java

C++

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Prefix Sum Method	Time Complexity: O(n) where n is the length of the string. Space Complexity: O(n) due to the prefix ones array.
Dynamic Programming	Time Complexity: O(n) as we traverse across the string once. Space Complexity: O(1) since only fixed states are maintained.
Prefix Sum + Enumeration	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Prefix Sum Method	O(n)	O(n)	When reasoning about split points or teaching the intuition behind counting flips on both sides
Dynamic Programming	O(n)	O(1)	Best for interviews and production code due to single pass and constant memory

Video Solution

Flip String to Monotone Increasing - Leetcode 926 - Python • NeetCodeIO • 16,024 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Flip String to Monotone Increasing easy or hard?

Flip String to Monotone Increasing is classified as a Medium problem. The challenge comes from recognizing the optimal greedy dynamic programming strategy instead of trying all possible flips. Once the prefix-based decision logic is understood, the implementation becomes short and efficient.

Flip String to Monotone Increasing Python/Java solution

In Python or Java, the optimal implementation uses two integer variables: one for the number of ones seen so far and one for the minimum flips required. Iterate through the string characters, update counters based on whether the character is '0' or '1', and compute the minimum flips using a simple min operation. The implementation runs in O(n) time and O(1) space.

How to solve Flip String to Monotone Increasing in O(n)?

Iterate through the string while tracking two variables: the number of '1's seen so far and the minimum flips required. When encountering a '0', choose the cheaper option between flipping that '0' to '1' or flipping all previous '1's to '0'. Update the running minimum using min(flips + 1, ones). This single-pass dynamic programming method achieves O(n) time.

What is the best approach for Flip String to Monotone Increasing?

The Dynamic Programming approach is typically the best solution. It scans the string once while maintaining the number of ones seen and the minimum flips required so far. Each time a '0' appears after some '1's, you decide whether to flip the current '0' or flip previous '1's. This achieves O(n) time and O(1) space.

Is Flip String to Monotone Increasing asked at Google/Amazon/Meta?

Flip String to Monotone Increasing appears in interviews at companies that emphasize string processing and dynamic programming patterns. Variations of the problem have been reported in interviews at companies like Amazon, Google, and Meta because it tests greedy reasoning and prefix-based DP optimization.

What data structure is used in Flip String to Monotone Increasing?

The problem mainly relies on string traversal and counting rather than complex data structures. Solutions typically use prefix sum arrays or constant-space counters to track the number of ones and flips. The key technique is dynamic programming on prefixes of the string.

What is the time complexity of Flip String to Monotone Increasing?

The optimal solutions run in O(n) time where n is the length of the string. Both the Prefix Sum method and the Dynamic Programming approach process the string linearly. The prefix sum approach may use O(n) extra space, while the optimized DP solution only uses O(1) space.

Ready to solve this problem?

Practice Flip String to Monotone Increasing with our built-in code editor and test cases.

Practice on FleetCode

Minimum Cost to Make All Characters Equal

Problem Info

DifficultyMedium

Acceptance61.5%

Approaches3

Reading time16 min

Asked at

Amazon Meta IBM Expedia Google

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Prefix Sum Method

Code

Complexity

Approach 2: Dynamic Programming

Code

Complexity

Approach 3: Prefix Sum + Enumeration

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents