Created
May 18, 2023 08:21
-
-
Save ritik-agrawal/b707681eb34d35c7e150da7d0c1d28cd to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public boolean canJump(int[] nums) { | |
var len = nums.length; | |
//cornor | |
if (len == 1){ | |
return true; | |
} | |
//cornor | |
var canReach = new boolean[len-1]; | |
var target = len - 1; | |
for (int cur = (len-2); cur >= 0; cur--){ | |
var maxJump = nums[cur]; | |
var required = target - cur; | |
var jump = (maxJump > required) ? required : maxJump; | |
while(jump > 0){ | |
var next = cur+jump; | |
if (next == target){ | |
canReach[cur] = true; | |
break; | |
} else if (canReach[next]){ | |
canReach[cur] = true; | |
break; | |
} | |
jump--; | |
} | |
} | |
return canReach[0]; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Leet code
Given with an integer array with each index having the max jump that can be made. Need to find if the last index can be reached from the first index.
Achievement
The above code solution is done by me using the Dynamic programming technique. The provided code took 144ms and beats 30% of the total solutions submitted.
Yet Better Approach
The above question can be solved using the greedy algorithm. The below code demonstrates the same and beats 73% of the total solutions submitted by taking a runtime of 2ms