I like to read this solution as a small machine: keep the useful information, throw away the noise. For 1526. Minimum Number of Increments on Subarrays to Form a Target Array, the solution in this repository is mainly a binary search solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. 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: binary search, two pointers.
The notes already sitting in the source point us in the right direction:
- Segment Tree
- https://leetcode.com/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/discuss/757373/C%2B%2B-Segment-Tree-Solution-w-explanation-Accepted
Guide
When?
This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are init, query, count, minNumberOperations.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- 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:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
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(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Segment Tree
02//https://leetcode.com/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/discuss/757373/C%2B%2B-Segment-Tree-Solution-w-explanation-Accepted
03//Runtime: 396 ms, faster than 38.41% of C++ online submissions for Minimum Number of Increments on Subarrays to Form a Target Array.
04//Memory Usage: 90.2 MB, less than 7.90% of C++ online submissions for Minimum Number of Increments on Subarrays to Form a Target Array.
05class SegTree {
06public:
07 vector<int> tree;
08 int n;
09
10 SegTree(vector<int>& arr){
11 n = arr.size();
12 tree = vector<int>(n<<2, -1);
13 init(arr, 0, 0, n-1);
14 }
15
16 int init(vector<int>& arr, int treeIdx, int l, int r){
17 //return the index of minimum value in the node's coverage
18 if(l == r){
19 return tree[treeIdx] = l;
20 }
21
22 int mid = (l+r)>>1;
23 int leftMinIdx = init(arr, (treeIdx<<1)+1, l, mid);
24 int rightMinIdx = init(arr, (treeIdx<<1)+2, mid+1, r);
25
26 //it chooses the index corresponding to smaller value
27 return tree[treeIdx] = (arr[leftMinIdx] <= arr[rightMinIdx]) ? leftMinIdx: rightMinIdx;
28 }
29
30 int query(vector<int>& arr, int treeIdx, int l, int r, int ql, int qr){
31 //node coverage: arr[l:r]
32 //query range: [ql:qr]
33 if(l > qr || ql > r){
34 //no overlap, return an invalid index
35 return -1;
36 }
37
38 //early stopping, avoid TLE!!
39 if(ql == l && qr == r){
40 return tree[treeIdx];
41 }
42
43 if(l == r){
44 //leaf node
45 return tree[treeIdx];
46 }
47
48 int mid = (l+r)>>1;
49
50 if(qr <= mid){
51 //totally falls in left subtree
52 return query(arr, (treeIdx<<1)+1, l, mid, ql, qr);
53 }else if(ql > mid){
54 return query(arr, (treeIdx<<1)+2, mid+1, r, ql, qr);
55 }
56
57 //query range becomes [ql, mid]
58 int leftMinIdx = query(arr, (treeIdx<<1)+1, l, mid, ql, mid);
59 //query range becomes [mid+1, qr]
60 int rightMinIdx = query(arr, (treeIdx<<1)+2, mid+1, r, mid+1, qr);
61
62 if(leftMinIdx == -1) return rightMinIdx;
63 else if(rightMinIdx == -1) return leftMinIdx;
64
65 return (arr[leftMinIdx] <= arr[rightMinIdx]) ? leftMinIdx: rightMinIdx;
66 }
67
68 int count(vector<int>& target, int ql, int qr, int curMin){
69 /*
70 count of incrementation needed to
71 convert from the "initial array" filled with "curMin"
72 to "target" in the range [ql, qr]
73 */
74 //curMin: current minimum in the query range of updated "initial" array
75 if(ql > qr) return 0;
76
77 int minIdx = query(target, 0, 0, n-1, ql, qr);
78 /*
79 now we conduct "res" incrementation to convert "initial"
80 which is filled with "curMin" to filled with "newMin"
81 */
82 int newMin = target[minIdx];
83 int res = newMin - curMin;
84 //divide and conquer
85 res += count(target, ql, minIdx-1, newMin);
86 res += count(target, minIdx+1, qr, newMin);
87 return res;
88 };
89};
90
91class Solution {
92public:
93 int minNumberOperations(vector<int>& target) {
94 SegTree* st = new SegTree(target);
95 int n = target.size();
96 return st->count(target, 0, n-1, 0);
97 }
98};
99
100//https://leetcode.com/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/discuss/754623/Detailed-Explanation
101//Runtime: 368 ms, faster than 43.51% of C++ online submissions for Minimum Number of Increments on Subarrays to Form a Target Array.
102//Memory Usage: 73.2 MB, less than 66.61% of C++ online submissions for Minimum Number of Increments on Subarrays to Form a Target Array.
103//time: O(N), space: O(1)
104class Solution {
105public:
106 int minNumberOperations(vector<int>& target) {
107 int totalOps = target[0];
108 int usableOps = target[0];
109
110 int n = target.size();
111
112 for(int i = 1; i < n; ++i){
113 if(target[i] <= usableOps){
114 usableOps = target[i];
115 }else{
116 //target[i] > usableOps
117 totalOps += (target[i] - usableOps);
118 usableOps = target[i];
119 }
120 }
121
122 return totalOps;
123 }
124};
125
126//refactored
127//Runtime: 296 ms, faster than 73.27% of C++ online submissions for Minimum Number of Increments on Subarrays to Form a Target Array.
128//Memory Usage: 73.4 MB, less than 44.42% of C++ online submissions for Minimum Number of Increments on Subarrays to Form a Target Array.
129//time: O(N), space: O(1)
130class Solution {
131public:
132 int minNumberOperations(vector<int>& target) {
133 int totalOps = target[0];
134
135 int n = target.size();
136
137 for(int i = 1; i < n; ++i){
138 //target[i-1] serves as operationsWeCanReuse
139 if(target[i] > target[i-1]){
140 //extra operations needed: target[i] - target[i-1]
141 totalOps += (target[i] - target[i-1]);
142 }
143 //every time usableOps will be updated to target[i]
144 }
145
146 return totalOps;
147 }
148};
149
150//shortest
151//https://leetcode.com/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/discuss/754674/JavaC%2B%2BPython-Comparison-of-Consecutive-Elements
152//Runtime: 376 ms, faster than 41.85% of C++ online submissions for Minimum Number of Increments on Subarrays to Form a Target Array.
153//Memory Usage: 73.2 MB, less than 78.18% of C++ online submissions for Minimum Number of Increments on Subarrays to Form a Target Array.
154//time: O(N), space: O(1)
155class Solution {
156public:
157 int minNumberOperations(vector<int>& target) {
158 int totalOps = target[0];
159
160 int n = target.size();
161
162 for(int i = 1; i < n; ++i){
163 totalOps += max(target[i]-target[i-1], 0);
164 }
165
166 return totalOps;
167 }
168};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.