Skip to content

55. Jump Game 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
 public:
  bool canJump(vector<int>& nums) {
    int i = 0;

    for (int reach = 0; i < nums.size() && i <= reach; ++i)
      reach = max(reach, i + nums[i]);

    return i == nums.size();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
  public boolean canJump(int[] nums) {
    int i = 0;

    for (int reach = 0; i < nums.length && i <= reach; ++i)
      reach = Math.max(reach, i + nums[i]);

    return i == nums.length;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
  def canJump(self, nums: List[int]) -> bool:
    i = 0
    reach = 0

    while i < len(nums) and i <= reach:
      reach = max(reach, i + nums[i])
      i += 1

    return i == len(nums)