Reference: LeetCode
Difficulty: Medium

My Post: Java Solutions with Full Explanations (B-F, DP x2, Constant Time & Space)

Problem

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

We are given a string s of '0's and '1's, and we may flip any '0' to a '1' or a '1' to a '0'.

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

Note:

  1. 1 <= s.length() <= 20000
  2. s only consists of '0' and '1' characters.

Example:

1
2
3
4
5
6
7
8
9
10
11
Input: "00000"
Output: 0

Input: "00110"
Output: 1

Input: "010110"
Output: 2

Input: "00011000"
Output: 2

Follow up: Reduce $O(N^2)$ to $O(N)$

Analysis

Brute-Force

In a brute-force fashion, We are going to consider all monotone increasing strings. For example, if the length is $4$, we consider "1111", "0111", "0011", "0001" , "0000". Specifically, we separate the array in zero-part [0, k] and one-part in [k+1, n-1], where -1 <= k <= n - 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int minFlipsMonoIncr(String s) {
int n = s.length();
int minCount = Integer.MAX_VALUE;
for (int k = -1; k <= n - 1; ++k) { // k is ranging from [-1, n-1]
int count = 0;
// zero-part
for (int i = 0; i <= k; ++i) {
if (s.charAt(i) == '1') ++count;
}
// one-part
for (int i = k + 1; i <= n - 1; ++i) {
if (s.charAt(i) == '0') ++count;
}
minCount = Math.min(minCount, count);
}
return minCount;
}

Time: $O(N^2)$
Space: $O(1)$

Since N could be 20000 at most, we cannot use $O(N^2)$ solution. Usually, if N is greater than 5000, we cannot use $O(N^2)$ approach.

DP (prefix + suffix)

In the counting part, we do a lot of repeated calculation. We denote:

  • prefix[i] as the minimum number of flips (1 to 0) for prefix s[0, i], where 0 <= i <= n - 1.
  • suffix[i] as the minimum number of flips (0 to 1) for suffix s[i, n - 1], where 0 <= i <= n - 1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int minFlipsMonoIncr(String s) {
int n = s.length();
// calculate prefix[] and suffix[]
int[] prefix = new int[n];
int[] suffix = new int[n];
prefix[0] = s.charAt(0) == '1' ? 1 : 0;
suffix[n - 1] = s.charAt(n - 1) == '0' ? 1 : 0;
for (int i = 1, j = n - 2; i < n; ++i, --j) {
prefix[i] = prefix[i - 1] + (s.charAt(i) == '1' ? 1 : 0);
suffix[j] = suffix[j + 1] + (s.charAt(j) == '0' ? 1 : 0);
}
// calculate the count
int minCount = Integer.MAX_VALUE;
for (int k = -1; k <= n - 1; ++k) {
// 0: [0, k], 1: [k+1, n-1]
int left = (k == -1) ? 0 : prefix[k];
int right = (k + 1 == n) ? 0 : suffix[k + 1];
minCount = Math.min(minCount, left + right);
}
return minCount;
}

Time: $O(N)$
Space: $O(N)$

DP (Extra Dimension for States)

Define:

  • dp[i][0] is the minimum number of flips for prefix s[0, i] when s[i] is required to be 0.
  • dp[i][1] is the minimum number of flips for prefix s[0, i] when s[i] is required to be 1.
  • Our goal is to calculate min(dp[n - 1][0], dp[n - 1][1]).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Consider a prefix s[0, i-1]: "001101" + "1" or "0"
a) if new value is s[i] == 0
- dp[i][0] = dp[i-1][0]
- new value is 0, s[i] is required to be 0,
- thus do not flip the new value
- dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + 1
- new value is 0, s[i] is required to be 1,
- thus flip the new value from 0 to 1
- notice whether the last second is 1 or 0 is okay
b) if new value is s[i] == 1
- dp[i][0] = dp[i-1][0] + 1
- new value is 1, s[i] is required to be 0,
- thus flip the new value from 1 to 0
- notice the last second must be 0 (or it is illegal)
- dp[i][1] = min(dp[i-1][0], dp[i-1][1])
- new value is 1, s[i] is required to be 1,
- thus do not flip the new value

Recurrence:

  • If s[i] == 0:
    • dp[i][0] = dp[i-1][0]
    • dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + 1
  • Else s[i] == 1:
    • dp[i][0] = dp[i-1][0] + 1
    • dp[i][1] = min(dp[i-1][0], dp[i-1][1])

Initialization:

  • If s[i] == 0:
    • dp[0][0] = 0
    • dp[0][1] = 1
  • Else s[i] == 1:
    • dp[0][0] = 1
    • dp[0][1] = 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int minFlipsMonoIncr(String s) {
int n = s.length();
int[][] dp = new int[n][2];
// init
if (s.charAt(0) == '0') {
dp[0][0] = 0;
dp[0][1] = 1;
} else {
dp[0][0] = 1;
dp[0][1] = 0;
}
for (int i = 1; i < n; ++i) {
if (s.charAt(i) == '0') {
dp[i][0] = dp[i - 1][0];
dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]) + 1;
} else { // == '1'
dp[i][0] = dp[i - 1][0] + 1;
dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]);
}
}
return Math.min(dp[n - 1][0], dp[n - 1][1]);
}

Time: $O(N)$
Space: $O(N)$

Reduce Space Complexity to Constant Time:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int minFlipsMonoIncr(String s) {
int n = s.length();
int f0, f1;
// init
if (s.charAt(0) == '0') f0 = 0; f1 = 1;
else f0 = 1; f1 = 0;
// dp
for (int i = 1; i < n; ++i) {
if (s.charAt(i) == '0') {
// int minTemp = Math.min(f0, f1);
f0 = f0;
f1 = Math.min(f0, f1) + 1; // actually do not need minTemp
} else { // == '1'
int minTemp = Math.min(f0, f1);
f0 = f0 + 1;
f1 = minTemp; // or calculate the f1 first then get rid of minTemp
}
}
return Math.min(f0, f1);
}

Time: $O(N)$
Space: $O(1)$


Comment