Hi All, so I have a solution run in 36 ms and beats 80 %. While i don't understand why it behaves faster than I thought. Because theoretically this algorithm should behave O(n^n) in worst case but it doesn't. I even tried the large input case mentioned in this thread. But it still run in 0ms.

Anyway, so my algorithm is to find whether there is a stone can reach the `end`

. To answer this question, iterate all stones before `end`

, from `end-1`

th to the `0`

th and for every stone `i`

, we then keep asking whether there is a stone can reach to `i`

.

To answer whether there is a stone can reach `i`

, we need to first calculate what is step required to reach `i`

and find whether we have such a stone. For example:

`[0,1,3,5,6,8,12,17]`

If we want to reach 17, the `end`

, let's first check `end-1`

which is 12, since distance between 12 to 17 is 5, we then ask "do we have a stone can reach 12 with either 4, 5 or 6 steps. Then we find stone 8 (4 steps) and 6 (6 steps) can do that. We then keep asking same question to 8 and 6. For 8, the distance to 12 is 4, so we ask "do we have a stone can reach 8 with either 3, 4, or 5 steps", for 6, the distance to 12 is 6, so we ask "do we have a stone can reach 6 with either 5,6 or 7 steps?" and so on until we reach to the first one.

Since the `end`

will ask every stones before it so it loops (n-1) times, and for each `DoWeHave[i]`

question, the time taken should be `1 * 2 * 3 * ... i`

so the run time complexity (worst case) should be`O(n^n)`

.

My plan was to make the logic correct first, then do some memorization optimization when I got TLE but I passed all the test cased even with the large one and I just confused why. Did I calculate the time complexity wrong? or this question was intended to use a `O(n^n)`

algorithm. Any hint will be appreciated. Below is my code:

```
class Solution {
public:
bool doWeHave(vector<int>& stones, unordered_map<int,int>& dict, int end, int step1, int step2, int step3) {
if (end == 0) {
if (step1 == 0 || step2 == 0 || step3 == 0) {
return true;
}
else {
return false;
}
}
else if (end == 1) {
if (step1 == 1 || step2 == 1 || step3 == 1) {
return true;
}
else {
return false;
}
}
else {
int current = stones[end];
if (step1 > 0 && dict.find(current - step1) != dict.end()) {
int index = dict[current-step1], dist = stones[end] - stones[index];
if (doWeHave(stones, dict, index, dist-1, dist, dist+1)) {
return true;
}
}
if (step2 > 0 && dict.find(current - step2) != dict.end()) {
int index = dict[current-step2], dist = stones[end] - stones[index];
if (doWeHave(stones, dict, index, dist-1, dist, dist+1)) {
return true;
}
}
if (step3 > 0 && dict.find(current - step3) != dict.end()) {
int index = dict[current-step3],dist = stones[end] - stones[index];
if (doWeHave(stones, dict, index, dist-1, dist, dist+1)) {
return true;
}
}
return false;
}
}
bool canCross(vector<int>& stones) {
int len = stones.size();
if (len == 1) {
return true;
}
else {
unordered_map<int,int> dict;
for (int i = 0; i < len; i++) {
dict[stones[i]] = i;
}
int dest = stones[len-1];
for (int i = len-2; i >= 0; i--) {
int current = stones[i];
int step1 = dest-current-1, step2 = dest-current, step3 = dest-current+1;
if (doWeHave(stones, dict, i, step1, step2, step3)) {
return true;
}
}
return false;
}
}
};
```