Problem statement

https://leetcode.com/problems/flip-string-to-monotone-increasing/

Solution 1 - dp

The first idea I thought about when I saw this problem is to use dynamic programming. Let us define by dp(i, k) the state where we are on index i at the moment and we make last element equal to k. From what states we can get to this state? It is for sure dp(i-1, j) and the question is what j we can use? We want our string be increasing, so we must have k>=j, that is j in range(k+1). What price we need to pay? If k == s[i], that is we do not change our sequence, we pay nothing, in opposite case we pay 1.

Complexity

We have O(n) states and at most 2 transactions from one state to another, so overall time and space complexity is O(n). Note, that it works quite slow, because we use lru_cache and not table, but it is fast enough to get AC.

Code

class Solution:
    def minFlipsMonoIncr(self, s):
        s = [int(i) for i in s] + [1]
        
        @lru_cache(None)
        def dp(i, k):
            if i == -1: return 0
            return min([dp(i-1, j) + int(k != s[i]) for j in range(k + 1)])
           
        return dp(len(s) - 1, 1)

Solution 2, accumulate

We can notice, that our monotonic sequence should look like this: 00...0011...11, that is we have some zeroes and then some ones. So, if we find efficient way to check how many flips we need to do to get zeroes on ones on range, we are done. For this we can use cumulative sums: indeed, number of flips can be evaluated in O(1) then! Imagine, that we want ot make first i elements zeroes and the rest ones, then we have two parts:

  1. acc[i] for the first part to make them all zeroes.
  2. n - i - (acc[-1] - acc[i]) for the second part to make all elements ones.

What we need to do now is to traverse all possible i - note there will be n+1 cases, not n, and return minimum.

Complexity

It is O(n) for time and space as well but in practice it works like 10 times faster than previous appaorach.

Code

class Solution:
    def minFlipsMonoIncr(self, s):
        acc, n = [0] + list(accumulate(map(int, s))), len(s)
        return min(2*acc[i] + n - i - acc[-1] for i in range(n+1))