The trick here is to name the state correctly, then let the implementation follow. For 1340. Jump Game V, the solution in this repository is mainly a DFS + memoization 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: DFS + memoization, graph traversal, dynamic programming, two pointers.
The notes already sitting in the source point us in the right direction:
- DFS
- TLE
- 51 / 127 test cases passed.
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are dfs, maxJumps, visited, query, update.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- Sorting is used to make local choices comparable, so the later scan does not have to rediscover order.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- The stack stores unfinished context, which is usually the cleanest way to handle nested or monotonic structure.
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(Nd), space: O(N)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//DFS
02//TLE
03//51 / 127 test cases passed.
04class Solution {
05public:
06 unordered_map<int, unordered_set<int>> graph;
07
08 void dfs(int cur, vector<bool>& visited, int jumps, int& max_jumps){
09 max_jumps = max(max_jumps, jumps);
10 for(const int& nei : graph[cur]){
11 if(!visited[nei]){
12 // cout << cur << ": " << jumps << "->" << nei << endl;
13 visited[nei] = true;
14 dfs(nei, visited, jumps+1, max_jumps);
15 visited[nei] = false;
16 }
17 }
18 };
19
20 int maxJumps(vector<int>& arr, int d) {
21 int n = arr.size();
22
23 for(int i = 0; i < n; ++i){
24 for(int j = i+1; j <= min(i+d, n-1) && arr[i] > arr[j]; ++j){
25 graph[i].insert(j);
26 }
27 for(int j = i-1; j >= max(i-d, 0) && arr[i] > arr[j]; --j){
28 graph[i].insert(j);
29 }
30 }
31
32 int max_jumps = 0;
33
34 for(int start = 0; start < n; ++start){
35 vector<bool> visited(n, false);
36 visited[start] = true;
37 int jumps = 0;
38 dfs(start, visited, 1, jumps);
39 max_jumps = max(max_jumps, jumps);
40 }
41
42 return max_jumps;
43 }
44};
45
46//top-down dp(dfs + memo)
47//https://mp.weixin.qq.com/s/kEQ00_WLqDTG6tbsjQ2Xjw
48//Runtime: 76 ms, faster than 57.67% of C++ online submissions for Jump Game V.
49//Memory Usage: 15.3 MB, less than 48.01% of C++ online submissions for Jump Game V.
50//time: O(Nd), space: O(N)
51class Solution {
52public:
53 int n;
54 vector<int> memo;
55
56 int dfs(vector<int>& arr, int& d, int i){
57 if(memo[i]) return memo[i];
58
59 memo[i] = 1;
60 for(int k = i-1; k >= max(i-d, 0) && arr[k] < arr[i]; --k){
61 memo[i] = max(memo[i], dfs(arr, d, k)+1);
62 }
63 for(int k = i+1; k <= min(i+d, n-1) && arr[k] < arr[i]; ++k){
64 memo[i] = max(memo[i], dfs(arr, d, k)+1);
65 }
66
67 return memo[i];
68 };
69
70 int maxJumps(vector<int>& arr, int d) {
71 n = arr.size();
72
73 memo = vector<int>(n, 0);
74 int ans = 0;
75
76 for(int i = 0; i < n; ++i){
77 ans = max(ans, dfs(arr, d, i));
78 }
79
80 return ans;
81 }
82};
83
84
85//bottom-up DP
86//Hint 1: Use dynamic programming. dp[i] is max jumps you can do starting from index i. Answer is max(dp[i]).
87//Hint 2: dp[i] = 1 + max (dp[j]) where j is all indices you can reach from i.
88//Runtime: 80 ms, faster than 53.12% of C++ online submissions for Jump Game V.
89//Memory Usage: 15.6 MB, less than 31.53% of C++ online submissions for Jump Game V.
90//time: O(NlogN + Nd), space: O(N)
91class Solution {
92public:
93 int maxJumps(vector<int>& arr, int d) {
94 int n = arr.size();
95
96 vector<pair<int, int>> parr(n);
97
98 for(int i = 0; i < n; ++i){
99 parr[i] = {i, arr[i]};
100 }
101
102 sort(parr.begin(), parr.end(),
103 [](const pair<int, int>& p, const pair<int, int>& q){
104 return (p.second == q.second) ? p.first < q.first : p.second < q.second;
105 });
106
107 vector<int> dp(n, INT_MIN);
108 int ans = 0;
109
110 for(pair<int, int>& p : parr){
111 dp[p.first] = 1;
112 for(int k = p.first-1; k >= max(p.first-d, 0) && arr[k] < arr[p.first]; --k){
113 dp[p.first] = max(dp[p.first], dp[k]+1);
114 }
115 for(int k = p.first+1; k <= min(p.first+d, n-1) && arr[k] < arr[p.first]; ++k){
116 dp[p.first] = max(dp[p.first], dp[k]+1);
117 }
118 ans = max(ans, dp[p.first]);
119 // cout << p.first << ", " << dp[p.first] << ", " << ans << endl;
120 }
121
122 return ans;
123 }
124};
125
126//segment tree
127//not understand
128//https://leetcode.com/problems/jump-game-v/discuss/497004/C%2B%2B-Segment-Tree
129//Runtime: 88 ms, faster than 44.60% of C++ online submissions for Jump Game V.
130//Memory Usage: 17.5 MB, less than 17.90% of C++ online submissions for Jump Game V.
131//time: O(NlogN)
132class Solution {
133private:
134 vector<int> tree;
135
136public:
137 int query(int x, int l, int r, int ql, int qr) {
138 if (ql > r || qr < l) {
139 return 0;
140 }
141 if (ql <= l && r <= qr) {
142 return tree[x];
143 }
144 int mid = (l + r) / 2;
145 return max(query(x * 2, l, mid, ql, qr), query(x * 2 + 1, mid + 1, r, ql, qr));
146 }
147
148 void update(int x, int l, int r, int u, int value) {
149 if (l > u || r < u) {
150 return;
151 }
152 if (l == r) {
153 tree[x] = value;
154 return;
155 }
156 int mid = (l + r) / 2;
157 update(x * 2, l, mid, u, value);
158 update(x * 2 + 1, mid + 1, r, u, value);
159 tree[x] = max(tree[x * 2], tree[x * 2 + 1]);
160 }
161
162 int maxJumps(vector<int>& arr, int d) {
163 int n = arr.size();
164 vector<int> bound_l(n), bound_r(n);
165
166 stack<int> stk;
167 for (int i = 0; i < n; ++i) {
168 while (!stk.empty() && arr[stk.top()] <= arr[i]) {
169 bound_r[stk.top()] = min(i - 1, stk.top() + d);
170 stk.pop();
171 }
172 stk.push(i);
173 }
174 while (!stk.empty()) {
175 bound_r[stk.top()] = min(n - 1, stk.top() + d);
176 stk.pop();
177 }
178
179 for (int i = n - 1; i >= 0; --i) {
180 while (!stk.empty() && arr[stk.top()] <= arr[i]) {
181 bound_l[stk.top()] = max(i + 1, stk.top() - d);
182 stk.pop();
183 }
184 stk.push(i);
185 }
186 while (!stk.empty()) {
187 bound_l[stk.top()] = max(0, stk.top() - d);
188 stk.pop();
189 }
190
191 vector<int> order(n);
192 iota(order.begin(), order.end(), 0);
193 sort(order.begin(), order.end(), [&](int i, int j) {return arr[i] < arr[j];});
194
195 vector<int> f(n);
196 tree.resize(n * 4 + 10);
197 for (int id: order) {
198 int prev = 0;
199 if (bound_l[id] < id) {
200 prev = max(prev, query(1, 0, n - 1, bound_l[id], id - 1));
201 }
202 if (id < bound_r[id]) {
203 prev = max(prev, query(1, 0, n - 1, id + 1, bound_r[id]));
204 }
205 f[id] = prev + 1;
206 update(1, 0, n - 1, id, f[id]);
207 }
208
209 return *max_element(f.begin(), f.end());
210 }
211};
212
213//dp, monotonic stack
214//not understand
215//https://mp.weixin.qq.com/s/kEQ00_WLqDTG6tbsjQ2Xjw
216//Runtime: 48 ms, faster than 96.87% of C++ online submissions for Jump Game V.
217//Memory Usage: 15.1 MB, less than 77.56% of C++ online submissions for Jump Game V.
218//time: O(N), space: O(N)
219class Solution {
220public:
221 void print_stack(stack<int>& stk){
222 int* end = &stk.top() + 1;
223 int* begin = end - stk.size();
224 vector<int> stack_contents(begin, end);
225 for(int& e : stack_contents){
226 cout << e << " ";
227 }
228 cout << endl;
229 };
230
231 int maxJumps(vector<int>& arr, int d) {
232 int n = arr.size();
233
234 vector<int> dp(n+1, 1);
235 //monotonic stack, bottom element is the highest
236 stack<int> stk, stk2;
237
238 //use to clear "stk"
239 arr.push_back(INT_MAX);
240
241 for(int i = 0; i <= n; ++i){
242 // cout << "i: " << i << endl;
243 //while we can jump from i to some previous index
244 while(!stk.empty() && arr[stk.top()] < arr[i]){
245 //stk.top() is current lowest element in "stk"
246 //"stk"'s bottom element is the highest
247 int pre_h = arr[stk.top()];
248 // cout << "stk: " << endl;
249 // print_stack(stk);
250 while(!stk.empty() && arr[stk.top()] == pre_h){
251 int j = stk.top(); stk.pop();
252 if(i - j <= d){
253 //the index in "stk" are all visited
254 //jump from i to j
255 dp[i] = max(dp[i], dp[j]+1);
256 // cout << "dp[" << i << "], jump to " << j << ": " << dp[j]+1 << endl;
257 }
258 stk2.push(j);
259 }
260 // cout << "stk2: " << endl;
261 // print_stack(stk2);
262 while(!stk2.empty()){
263 int j = stk2.top(); stk2.pop();
264 if(!stk.empty() && j - stk.top() <= d){
265 //j's height is smaller than all element in "stk"
266 //jump from stk.top() to j
267 dp[stk.top()] = max(dp[stk.top()], dp[j]+1);
268 // cout << "dp[" << stk.top() << "], jump to " << j << ": " << dp[j]+1 << endl;
269 }
270 }
271 }
272 stk.push(i);
273 }
274
275 return *max_element(dp.begin(), dp.begin()+n);
276 }
277};Cost
Complexity
Time
O(Nd), space: O(N)
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.