Gaurav Kumar Jan 25, 2023 2023-01-25T23:55:00+05:30
Jan 26, 2023 2023-01-26T00:18:23+05:30 1 min
PROBLEM DESCRIPTION
You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position. Return true if you can reach the last index, or false otherwise.
leetcode
SOLUTION
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
public boolean canJump(int[] nums) {
int n = nums.length;
//to track which cells have been visited
boolean[] visited = new boolean[n];
//mark first cell as visited
visited[0] = true;
//loop through the cells
for(int i=0; i<n; i++){
//if the current cell has not been visited, it's impossible to move forward
if(visited[i] == false) return false;
//get the current max jumps possible
int x = nums[i];
//mark the next "x" cells true because it's possible to visit them from the current cell
for(int j=i+1; j<n && x > 0; j++, x--){
visited[j] = true;
}
}
//if the last cell was visited, return true
return visited[n-1] == true;
}
}
|
GREEDY SOLUTION
NeetCode YouTube
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public boolean canJump(int[] nums) {
//final destination is index n-1
int goal = nums.length-1;
//check from right to left
//keep checking if the current goal/position is reachable
//if it's reachabled, update the goal to current index (as it's possible to go from current index to previous goal)
for(int i=goal-1; i>=0; i--){
int current = nums[i];
//if -> current index + max jumps from current index >= current goal
//we can update the goal to current position
if(current + i >= goal){
goal = i;
}
}
//if we have reached 0th index, there was definitely a path from 0th to (n-1)th index
return goal == 0;
}
}
|
