Delete Columns to Make Sorted II LeetCode solution in C++

1
// in this i have iterated for every column and then for every string
2
// i have used array arr[101] in order to store wich indices are valid and which
3
// are not i have taken an array of positions(vector) done[101] to find at which
4
// previous locations i found this particular (jth index string ) to be smaller
5
// than its successor
6

7
class Solution {
8
 public:
9
  int arr[101] = {0};    // arr is to check which columns are valid(0) and invalid(-1)
10
  vector<int> done[101]; // where u found string j was greater than string j+1
11
                         // ,u put it into vector
12

13
  // below is a helper function in order to check all the locations (at which
14
  // string j has been classified as done ) are still present or not
15
  bool check(vector<int> &a) {
16
    for (int i : a) {
17
      if (arr[i] != -1) {
18
        return 1;
19
      }
20
    }
21
    return 0;
22
  }
23
  int minDeletionSize(vector<string> &strs) {
24
    int ans = 0;
25
    // for iterating columns
26
    for (int i = 0; i < strs[0].size(); i++) {
27
      // for iterating the strings
28
      for (int j = 0; j < strs.size() - 1; j++) {
29
        if ((done[j].size() == 0 || check(done[j]) == 0) && strs[j][i] > strs[j + 1][i]) {
30
          ans++;
31
          arr[i] = -1; // make the column invalid
32
          break;
33
        }
34
        if (strs[j][i] < strs[j + 1][i]) {
35
          done[j].push_back(i); // here we are storing at which index (i) said string j is ok
36
        }
37
      }
38
    }
39

40
    return ans;
41
  }
42
};