Difficulty: Medium; Asked in: Google, Amazon, Walmart, Adobe, eBay
Key takeaway: This is an excellent problem to learn time and space complexity optimization in a dynamic programming context. The efficient single loop solution is intuitive and worth exploring.
Given an array of positive integers, write a program to reach the last index using the minimum number of jumps.
Important note: Before moving on to the solutions, we recommend trying this problem on paper for at least 15 or 30 minutes. Enjoy problem-solving!
Input: A[] = [1, 3, 5, 8, 10, 2, 6, 7, 6, 8, 9], Output: 3
Explanation: 1-> 3 -> 8 -> 9 or 1-> 3 -> 10 -> 9
Input: A[] = [2, 3, 1, 1, 4], Output: 2
Explanation: 2->3->4. The minimum number of jumps to reach the last index is 2. We jump 1 step from index 0 to 1, then 3 steps to the last index.
There can be many possible ways to reach the end, but we need to find a way using the minimum number of jumps. So, one basic solution would be to calculate the jump count of all possible ways to reach the end and return the minimum among those values. The critical question would be: How do we explore all possible ways to reach the end? Let's think!
When there is a requirement to explore all possible ways, we can think to apply the idea of recursion, i.e., the solution of the larger problem using the solution of smaller subproblems.
Here is an intuition for a recursive solution: We start from the 0th index and recursively call for all the indices reachable from the 0th index. In other words, the minimum number of jumps to reach the last index can be calculated using the minimum number of jumps needed to reach the last index from the index reachable from the 0th index. (Think!)
Recursive structure
For all i reachable from start i.e. i = 1 to A[start]:
minJumps (A[], start, end) = 1 + min (minJumps (A[], start + i, end ))
Base case: This is a case of single or zero element array where no jump is required to reach the end. i.e. if (start >= end), we return 0.
int minJump(int A[], int start, int end)
{
if (start >= end)
return 0;
int minJumpCount = INT_MAX;
for (int i = 1; i <= A[start] && i < end; i++)
{
int jumpCount = 1 + minJump(A, start + i, end);
if (jumpCount < minJumpCount)
minJumpCount = jumpCount;
}
return minJumpCount;
}
def minJump(A, start, end):
if start >= end:
return 0
minJumpCount = sys.maxsize
for i in range(1, A[start] + 1):
if i < end:
jumpCount = 1 + minJump(A, start + i, end)
if jumpCount < minJumpCount:
minJumpCount = jumpCount
return minJumpCount
We can think from a simple perspective to calculate all possible ways to reach the end. There are two possibilities for each index from 1 to n - 1: either we take a jump from that index or do not take a jump. So the total number of possible ways is 2^(n-1), which is exponential time. (Think!)
We can also analyze it by writing a recurrence relation.
So finding the min jump is an exponential function of n, which is inefficient. In retrospect, this is not surprising because we are exploring all possibilities. If we create a recursion tree for the above approach, we can notice overlapping subproblems.
For example, if we observe the following picture, the sub-problem minJump(2, 5) is coming two times, minJump(3, 5) is coming three times, and so on.
Since we have identified this as a dynamic programming problem, we can efficiently solve it using a bottom-up approach. We aim to calculate the solution of smaller sub-problems iteratively and store their results in a table.
int minJump(int A[], int n)
{
int jump[n];
jump[0] = 0;
for (int i = 1; i < n; i = i + 1)
jump[i] = INT_MAX;
for (int i = 1; i < n; i = i + 1)
{
for (int j = 0; j < i; j = i + 1)
{
if (i <= j + A[j] && jump[j] != INT_MAX)
jump[i] = min(jump[i], jump[j] + 1);
}
}
return jump[n - 1];
}
def minJump(A, n):
jump = [0] + [sys.maxsize] * (n - 1)
for i in range(1, n):
for j in range(i):
if i <= j + A[j] and jump[j] != sys.maxsize:
jump[i] = min(jump[i], jump[j] + 1)
return jump[n -1]
Time complexity = Time complexity of initializing jump[] array + Time complexity of nested loops to store values in jump[] array = O(n) + O(n^2) = O(n^2). Similarly, space complexity = O(n) for using n size jump[] array.
The above dynamic programming solution is much more efficient than a brute force solution. But critical questions are: can we further improve the time complexity, space complexity, or both? Can we try to remove inner loop of the above solution? Can we track the value of minimum jump using some variable?
Here is an improvement insight: From any jump point i, we can reach any index from (i + 1) to (i + A[i]), and there will be some value between range A [i + 1] to A [i + A[i]], which can provide the farthest reach from that range. So we define lower and upper end of the current jump point and calculate the farthest reach in that range. Whenever we reach the upper endpoint of a range, we update the upper end with the value of farthest reach and increment jump count. We continue this process till the value of farthest reachable index is greater than n - 1.
Let's define four variables to simulate the above process:
int minJump(int A[], int n)
{
if (n <= 1)
return 0;
int jump = 0, currStart = 0;
int currEnd = 0, currMaxReach = -1;
while (currStart < n - 1)
{
currMaxReach = max(currMaxReach, currStart + A[currStart]);
if (currMaxReach >= n - 1)
{
jump = jump + 1;
break;
}
if (currStart == currEnd)
{
jump = jump + 1;
currEnd = currMaxReach;
}
currStart = currStart + 1;
}
return jump;
}
def minJump(A, n):
if n <= 1:
return 0
jump = 0
currStart = 0
currEnd = 0
currMaxReach = -1
while currStart < n - 1:
currMaxReach = max(currMaxReach, currStart + A[currStart])
if currMaxReach >= n - 1:
jump = jump + 1
break
if currStart == currEnd:
jump = jump + 1
currEnd = currMaxReach
currStart = currStart + 1
return jump
In this approach, we define three variables: currMaxReach, stepsCount, and jump. We set both the jump and stepsCount variables to the value of the first index of the array. Here, currMaxReach is the maximum we can reach from that index, which is the index plus the value of the index (the jump value). So, we keep updating it in each iteration (starting from 1 to n - 2), so that whenever we move forward, the variable currMaxReach stores the max reach by using currMaxReach = max(currMaxReach, A[start] + start).
Also, at each iteration, we reduce our stepsCount variable by 1. As we move forward, we consume 1 step each time. So, whenever we run out of steps, it means we need to take one jump. So, we increase the jump variable and update the stepsCount variable to the value (currMaxReach - start), which is the maximum reach possible from the current index. This means that we can take those steps, and then we need to jump again.
So, we return jump + 1 as our output in this solution since we only jump after running out of steps. Also, we need to note that: we moved only till the second last element and not the last element since at the last step, we do not need to consume one more step as we are already there and no need to jump more.
int minJump(int A[], int n)
{
if (n <= 1)
return 0;
int currMaxReach = A[0];
int stepsCount = A[0];
int jump = 0;
for (int start = 1; start < n - 1; start = start + 1)
{
currMaxReach = max(currMaxReach, start + A[start]);
stepsCount = stepsCount - 1;
if (stepsCount == 0)
{
jump = jump + 1;
stepsCount = currMaxReach - start;
}
}
return jump + 1;
}
def minJump(A, n):
if n <= 1:
return 0
currMaxReach = A[0]
stepsCount = A[0]
jump = 0
for start in range(1, n - 1):
currMaxReach = max(currMaxReach, start + A[start])
stepsCount = stepsCount - 1
if stepsCount == 0:
jump = jump + 1
stepsCount = currMaxReach - start
return jump + 1
In both the single loop solution, we are doing constant operations at each iteration. So time complexity = O(n). We are using constant extra space, so space complexity = O(1)
If you have any queries/doubts/feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!