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


  • 0
    F

    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;
        }
    };
    

Log in to reply
 

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