java dp solution, only use array, 15ms


  • 0
    S

    Record the minimal and maximal possible next step at each stone, and move forward.

    
    public class Solution {
        public boolean canCross(int[] stones) {
            if (stones.length <= 1){
                return true;
            }
            int n = stones.length;
            int[] minNextStep = new int[n];
            int[] maxNextStep = new int[n];
            Arrays.fill(minNextStep, Integer.MAX_VALUE);
            minNextStep[0] = 1;
            maxNextStep[0] = 1;
            for (int i = 0; i < n; i++){
                if (minNextStep[i] > maxNextStep[i]){
                    return false;
                }
                int j = i + 1;
                for (int k = Math.max(1, minNextStep[i]); k <= maxNextStep[i]; k++){
                    if (j >= n){
                        break;
                    }
                    if (stones[i] + k < stones[j]){
                        continue;
                    } else if (stones[i] + k == stones[j]){
                        minNextStep[j] = Math.min(minNextStep[j], k - 1);
                        maxNextStep[j] = Math.max(maxNextStep[j], k + 1);
                        j++;
                    } else{
                        j++;
                    }
                }
            }
            return true;
        }
    }
    

  • 1
    Z

    This method fails in this case: [0,1,3,6,10,13,15,16,19,21,25], which should return false, while this method returns true. Because only storing min and max step might miss some information. For example, at ith stone, we might only has possible previous step length 1-3 and 5-6, while this method simply combine them as 1-6. @1337c0d3r


  • 0
    This post is deleted!

  • 0

    @zehua2 said in java dp solution, only use array, 15ms:

    This method fails in this case: [0,1,3,6,10,13,15,16,19,21,25], which should return false, while this method returns true. Because only storing min and max step might miss some information. For example, at ith stone, we might only has possible previous step length 1-3 and 5-6, while this method simply combine them as 1-6.

    Nice catch, there are so many problem with not enough test cases


  • 0

    @zehua2 Thanks! I have added your test case.


Log in to reply
 

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