The trick here is to name the state correctly, then let the implementation follow. For 944. Delete Columns to Make Sorted, the solution in this repository is mainly a greedy solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: greedy.
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are minDeletionSize.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(\mathcal{A})O(A), where \mathcal{A}A is the total content of A.
- Space: O(1)O(1).
Guide
C++ Solution
Your submission
The accepted solution
01/**
02We are given an array A of N lowercase letter strings, all of the same length.
03
04Now, we may choose any set of deletion indices, and for each string, we delete all the characters in those indices. The remaining rows of strings form columns when read north to south.
05
06For example, if we have an array A = ["abcdef","uvwxyz"] and deletion indices {0, 2, 3}, then the final array after deletions is ["bef","vyz"], and the remaining columns of A are ["b","v"], ["e","y"], and ["f","z"]. (Formally, the c-th column is [A[0][c], A[1][c], ..., A[A.length-1][c]].)
07
08Suppose we chose a set of deletion indices D such that after deletions, each remaining column in A is in non-decreasing sorted order.
09
10Return the minimum possible value of D.length.
11
12
13
14Example 1:
15
16Input: ["cba","daf","ghi"]
17Output: 1
18Explanation:
19After choosing D = {1}, each column ["c","d","g"] and ["a","f","i"] are in non-decreasing sorted order.
20If we chose D = {}, then a column ["b","a","h"] would not be in non-decreasing sorted order.
21Example 2:
22
23Input: ["a","b"]
24Output: 0
25Explanation: D = {}
26Example 3:
27
28Input: ["zyx","wvu","tsr"]
29Output: 3
30Explanation: D = {0, 1, 2}
31
32
33Note:
34
351 <= A.length <= 100
361 <= A[i].length <= 1000
37**/
38
39/**
40Solution
41Approach 1: Greedy
42Intuition
43
44If a column isn't sorted, it can't be part of the final answer.
45
46Algorithm
47
48For each column, check if its sorted. If it isn't, it must be deleted, so we add 1 to the final answer.
49
50
51Complexity Analysis
52
53Time Complexity: O(\mathcal{A})O(A), where \mathcal{A}A is the total content of A.
54
55Space Complexity: O(1)O(1).
56**/
57
58//Your runtime beats 98.76 % of cpp submissions.
59class Solution {
60public:
61 int minDeletionSize(vector<string>& A) {
62 int D=0;
63 vector<string> B;
64 //iterate A by column
65 for(int j = 0; j < A[0].size(); j++){
66 bool nonDecreasing = true;
67 for(int i = 0; i < A.size()-1; i++){
68 if(A[i+1][j]<A[i][j]){ //latter char should be greater or equal to current char
69 nonDecreasing = false;
70 }
71 }
72 if(!nonDecreasing) D+=1;
73 }
74 return D;
75 }
76};Cost