Optimized O(n * m * m) 6ms beating 100%
IntuitionThis is the optimized version of my solution https://leetcode.com/problems/delete-columns-to-make-sorted-ii/solutions/6363569/greedy-o-m-m-n/
We can ca
# Intuition
This is the optimized version of my solution https://leetcode.com/problems/delete-columns-to-make-sorted-ii/solutions/6363569/greedy-o-m-m-n/
We can cache the all the already-strictly-increasing neighbour row pairs to avoid meaningless comparations.
# Approach
1. When we have found that one row must be strictly smaller than its next row, we mark it.
2. When we next time encounter them, we skip.
3. And when we have cached all the neighbour pairs, we break the loop!
# Complexity
- Time complexity:
O(n * m * m)
- Space complexity:
O(n * m)
# Code
```javascript []
/**
 * @param {string[]} strs
 * @return {number}
 */
var minDeletionSize = function(strs) {
    const len = strs.length, size = strs[0].length
    const prevs = new Array(len).fill('')
    const comparations = new Array(len).fill(false)
    let comparationDoneCount = 0


    let result = 0
    forEachJ:
    for (let j = 0; j < size; j++) {
        const comparationBuffer = []
        for (let i = 1; i < len; i++) {
            if (comparations[i])    continue

            const strA = prevs[i - 1] + strs[i - 1][j]
            const strB = prevs[i] + strs[i][j]
            const comparationResult = strA.localeCompare(strB)
            if (comparationResult > 0) {
                result++
                continue forEachJ
            } else {
                if (comparationResult < 0) {
                    comparationBuffer.push(i)
                }
            }
        }

        for (let i = 0; i < len; i++)
            prevs[i] += strs[i][j]

        for (const index of comparationBuffer) {
            comparations[index] = true
        }
        comparationDoneCount += comparationBuffer.length
        if (comparationDoneCount === len - 1)
            break
    }


    return result
};
```
['JavaScript']