Problem source: Jump Game
1. Understand the problem
The problem requires to determine if we could jump to the last index in the array using the values of the elements within it.
Let say if we are at index i with the value of 3, we can visit all position from i till i + 3.
2. First thought
We can apply a brute force method to solve this.
We can have an array keeping track of whether it is possible to visit an index i.
For each element e with value nums[e], we can run a loop to mark all element from e to e + nums[e] to be visitable
Here is a simple code in Java:
// input is int[] nums
int visitable = new boolean[nums.length];
for (int i = 0; i < nums.length; i++) {
int element = nums[i];
for (int index = element; index <= element + nums[element]; index ++) {
visitable[index] = true;
}
}
return visitable[nums.length -1];
This may yeild a time limit exceed since it will require O(n^2) runtims.
3. Solution
What could be improved is that we do not need nested for loop for this. We can use greedy method.
One observation we can claim is that: if we could visit index x, we can visit all indices y with y < x.
This can be proven using contradiction. I will leave this to you.
So here is the solution to this problem, which runs in just O(n)
class Solution {
public boolean canJump(int[] nums) {
/**
The steps count from that index to index + step.
We can maintain a queue to keep track of which index can be visited, also keep track of a set of index already visit to avoid repetition.
Runtime: O(n ^ 2) with n can be 10^5
Need to improve this:
- do not care about the value at the last index
- care whether the other cell could reach the last one.
- update the value of the elements to the farthest cell they can reach
If we can visit cell x, can we claim that we can always visit cell y < x?
*/
int max = 0;
int idx = 0;
while (idx < nums.length && idx <= max) {
max = Math.max(max, idx + nums[idx]);
if (max >= nums.length - 1) {
return true;
}
idx ++;
}
return false;
}
}
Top comments (0)