[Java/C++/Python] Greedy Solution, O(MN)
Intuition\nSolve it with a greed algorithme.\n\nInitial N empty string.\nFor each column,\nadd the character to each row,\nand check if all rows are still sorte
## **Intuition**\nSolve it with a greed algorithme.\n\nInitial `N` empty string.\nFor each column,\nadd the character to each row,\nand check if all rows are still sorted.\n\nIf not, we have to delete this column.\n<br>\n\n## **Explanation**\nInitial a boolean array `sorted`,\n`sorted[i] = true` if and only if `A[i] < A[i + 1]`,\nthat is to say `A[i]` and `A[i + 1]` are sorted.\n\nFor each col, we check all unsorted rows.\nIf `A[i][j] > A[i + 1][j]`, we need to deleted this col, `res++`.\n\nOtherwise, we can keep this col, and update all sorted rows.\n<br>\n\n\n**Java, Using array, O(MN), 14ms**\n```\n    public int minDeletionSize(String[] A) {\n        int res = 0, n = A.length, m = A[0].length(), i, j;\n        boolean[] sorted = new boolean[n - 1];\n        for (j = 0; j < m; ++j) {\n            for (i = 0; i < n - 1; ++i) {\n                if (!sorted[i] && A[i].charAt(j) > A[i + 1].charAt(j)) {\n                    res++;\n                    break;\n                }\n            }\n            if (i < n - 1) continue;\n            for (i = 0; i < n - 1; ++i) {\n                sorted[i] |= A[i].charAt(j) < A[i + 1].charAt(j);\n            }\n        }\n        return res;\n    }\n```\n\n**C++, Using vector, O(MN), 8ms**\n```\n    int minDeletionSize(vector<string>& A) {\n        int res = 0, n = A.size(), m = A[0].length(), i, j;\n        vector<bool> sorted(n - 1, false);\n        for (j = 0; j < m; ++j) {\n            for (i = 0; i < n - 1; ++i) {\n                if (!sorted[i] && A[i][j] > A[i + 1][j]) {\n                    res++;\n                    break;\n                }\n            }\n            if (i < n - 1) continue;\n            for (i = 0; i < n - 1; ++i) {\n                sorted[i] = sorted[i] || A[i][j] < A[i + 1][j];\n            }\n        }\n        return res;\n    }\n```\n\n**Python, Using list, `O(NM)`, 64ms**\n```\n    def minDeletionSize(self, A):\n        res, n, m = 0, len(A), len(A[0])\n        is_sorted = [0] * (n - 1)\n        for j in range(m):\n            is_sorted2 = is_sorted[:]\n            for i in range(n - 1):\n                if A[i][j] > A[i + 1][j] and is_sorted[i] == 0:\n                    res += 1\n                    break\n                is_sorted2[i] |= A[i][j] < A[i + 1][j]\n            else:\n                is_sorted = is_sorted2\n        return res\n```\n<br>\n\n## More\nOther version of python solution.\n\n**Python, Brute force, `O(NlogN M^2)`\uFF0C 230ms**\n```\n    def minDeletionSize(self, A):\n        res = 0\n        cur = [""] * len(A)\n        for col in zip(*A):\n            cur2 = zip(cur, col)\n            if cur2 == sorted(cur2): cur = cur2\n            else: res += 1\n        return res\n```\n\n\n**Python, Using set, `O(NM)`, 24ms**\n```\n    def minDeletionSize(self, A):\n        res, n, m = 0, len(A), len(A[0])\n        unsorted = set(range(n - 1))\n        for j in range(m):\n            if any(A[i][j] > A[i + 1][j] for i in unsorted):\n                res += 1\n            else:\n                unsorted -= {i for i in unsorted if A[i][j] < A[i + 1][j]}\n        return res\n```\n
[]