(very simple) DP using HashMap + Get rid of TLE using a simple array + beat 84%


  • 0
    C

    Address the problem of TLE.

    public class Solution {
        public boolean canCross(int[] stones) {
            Map<Integer, Set<Integer>> map = new HashMap<>();
            int[] maxMap = new int[stones.length];
            // store accumulative max step to prune
            map.put(0, new HashSet<>());
            map.get(0).add(0);
            int max = 0;
            for (int i = 1; i < stones.length; i++) {
                Set<Integer> set = new HashSet<>();
                // how many ways can frog get to stone i
                // hashset stores the steps took
                for (int j = i - 1; j >= 0; j--) {
                    int step = stones[i] - stones[j];
                    if (step > maxMap[j] + 1) // essential, or else will TLE
                        break;
                    if (map.get(j).contains(step - 1) || map.get(j).contains(step) || map.get(j).contains(step + 1)) {
                        set.add(step);
                        max = Math.max(max, step);
                    }
                }
                map.put(i, set);
                maxMap[i] = max;
            }
            return map.get(stones.length - 1).size() > 0;
        }
    }
    

Log in to reply
 

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