Jump Game
- 2 min read
- Greedy
- LC-Medium
- Dynamic Programming
3 years ago
Greedy Solution
There are a lot of overlapping subproblems, so it makes sense to use dynamic programming here. However, it still TLEs on Leetcode.
| Time | Space | Explanation |
|---|---|---|
O(n) | O(1) |
- Work backwards and shift the goal
- For the input [2, 3, 1, 1, 4]
- Look at the element closest to our goal of 4, it is 1.
- It means if we're at the element 1 at index 3, we can reach our goal
- So we shift the goal to 1 at index 3
- It's our new goal- if we reach this, we can reach our eventual goal.
- Keep doing the same thing backwards.
- At the end of the for loop, our goal is either 0 or not 0. If it's 0, it means we can reach the end from the starting index. If it's not, we cannot.
def canJump(self, nums: List[int]) -> bool:
goal = len(nums) - 1
for i in range(len(nums) - 2, -1, -1):
if i + nums[i] >= goal:
goal = i
return goal == 0
Dynamic Programming Solution (TLE)
There are a lot of overlapping subproblems if we do the typical logic of looking at the first index, looking at it's value, and travelling to all the index we can travel from it and checking them individuallyw, so it makes sense to use dynamic programming here. However, it still TLEs on Leetcode.
| Time | Space | Explanation |
|---|---|---|
O(n^2) | O(n) |
def canJump(self, nums: List[int]) -> bool:
memo = {}
def dfs(i):
if i in memo:
return memo[i]
if i == len(nums) - 1:
return True
if nums[i] == 0:
return False
can_jump = False
for jump in range(1, nums[i] + 1):
can_jump = can_jump or dfs(i + jump)
memo[i] = can_jump
return can_jump
return dfs(0)