My 2ms Java solution, O(n) complexity and O(1) space, easy to understand


  • 5
    V

    The way I think of it is that finding the furthest point that we can jump to. Initialize nums[0] to be the furthest position that we can jump to, then loop from nums[1] to that furthest position to find if we can jump further than that using each element. Once we find a value that helps us jump further than the current furthest position, set that value to be the new furthest position. When our furthest position is bigger than the last position of the array, exits the loop and returns true. If the loop exits before that, it means that we cannot reach the last position, return false.

        public class Solution {
        public boolean canJump(int[] nums) {
            if (nums == null) return false;
            if (nums.length == 1) return true;
            
            int furthest_pos = nums[0];
            for (int i = 1; i <= furthest_pos; ++i){
                if (furthest_pos >= nums.length-1){
                    return true;
                }
                int cur_furthest_pos = i + nums[i];
                if (cur_furthest_pos > furthest_pos){
                    furthest_pos = cur_furthest_pos;
                }
            }
            
            return false;
        }
    }

Log in to reply
 

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