In this post I detail my solution to a LeetCode medium coding question - 926 Flip String to Monotone Increasing using TypeScript.

Code

Here's a snapshot of my code at submission time, passing all test cases with an O(n) runtime and constant O(1) space requirement.

It's not the cleanest (I'm leaving in all comments) but should be readable and contains descriptions of each area.

const countCharsInString = (s : string, target : string) : number => {
    let count = 0

    for(let i = 0; i < s.length; i++) {
        const currentCharacter = s[i]
        if(currentCharacter === target) {
            count++
        }
    }

    return count
}

function minFlipsMonoIncr(s: string): number {
    let onesToLeftCount = 0 
    let zeroesToRightCount = countCharsInString(s, "0")

    let minimumFlipsFound = s.length
    for(let i = 0; i < s.length; i++) {
        minimumFlipsFound = Math.min(
            minimumFlipsFound,
            onesToLeftCount + zeroesToRightCount
        )

        const currentCharacter = s[i]
        if(currentCharacter === "0") {
            zeroesToRightCount--
        // hamytodo - maybe do direct equality check in case more than 0, 1
        } else {
            onesToLeftCount++
        }
    }

    const allOnesCount = countCharsInString(s, "1")
    minimumFlipsFound = Math.min(
            minimumFlipsFound,
            allOnesCount
        )

    return minimumFlipsFound
};

/*
* Given: string of 1s and 0s
* Goal: Find minimum flips needed to make s monotone increasing
    * Monotone increasing: 0s to left, 1s to right
        * 00001111
    * Available operations - flip 0 to 1 or 1 to 0

Best: O(n)

SubProblems:
* A: Finding optimal flip point
    * 1: Keep track of flips needed to left and right, find min of those - O(n), 1
        * onesToLeft (flipsNeededLeft) = 0
        * zeroesToRight (flipsNeededRight) -> O(n)
        * minimumFlipsFound = s.length
        * Iterate over array: O(n)
            * minimumFlipsFound = Math.min(onesToLeft, zeroesToRight)
            * currentValue = .
            * if 1 -> onesToLeft++
            * if 0 -> zeroesToRight--

Options:
* A: Use Sub-A.1
*/

Next Steps

I've compiled my tips for interviewing for software engineering positions into a short blog post - if you're interested check out my Software Engineering inteview guide;