The trick here is to name the state correctly, then let the implementation follow. For 1306. Jump Game III, the solution in this repository is mainly a graph traversal solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. 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, two pointers, sliding window.
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 canReachRecursive, canReach.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- 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//Runtime: 44 ms, faster than 97.42% of C++ online submissions for Jump Game III.
02//Memory Usage: 12.7 MB, less than 100.00% of C++ online submissions for Jump Game III.
03
04class Solution {
05public:
06 enum Index{
07 GOOD, BAD, UNKNOWN
08 };
09
10 vector<Index> reach;
11 vector<bool> visited;
12
13 bool canReachRecursive(vector<int>& arr, int start) {
14 //avoid fall into a loop in the graph
15 if(visited[start]){
16 reach[start] = Index::BAD;
17 return reach[start];
18 }
19 visited[start] = true;
20
21 // cout << start << ": ";
22 // switch(reach[start]){
23 // case Index::GOOD:
24 // cout << "G ";
25 // break;
26 // case Index::BAD:
27 // cout << "B ";
28 // break;
29 // case Index::UNKNOWN:
30 // cout << "U ";
31 // }
32 // cout << endl;
33
34 if(reach[start] == Index::GOOD || reach[start] == Index::BAD){
35 return reach[start];
36 }
37
38 //jump right
39 if(start + arr[start] < arr.size()){
40 if(canReachRecursive(arr, start + arr[start]) == Index::GOOD){
41 reach[start] = Index::GOOD;
42 return reach[start];
43 }
44 }
45
46 //jump left
47 if(start - arr[start] >= 0){
48 if(canReachRecursive(arr, start - arr[start]) == Index::GOOD){
49 reach[start] = Index::GOOD;
50 return reach[start];
51 }
52 }
53
54 //cannot reach 0
55 reach[start] = Index::BAD;
56
57 // for(int i = 0; i < reach.size(); i++){
58 // cout << i << ": ";
59 // switch(reach[i]){
60 // case Index::GOOD:
61 // cout << "G ";
62 // break;
63 // case Index::BAD:
64 // cout << "B ";
65 // break;
66 // case Index::UNKNOWN:
67 // cout << "U ";
68 // }
69 // }
70 // cout << endl;
71
72 return reach[start];
73 }
74
75 bool canReach(vector<int>& arr, int start) {
76 int N = arr.size();
77
78 reach = vector<Index>(N, Index::UNKNOWN);
79 visited = vector<bool>(N, false);
80
81 for(int i = 0; i < N; i++){
82 if(arr[i] == 0)
83 reach[i] = Index::GOOD;
84 }
85
86 return canReachRecursive(arr, start) == Index::GOOD;
87 }
88};
89
90//Recursion
91//https://leetcode.com/problems/jump-game-iii/discuss/464083/C%2B%2BJava-Recursion
92//Runtime: 52 ms, faster than 77.17% of C++ online submissions for Jump Game III.
93//Memory Usage: 11.9 MB, less than 100.00% of C++ online submissions for Jump Game III.
94//time: O(n), space: O(n)
95class Solution {
96public:
97 set<int> visited;
98
99 bool canReach(vector<int>& arr, int start) {
100 if((start >= 0) && (start < arr.size()) && visited.insert(start).second){
101 return arr[start] == 0 || canReach(arr, start+arr[start]) || canReach(arr, start-arr[start]);
102 }
103 //not valid "start" or already visited
104 return false;
105 }
106};
107
108//queue BFS
109//https://leetcode.com/problems/jump-game-iii/discuss/463872/Simple-one-using-queue-and-visited-paths-JAVA
110//Runtime: 52 ms, faster than 77.17% of C++ online submissions for Jump Game III.
111//Memory Usage: 11.8 MB, less than 100.00% of C++ online submissions for Jump Game III.
112class Solution {
113public:
114 bool canReach(vector<int>& arr, int start) {
115 set<int> visited;
116 queue<int> q;
117
118 q.push(start);
119 while(!q.empty()){
120 int cur = q.front(); q.pop();
121 if(visited.find(cur) != visited.end()){
122 //ignore visited node
123 continue;
124 }
125 visited.insert(cur);
126
127 if(arr[cur] == 0){
128 return true;
129 }
130 if(cur + arr[cur] < arr.size()){
131 q.push(cur + arr[cur]);
132 }
133 if(cur - arr[cur] >= 0){
134 q.push(cur - arr[cur]);
135 }
136 }
137
138 return false;
139 }
140};
141
142//Recursion, without set and queue
143//https://leetcode.com/problems/jump-game-iii/discuss/465602/JavaC%2B%2BPython-1-Line-Recursion
144//Runtime: 52 ms, faster than 77.17% of C++ online submissions for Jump Game III.
145//Memory Usage: 11.3 MB, less than 100.00% of C++ online submissions for Jump Game III.
146class Solution {
147public:
148 bool canReach(vector<int>& arr, int start) {
149 if((start >= 0) && (start < arr.size()) && (arr[start] >= 0)){
150 //mark as visited
151 arr[start] *= -1;
152 return arr[start] == 0 || canReach(arr, start+arr[start]) || canReach(arr, start-arr[start]);
153 }
154
155 return false;
156 }
157};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.