926. Flip String to Monotone Increasing
Problem Description
The problem presents us with a binary string s
which consists only of the characters '0' and '1'. A monotone increasing binary string is defined as one where all '0's appear before any '1's. This means that there is no '1' that comes before a '0' in the string.
However, the input string s
may not be monotone increasing already, so we need to transform it into one by flipping some of its characters. Flipping a character means changing a '0' to a '1' or a '1' to a '0'. The objective is to perform the minimum number of such flips so that the resulting string is monotone increasing.
We need to return the smallest number of flips necessary to convert the string s
into a monotone increasing string.
Intuition
To solve this problem, we can use a dynamic programming approach to keep track of the minimum flips required to make prefixes and suffixes of the string monotone increasing. The core of the solution revolves around recognizing that for any position in the string, we can split the string into two parts:
- the prefix (all the characters before this position), which we want to turn into all '0's,
- and the suffix (all the characters from this position), which we want to turn into all '1's.
Now, if we know how many flips it would take to turn the prefix into all '0's and the suffix into all '1's, the total flips for the whole string would be the sum of both.
To compute these efficiently, we build two arrays, left
and right
.
- The
left
array at positioni
contains the number of flips to turn all characters from0 to i-1
into '0's (note this includes the character at positioni-1
). - The
right
array at positioni
contains the number of flips to turn all characters fromi to n-1
into '1's.
With these arrays, we iterate through each position in the string, representing all possible split points, compute the sum of flips from the left
and right
arrays for that position, and keep track of the minimum sum seen. After going through all the split points, the minimum sum found will be our answer, the least number of flips required to make the string monotone increasing.
Learn more about Dynamic Programming patterns.
Solution Approach
The solution uses dynamic programming to minimize the number of flips needed to make the string monotone increasing. Here’s a step-by-step breakdown of how the provided code accomplishes this task:
-
Initialize two arrays,
left
andright
, both of sizen+1
, wheren
is the length of the strings
. These arrays will be used to store the cumulative number of '1's in theleft
array (from the start of the string to the current index) and the cumulative number of '0's in theright
array (from the current index to the end of the string), respectively. -
Populate the
left
array by iterating from1
ton+1
(inclusive). For each indexi
inleft
, increment the current value by 1 if the corresponding character in the strings[i - 1]
is '1'. This gives us the number of '1's that would need to be flipped to '0's if the split is made after indexi-1
. -
Populate the
right
array by iterating fromn-1
down to0
(inclusive). For each indexi
inright
, increment the current value by 1 if the corresponding character in the strings[i]
is '0'. This gives us the number of '0's that would need to be flipped to '1's if the split is made before indexi
. -
Now, we must determine the optimal split point. Set an initial
ans
value to a large number, representing the upper bound of the flips (the code uses0x3F3F3F3F
as this value). -
Iterate through each possible split point (from
0
ton+1
inclusive). At each split pointi
, compute the total flips required by addingleft[i]
(flips required for the prefix to become all '0's) andright[i]
(flips required for the suffix to become all '1's). -
Update
ans
with the minimum between the currentans
and the total flips for the current split positioni
. -
After completing the iteration through all split points,
ans
will contain the minimum number of flips required to make the original strings
monotone increasing.
The algorithm efficiently uses dynamic programming to compute the answer in O(n)
time, where n
is the length of the string. It avoids recalculation of the cumulative sums by storing them in the left
and right
arrays, which is a common technique used in dynamic programming to optimize for time complexity. The code does not use any complicated data structures, relying only on arrays for storage, which makes for an elegant and efficient solution.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider an example to illustrate the solution approach. Assume we have the binary string s = "00110"
which we want to convert into a monotone increasing string using the minimum number of flips.
Step-by-Step Process:
-
Initialize Arrays:
- Our string
s
hasn = 5
characters, so we initializeleft
andright
arrays of sizen+1
, which is6
in this case.
- Our string
-
Populate the
left
Array:- The
left
array tracks the cumulative number of flips to turn all characters to '0's. We iterate through the string and ourleft
array will be built as follows:1Initialize left = [0, 0, 0, 0, 0, 0] 2After processing '0': left = [0, 0, 0, 0, 0, 0] 3After processing '0': left = [0, 0, 0, 0, 0, 0] 4After processing '1': left = [0, 0, 1, 1, 1, 1] 5After processing '1': left = [0, 0, 1, 2, 2, 2] 6After processing '0': left = [0, 0, 1, 2, 2, 2]
- The
-
Populate the
right
Array:- The
right
array tracks the cumulative number of flips to turn all characters to '1's. We iterate from the end of the string and form ourright
array as:1Initialize right = [0, 0, 0, 0, 0, 0] 2After processing '0': right = [1, 1, 1, 1, 1, 0] 3After processing '1': right = [1, 1, 1, 1, 0, 0] 4After processing '1': right = [1, 1, 1, 0, 0, 0] 5After processing '0': right = [1, 1, 0, 0, 0, 0] 6After processing '0': right = [1, 0, 0, 0, 0, 0]
- The
-
Determine Optimal Split Point:
- We set our initial answer as
ans = Infinity
(or a very large value) for comparison purposes. - We then iterate through the possible split points to calculate the minimum flips:
1At split 0: flips = left[0] + right[0] = 0 + 1 = 1 2At split 1: flips = left[1] + right[1] = 0 + 0 = 0 3At split 2: flips = left[2] + right[2] = 0 + 0 = 0 4At split 3: flips = left[3] + right[3] = 1 + 0 = 1 5At split 4: flips = left[4] + right[4] = 2 + 0 = 2 6At split 5: flips = left[5] + right[5] = 2 + 0 = 2
- We set our initial answer as
-
Find Minimum Flips:
- The minimum number of flips required to make the string monotone increasing occurs at split positions 1 and 2, with
0
flips. - Thus,
ans = 0
.
- The minimum number of flips required to make the string monotone increasing occurs at split positions 1 and 2, with
Therefore, the given string s = "00110"
requires 1 flip to become a monotone increasing string. The correct answer is 1.
This example clearly demonstrates that by keeping track of the number of flips for making all characters to the left '0's and all characters to the right '1's for every position, we can easily compute the minimum total number of flips needed by considering all possible split points.
Solution Implementation
1class Solution:
2 def minFlipsMonoIncr(self, s: str) -> int:
3 # Calculate the length of the input string
4 length = len(s)
5
6 # Initialize the arrays to hold the number of 1s to the left (inclusive)
7 # and the number of 0s to the right (inclusive) of each position
8 ones_to_left = [0] * (length + 1)
9 zeros_to_right = [0] * (length + 1)
10
11 # Variable to hold the final minimum flips answer
12 min_flips = float('inf')
13
14 # Populate the ones_to_left array by counting the number of 1s to the left of each position
15 for i in range(1, length + 1):
16 ones_to_left[i] = ones_to_left[i - 1] + (1 if s[i - 1] == '1' else 0)
17
18 # Populate the zeros_to_right array by counting the number of 0s to the right of each position
19 for i in reversed(range(length)):
20 zeros_to_right[i] = zeros_to_right[i + 1] + (1 if s[i] == '0' else 0)
21
22 # Calculate the minimum flips required for a monotonically increasing string at each position
23 # by adding the number of 1s to the left and 0s to the right for every possible split
24 for i in range(0, length + 1):
25 min_flips = min(min_flips, ones_to_left[i] + zeros_to_right[i])
26
27 # Return the minimum number of flips required to make the string monotonically increasing
28 return min_flips
29
1class Solution {
2
3 /**
4 * Calculate the minimum number of flips to make a binary string monotone increasing.
5 *
6 * @param s The input binary string.
7 * @return The minimum number of flips.
8 */
9 public int minFlipsMonoIncr(String s) {
10 int length = s.length(); // Length of the input string
11
12 // Create arrays to store the prefix and suffix sums.
13 int[] prefixOnes = new int[length + 1];
14 int[] suffixZeros = new int[length + 1];
15
16 // To hold the cumulative minimum number of flips.
17 int minFlips = Integer.MAX_VALUE;
18
19 // Calculate the prefix sums of 1s from the beginning of the string to the current position.
20 for (int i = 1; i <= length; i++) {
21 prefixOnes[i] = prefixOnes[i - 1] + (s.charAt(i - 1) == '1' ? 1 : 0);
22 }
23
24 // Calculate the suffix sums of 0s from the end of the string to the current position.
25 for (int i = length - 1; i >= 0; i--) {
26 suffixZeros[i] = suffixZeros[i + 1] + (s.charAt(i) == '0' ? 1 : 0);
27 }
28
29 // Iterate through all possible positions to split the string into two parts
30 // and find the minimum number of flips by combining the count of 1s in the prefix
31 // and the count of 0s in the suffix.
32 for (int i = 0; i <= length; i++) {
33 minFlips = Math.min(minFlips, prefixOnes[i] + suffixZeros[i]);
34 }
35
36 // Return the cumulative minimum number of flips.
37 return minFlips;
38 }
39}
40
1class Solution {
2public:
3 // Function that returns the minimum number of flips to make the string monotonically increasing.
4 int minFlipsMonoIncr(string s) {
5 int size = s.size();
6 vector<int> prefixOnes(size + 1, 0), suffixZeroes(size + 1, 0);
7 int minFlips = INT_MAX;
8
9 // Populate the prefixOnes to count the number of 1's from the start.
10 for (int i = 1; i <= size; ++i) {
11 prefixOnes[i] = prefixOnes[i - 1] + (s[i - 1] == '1');
12 }
13
14 // Populate the suffixZeroes to count the number of 0's from the end.
15 for (int i = size - 1; i >= 0; --i) {
16 suffixZeroes[i] = suffixZeroes[i + 1] + (s[i] == '0');
17 }
18
19 // For each position in the string, calculate the total flips
20 // by adding the number of 1's in the prefix to the number of 0's in the suffix.
21 // This sum represents the number of flips to make the string monotonically increasing
22 // if the cut is made between the current position and the next.
23 for (int i = 0; i <= size; i++) {
24 // Find the minimum number of flips.
25 minFlips = min(minFlips, prefixOnes[i] + suffixZeroes[i]);
26 }
27
28 return minFlips;
29 }
30};
31
1/**
2 * Calculates the minimum number of flips needed to make a binary string
3 * increasing (each '0' should come before each '1').
4 *
5 * @param {string} s - The binary string to be processed.
6 * @return {number} - The minimum number of flips required.
7 */
8const minFlipsMonoIncr = (s: string): number => {
9 const n: number = s.length;
10 let prefixSum: number[] = new Array(n + 1).fill(0);
11
12 // Compute the prefix sum of the number of '1's in the string
13 for (let i = 0; i < n; ++i) {
14 prefixSum[i + 1] = prefixSum[i] + (s[i] === '1' ? 1 : 0);
15 }
16
17 let minFlips: number = prefixSum[n]; // Initialize minFlips with total number of '1's
18
19 // Try flipping at each position, find the point that minimizes the
20 // number of flips needed to make the string monotonically increasing
21 for (let i = 0; i < n; ++i) {
22 const flipsIfSplitHere: number =
23 prefixSum[i] + // Number of '1's to flip to '0's before position i
24 (n - i - (prefixSum[n] - prefixSum[i])); // Number of '0's to flip to '1's after position i, excluding i
25
26 minFlips = Math.min(minFlips, flipsIfSplitHere);
27 }
28
29 return minFlips;
30};
31
Time and Space Complexity
Time Complexity
The given code computes the minimum number of flips needed to make a binary string monotonically increasing using dynamic programming. The main operations are iterating through the string twice and computing the minimum in another pass. Let's break it down:
-
Initializing two arrays,
left
andright
, each of sizen + 1
, wheren
is the length of the strings
. This takesO(1)
time as it's just initializing the lists with zeros. -
A single for-loop to fill the
left
array. The loop runsn
times (wheren
is the length of the strings
), resulting in a complexity ofO(n)
. -
Another single for-loop in reverse to fill the
right
array, which is alsoO(n)
. -
A final loop that goes from
0
ton
to find theans
(minimum flips needed). This loop also runsn + 1
times and themin
operation inside it takesO(1)
time. The total time complexity for this step isO(n)
.
Therefore, the overall time complexity is the sum of the individual complexities: O(n) + O(n) + O(n) = O(3n)
. Since constant factors are ignored in big O notation, the final time complexity simplifies to O(n)
.
Space Complexity
The space complexity is the amount of additional memory space required to execute the code, which depends on the size of the input:
-
Two arrays
left
andright
each of lengthn + 1
are created. Hence, the space taken by these arrays is2 * (n + 1)
. -
Constant space is used for variables
n
,ans
, and the loop indices, which isO(1)
.
Thus, the total space complexity is O(2n + 2)
which simplifies to O(n)
as lower order terms and constant factors are dropped in big O notation.
Learn more about how to find time and space complexity quickly using problem constraints.
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___
in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
12
1public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
1function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.