8ms java solution with binary search


  • 0
        public boolean canCross(int[] stones) {
            if (stones.length <= 1) return true;
            if (stones[1] != 1) return false;
            return helper(stones, 1, 1);
        }
        
        private boolean helper(int[] stones, int num, int step) {
            if (num == stones.length - 1) return true;
            for (int i = -1; i <= 1; i++) {
                int next = bs(stones, num + 1, stones.length - 1, stones[num] + step + i);
                if (next != -1 && helper(stones, next, step + i)) return true;
            }
            return false;
        }
        
        private int bs(int[] stones, int i, int j, int target) {
            if (i > j) return -1;
            while (i <= j) {
                int mid = i + (j - i) / 2;
                if (stones[mid] == target) return mid;
                else if (stones[mid] < target) i = mid + 1;
                else j = mid - 1;
            }
            return -1;
        }
    

  • 0
    I

    How did you make it 8ms? I am getting " Time Limit Exceeded".


  • 0
    W

    @ibmtp380
    Because the test cases were simple and few when he submitted his solution.


Log in to reply
 

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