LeetCode Jump Game: Greedy vs DP vs BFS

Overview

I analyze three methods (DP, BFS, Greedy) to tackle the LeetCode problem Jump Game, both time and space complexity are given too. Greedy runs in linear time

LeetCode Jump Game Problem

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.

Solutins: DP, BFS, Greedy

(1) DP: let f(i) denote if it true to reach position i, then we have f(i) = OR ‘f(j) && (A[j] + j >= i)’ for j = 0, … i – 1.  The time complexity is O(N^2) and space complexity is O(N) because you need an array of size n to hold the dp values.

(2) BFS:for each position i, set all the positions reachable from i as true. The time complexity of this is O(N * max(A)) = O(N^2) since we max(A) will be bounded by N actually.

(3) Greedy: use a variable to keep the current maximum reachable distance from zero position, linear scan the given array, and update the maximum reachable distance by comparing with A[i] + i, once the maximum reachable distance is larger than the length of the array, return true, after linear scanning, the maximum reachable distance is not larger than the length, we return false.

The following is the C++ source code accepted by LeetCode OJ to pass this Jump Game problem:

bool canJump(int A[], int n) {
    if (n <= 1) return true;
    int maxReachable = 0;
    int currPos = 0;
    while (currPos <= maxReachable && maxReachable < n - 1) {
        maxReachable = max(maxReachable, currPos + A[currPos++]);
    }
    return maxReachable >= n - 1;
}

Summary

Three methods (DP, BFS, Greedy) are discussed to tackle the LeetCode problem Jump Game, both time and space complexity are given too. Greedy runs in linear time

Written on May 16, 2013