# C++ O(n^2) Time, And Space Friendly Solution.

• The major advantage of this solution is, it checks at each step if there is a stone at the reachable positions. For example, if at 2 it can reach 5, but there is no stone at 5th unit, then this record is not recorded.

``````class Solution {
unordered_map<int, unordered_set<int>> arrivials;
public:
bool canCross(vector<int>& stones) {
if (stones.size() < 2 || stones[1] != 1)
return false;
for (int i = 2; i < stones.size(); ++i)
arrivials[stones[i]] =  unordered_set<int>();
arrivials[1].insert(1);
for (int i = 1; i < stones.size(); ++i)
{
int pos = stones[i];
for(auto step : arrivials[pos])
{
if (pos + step + 1 >= stones.back() && pos + step - 1 <= stones.back())
return true;
auto iter = arrivials.find(pos + step + 1);
if (iter != arrivials.end())
iter->second.insert(step + 1);
iter = arrivials.find(pos + step);
if (iter != arrivials.end())
iter->second.insert(step);
iter = arrivials.find(pos + step - 1);
if (step > 1 && iter != arrivials.end())
iter->second.insert(step - 1);
}
}
return false;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.