*****MISSING TEST CASE!!!***** Accepted code fails on a case.


  • 0
    S

    My solution. Accepted but fails on [0,1,3,6,10,15,16,21].

    public class Solution {
        public boolean canCross(int[] stones) {
            int n = stones.length;
            
            Map<Integer, List<Integer>> indexToJumps = new HashMap<>();
            
            List<Integer> firstJump = Arrays.asList(0);
            indexToJumps.put(0, firstJump);
            
            for (int i = 1; i < n; i++) {
                
                if (indexToJumps.size() == 0) {
                    return false;
                }
                
                List<Integer> nextJump = new ArrayList<>();
                List<Integer> removeIndexes = new ArrayList<>();
                for (int index: indexToJumps.keySet()) {
                    boolean canReach = false;
                    
                    int distance = stones[i] - stones[index];
                    for (int jump: indexToJumps.get(index)) {
                        if (Math.abs(distance - jump) <= 1) {
                            nextJump.add(distance);
                            canReach = true;
                            break;
                        }
                    }
                    
                    if (!canReach) {
                        removeIndexes.add(index);
                    }
                }
                indexToJumps.put(i, nextJump);
                
                for (int index: removeIndexes) {
                    indexToJumps.remove(index);
                }
            }
            
            return !(indexToJumps.get(n-1).size() == 0);
        }
    }
    

  • 0
    S

    Revised solution. Accepted and passes [0,1,3,6,10,15,16,21].

    public class Solution {
        public boolean canCross(int[] stones) {
            int n = stones.length;
            
            Map<Integer, List<Integer>> indexToJumps = new HashMap<>();
            
            List<Integer> firstJump = Arrays.asList(0);
            indexToJumps.put(0, firstJump);
            
            for (int i = 1; i < n; i++) {
                
                if (indexToJumps.size() == 0) {
                    return false;
                }
                
                List<Integer> nextJump = new ArrayList<>();
                List<Integer> removeIndexes = new ArrayList<>();
                for (int index: indexToJumps.keySet()) {
                    boolean canReach = false;
                    
                    int distance = stones[i] - stones[index];
                    for (int jump: indexToJumps.get(index)) {
                        if (jump-1 > distance) canReach = true;
                        if (Math.abs(distance - jump) <= 1) {
                            nextJump.add(distance);
                            canReach = true;
                            break;
                        }
                    }
                    
                    if (!canReach) {
                        removeIndexes.add(index);
                    }
                }
                indexToJumps.put(i, nextJump);
                
                for (int index: removeIndexes) {
                    indexToJumps.remove(index);
                }
            }
            
            return !(indexToJumps.get(n-1).size() == 0);
        }
    }
    

  • 0

    @stellalai Thanks so much. I have just added your test case.


Log in to reply
 

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