O(n^2) solution with detailed comments, using BFS


  • 0
    Z
    class Solution {
    public:
        using SET = unordered_set<int>;
        
        void updateJump(unordered_map<int, SET> &s, int unit, int k) {
            if (k > 0) {
                const int next_unit = unit + k;
                auto it = s.find(next_unit);
                if (it != s.end()) {
                    it->second.insert(k);
                }
            }
        }
        
        bool canCross(vector<int>& stones) {
            if (stones.empty()) {
                return true;
            }
            // Stores all possible last-jumps for stone unit at a specific position.
            unordered_map<int, SET> stones_to_jump = {{0, {0}}};
            for (const int unit : stones) {
                if (unit > 0) {
                    // Pre insert all stone unit into the map, this can 
                    // facilitate a little.
                    stones_to_jump[unit] = {};
                }
            }
            // This points to all possible last-jumps for the last stone unit.
            auto final_iter = stones_to_jump.find(stones.back());
            for (const int unit : stones) {
                auto it = stones_to_jump.find(unit);
                if (it->second.empty()) {
                    // If empty, then means no possible jumps to stone at <unit>
                    continue;
                }
                for (const int jump : it->second) {
                    // Update all other jumps starting from <unit>.
                    updateJump(stones_to_jump, unit, jump - 1);
                    updateJump(stones_to_jump, unit, jump);
                    updateJump(stones_to_jump, unit, jump + 1);
                }
                if (!final_iter->second.empty()) {
                    // This means we already find one solution, directly return.
                    return true;
                }
            }
            return !final_iter->second.empty();
        }
    };
    

Log in to reply
 

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