Java Solution Using HashMap


  • 3
    R

    For each stone, we write down a set of jump distances taken from previous stones to reach this stone (for example, if the stones were 3, 5, 7, then for stone 7 we write down 7 - 3 = 4 and 7 - 5 = 2, assuming they're both valid moves). From the distance set we can find a set of "imaginary" stones reachable from this stone, so all we have to do is to figure out (through hash table) which of those target stones actually exists, and propagate the distance to their distance sets.

    Finally, we check if the last stone was reachable by checking if its distance set wasn't empty.

    public class Solution {
        public boolean canCross(int[] stones) {
            final int l = stones != null ? stones.length : 0;
            if (l < 1 || stones[0] != 0) return false;
            final Map<Integer, Set<Integer>> map = new HashMap<>();
            for (int s : stones) map.put(s, new HashSet<Integer>());
            for (int s : stones) {
                Set<Integer> jSet = map.get(s);
                // Initial condition
                if (s == 0) {
                    jSet.add(0);
                    if (map.containsKey(1)) map.get(1).add(1);
                    continue;
                }
                // For other stones
                for (int j : jSet) {
                    int jj = j - 1;
                    int ss = s + jj;
                    // Previous jump - 1
                    if (ss != s && map.containsKey(ss)) map.get(ss).add(jj);
                    // Previous jump
                    jj++; ss++;
                    if (ss != s && map.containsKey(ss)) map.get(ss).add(jj);
                    // Previous jump + 1
                    jj++; ss++;
                    if (ss != s && map.containsKey(ss)) map.get(ss).add(jj);
                }
            }
            return !map.get(stones[l - 1]).isEmpty();
        }
    }
    

  • 0
    Z
    This post is deleted!

  • 0
    L

    @zehua2 I think it isn't O(n).


  • 0
    S

    I think this solution is not O(N) but your iteration and propagate idea is clever.

    I like it.

    Just one tip: we just want to find one valid path so it could plug in a "cut branch" inside your outer loop like:

    if (!map.get(stones[l - 1]).isEmpty()){
         break;
    }
    

    once reach last stone, no need to start again. :)


  • 0
    Z

    @liu971 You are right. It seems that it still is O(3^n). Since each stone could triple size of set.


  • 1
    I

    @Rabby250 I think no need to use Set, List is OK, if k are added in descending order.

        if (stones[1] != 1) return false;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 2; i < stones.length; ++i) map.put(stones[i], new ArrayList<>());
        map.put(stones[1], Arrays.asList(1));
        for (int i = 1; i < stones.length; ++i) {
            List<Integer> units = map.get(stones[i]);
            int lastUnit = Integer.MAX_VALUE;
            for (int unit : units) {
                if (unit + 1 < lastUnit) { // units are in descending order
                    List<Integer> list = map.get(stones[i] + unit + 1);
                    if (list != null) list.add(unit + 1);
                }
                if (unit < lastUnit) {
                    List<Integer> list = map.get(stones[i] + unit);
                    if (list != null) list.add(unit);
                }
                if (unit - 1 > 0) {
                    List<Integer> list = map.get(stones[i] + unit - 1);
                    if (list != null) list.add(unit - 1);
                }
                lastUnit = unit - 1;
            }
        }
        return map.get(stones[stones.length - 1]).size() > 0;
    
    

  • 0
    I

    @zehua2 This is not O(3^n), it can at least bounded to O(n^2). At each stone i, the units or distances stored can be bounded to i-1 (if from every stone j < i, can have a jump to i).


Log in to reply
 

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