A good way into this one is to ask: what do we need to remember so we never redo work blindly? For 55. Jump Game, the solution in this repository is mainly a graph traversal 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: graph traversal, dynamic programming, backtracking, greedy.
The notes already sitting in the source point us in the right direction:
- TLE
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are canJump, visited, canJumpFromPos.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- The queue gives the solution a level-by-level or frontier-style traversal.
- 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(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//TLE
02class Solution {
03public:
04 bool canJump(vector<int>& nums) {
05 int N = nums.size();
06 vector<bool> dp(N, false);
07
08 dp[N-1] = true;
09 for(int i = N-1; i >= 0; i--){
10 if(nums[i] >= 1){
11 //can reach to one of dp[i+j] which is true
12 for(int j = 1; j <= nums[i] && i+j < N; j++){
13 if(dp[i+j]){
14 dp[i] = true;
15 break;
16 }
17 }
18 }
19 }
20
21
22 for(int i = 0; i < N; i++){
23 if(nums[i] >= 1){
24 //can reach to one of dp[i+j] which is true
25 for(int j = 1; j <= nums[i] && i-j >= 0; j++){
26 if(dp[i-j]){
27 dp[i] = true;
28 break;
29 }
30 }
31 }
32 }
33
34 return dp[0];
35 }
36};
37
38//TLE
39//74 / 75 test cases passed.
40//Graph
41class Solution {
42public:
43 bool canJump(vector<int>& nums) {
44 map<int, vector<int>> graph;
45 int n = nums.size();
46
47 for(int i = 0; i < n; i++){
48 // for(int j = max(0, i-nums[i]); j <= min(n-1, i+nums[i]); j++){
49 for(int j = i; j <= min(n-1, i+nums[i]); j++){
50 graph[i].push_back(j);
51 }
52 }
53
54 queue<int> q;
55 q.push(0);
56
57 vector<bool> visited(n, false);
58 visited[0] = true;
59
60 while(!q.empty()){
61 int cur = q.front(); q.pop();
62
63 for(int next : graph[cur]){
64 if(!visited[next]){
65 visited[next] = true;
66 q.push(next);
67 }
68 }
69 }
70
71 return visited[n-1];
72 }
73};
74
75//Approach 1: Backtracking
76//TLE
77//time: O(2^n), space: O(n)
78class Solution {
79public:
80 bool canJumpFromPos(vector<int>& nums, int pos){
81 int N = nums.size();
82 if(pos == N-1) return true;
83
84 int furthestJump = min(pos+nums[pos], N-1);
85 // for(int nextPos = pos+1; nextPos <= furthestJump; nextPos++){
86 for(int nextPos = furthestJump; nextPos > pos; nextPos--){
87 if(canJumpFromPos(nums, nextPos)){
88 return true;
89 }
90 }
91
92 return false;
93 };
94
95 bool canJump(vector<int>& nums) {
96 return canJumpFromPos(nums, 0);
97 }
98};
99
100//Approach 2: Dynamic Programming Top-down(backtracking with memorization)
101//TLE
102//time: O(n^2), space: O(n)
103
104class Solution {
105public:
106 enum Index {
107 GOOD, BAD, UNKNOWN
108 };
109
110 vector<Index> memo;
111
112 bool canJumpFromPos(vector<int>& nums, int pos){
113 int N = nums.size();
114 if(memo[pos] != Index::UNKNOWN){
115 return memo[pos] == GOOD ? true : false;
116 }
117
118 int furthestJump = min(pos+nums[pos], N-1);
119 // for(int nextPos = pos+1; nextPos <= furthestJump; nextPos++){
120 for(int nextPos = furthestJump; nextPos > pos; nextPos--){
121 if(canJumpFromPos(nums, nextPos)){
122 memo[pos] = Index::GOOD;
123 return true;
124 }
125 }
126
127 memo[pos] = Index::BAD;
128 return false;
129 };
130
131 bool canJump(vector<int>& nums) {
132 int N = nums.size();
133 memo = vector<Index>(N);
134 for(int i = 0; i < N-1; i++){
135 memo[i] = Index::UNKNOWN;
136 }
137 memo[N-1] = Index::GOOD;
138
139 return canJumpFromPos(nums, 0);
140 }
141};
142
143//Approach 3: Dynamic Programming Bottom-up
144//Runtime: 516 ms, faster than 14.01% of C++ online submissions for Jump Game.
145//Memory Usage: 9.1 MB, less than 100.00% of C++ online submissions for Jump Game.
146//time: O(n^2), space: O(n)
147
148class Solution {
149public:
150 enum Index {
151 GOOD, BAD, UNKNOWN
152 };
153
154 vector<Index> memo;
155
156 bool canJump(vector<int>& nums) {
157 int N = nums.size();
158 memo = vector<Index>(N);
159 for(int i = 0; i < N-1; i++){
160 memo[i] = Index::UNKNOWN;
161 }
162 memo[N-1] = Index::GOOD;
163
164 for(int pos = N-2; pos >= 0; pos--){
165 int furthestJump = min(pos+nums[pos], N-1);
166 for(int nextPos = furthestJump; nextPos > pos; nextPos--){
167 if(memo[nextPos] == Index::GOOD){
168 memo[pos] = Index::GOOD;
169 break;
170 }
171 }
172 }
173
174 return memo[0] == Index::GOOD;
175 }
176};
177
178//Approach 4: Greedy
179//Runtime: 12 ms, faster than 73.33% of C++ online submissions for Jump Game.
180//Memory Usage: 9.3 MB, less than 100.00% of C++ online submissions for Jump Game.
181//time: O(n), space: O(1)
182
183class Solution {
184public:
185 bool canJump(vector<int>& nums) {
186 int N = nums.size();
187 int lastGood = N-1;
188
189 for(int i = N-2; i >= 0; i--){
190 if(i + nums[i] >= lastGood){
191 lastGood = i;
192 }
193 }
194
195 return lastGood == 0;
196 }
197};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.