LeetCode: Jump Game I && II

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

Solution

At first glance, the problem can be solved with recursion or BFS. However, both solutions got the TLE error. Apparently, the intended solution should have less time complexity.

Key point: use maxCover to indicate the maximum index that current index can reach. Update the value of maxCover correspondingly.

	//O(n) solution
	public boolean canJump(int[] A) {
	if(A==null) return false;
	if(A.length == 0) return true;
	int maxCover =0;
	for(int i=0; i<=maxCover&&i<A.length; i++){//i<=maxCover is essential
	maxCover = Math.max(maxCover, A[i]+i);
	if(maxCover >= A.length-1) return true;
	}
	return false;
	}
	//BFS
	public boolean canJump(int[] A) {
	if(A==null) return false;
	if(A.length == 0) return true;
	Queue<Integer> que = new LinkedList<Integer>();
	HashSet<Integer> set = new HashSet<Integer>();
	que.add(0);
	set.add(0);
	while(!que.isEmpty()){
	int id = que.poll();
	int maxJump = A[id];
	if(id+maxJump>=A.length-1) return true;
	else{
	for(int i=1; i<=maxJump; i++){
	if(!set.contains(id+i)){
	que.add(id+i);
	set.add(id+i);
	}
	}
	}
	}
	return false;
	}
	//Recursion DFS
	public boolean canJump(int[] A) {
	if(A==null) return false;
	if(A.length == 0) return true;
	return dfs(A, 0);
	}
	public boolean dfs(int[] A, int id) {
	boolean res = false;
	if(id>=A.length) return false;
	int maxJump = A[id];
	if(id+maxJump>=A.length-1) return true;
	else{
	for(int i=1; i<=maxJump; i++){
	res |= dfs(A, id+i);
	}
	}
	return res;
	}

view raw gistfile1.java hosted with ❤ by GitHub

For Jump Game II. Tried BFS first, got TLE error. Then figured out the right answer based on the solution of Jump Game I. Key point: use a tempoary variable tempCover to get the largest A[i]+i  from all the indices within current maxCover.

	public int jump(int[] A) {
	int minStep = 0;
	if(A==null) return minStep;
	if(A.length == 0 ||A.length == 1) return minStep;
	int maxCover =0;
	int tempCover =0;
	for(int i=0; i<=maxCover&&i<A.length; i++){
	if(tempCover<maxCover)
	tempCover = maxCover;
	if(tempCover < A[i]+i){
	tempCover = A[i]+i;
	}
	if(tempCover >= A.length-1) return ++minStep;
	if(i==maxCover){
	maxCover = tempCover;
	minStep++;
	}
	}
	return minStep;
	}
	//BFS TLE
	public int jump(int[] A) {
	int minStep=0;
	if(A==null) return minStep;
	if(A.length == 0) return minStep;
	Queue<Integer> que = new LinkedList<Integer>();
	HashSet<Integer> set = new HashSet<Integer>();
	que.add(0);
	que.add(-1);
	set.add(0);
	while(!que.isEmpty()){
	int id = que.poll();
	if(id == -1){
	que.add(-1);
	minStep++;
	continue;
	}
	int maxJump = A[id];
	if(id+maxJump>=A.length-1) return minStep;
	else{
	for(int i=1; i<=maxJump; i++){
	if(!set.contains(id+i)){
	que.add(id+i);
	set.add(id+i);
	}
	}
	}
	}
	return minStep;
	}

view raw gistfile1.java hosted with ❤ by GitHub