Skip to content

955. Delete Columns to Make Sorted II 👍

  • Time: $O(|\texttt{strs[0]}| \cdot n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  int minDeletionSize(vector<string>& strs) {
    const int n = strs.size();
    int ans = 0;
    // sorted[i] := true if strs[i] < strs[i + 1]
    vector<bool> sorted(n - 1);

    for (int j = 0; j < strs[0].length(); ++j) {
      int i;
      for (i = 0; i + 1 < n; ++i)
        if (!sorted[i] && strs[i][j] > strs[i + 1][j]) {
          ++ans;
          break;
        }
      // Already compared each pair, so update the sorted array if needed.
      if (i + 1 == n)
        for (i = 0; i + 1 < n; ++i)
          sorted[i] = sorted[i] || strs[i][j] < strs[i + 1][j];
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public int minDeletionSize(String[] strs) {
    final int n = strs.length;
    int ans = 0;
    // sorted[i] := true if strs[i] < strs[i + 1]
    boolean[] sorted = new boolean[n - 1];

    for (int j = 0; j < strs[0].length(); ++j) {
      int i;
      for (i = 0; i + 1 < n; ++i)
        if (!sorted[i] && strs[i].charAt(j) > strs[i + 1].charAt(j)) {
          ++ans;
          break;
        }
      // strslready compared each pair, so update the sorted array if needed.
      if (i + 1 == n)
        for (i = 0; i + 1 < n; ++i)
          sorted[i] = sorted[i] || strs[i].charAt(j) < strs[i + 1].charAt(j);
    }

    return ans;
  }
}