Start learning free

LESSON 345 OF 347 · GRAPHS

Jump Game in C#: Minimum Jumps in O(n) with Dynamic Programming

Practice O(n) Read the full explanation

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.

Your goal is to reach the last index in the minimum number of jumps.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
             Jump 1 step from index 0 to 1, then 3 steps to the last index.
STEP 1 OF 6
    Ctrl + Enter to check

    C# · GRAPHS

    Jump Game in C#, explained

    Problem overview

    Jump(nums) receives an array of non-negative integers. You start at index 0, and nums[i] is the maximum length of a jump from index i: from there you may land on any index from i + 1 to i + nums[i]. The method returns the minimum number of jumps needed to reach the last index.

    For [2, 3, 1, 1, 4] the answer is 2. Jump one step from index 0 to index 1, then three steps from index 1 to the last index, at index 4. One jump is not enough, because index 0 reaches only indices 1 and 2.

    Approach: fill in the cheapest cost of each cell, left to right

    Let dp[k] be the minimum number of jumps needed to reach index k. Then dp[0] is 0, and the answer is dp[nums.Length - 1]. A direct way to fill the table is to let every index i improve all the cells it can reach, which is quadratic in the worst case. This lesson notices something that makes it linear.

    The values of dp never decrease from left to right: reaching a farther cell never takes fewer jumps than reaching a nearer one. That means the first index i that can reach a cell j also gives the best answer for it, namely dp[i] + 1. Every later index that can reach j has a dp value that is at least as large, so it can't improve anything.

    So each cell needs to be written once, and a single pointer j is enough to remember where the unreached cells begin. Cells are reached in order from left to right, so everything before j is done and everything from j on is still unvisited.

    Here is the run on [2, 3, 1, 1, 4], showing j and the array after each value of i:

    i=0 j=3 dp=0,1,1,0,0
i=1 j=5 dp=0,1,1,2,2
i=2 j=5 dp=0,1,1,2,2
i=3 j=5 dp=0,1,1,2,2
i=4 j=5 dp=0,1,1,2,2

    Index 0 reaches cells 1 and 2 with one jump each. Index 1 then reaches cells 3 and 4, so both get dp[1] + 1 = 2. Once j reaches 5, which is the array length, nothing is left to fill.

    Step by step

    1. Create dp as an int[] with nums.Length entries. A new int array is filled with zeros, which is right for dp[0], and every other cell is overwritten the first time it is reached.
    2. Declare j and set it to 1. It marks the first cell no jump has reached yet. Cell 0 is the start.
    3. Loop over every index i of nums.
    4. Add a while loop that continues while j is reachable from i (j <= nums[i] + i) and still inside the array (j < nums.Length). Because j only moves forward, the inner loop runs at most n times in total across all values of i.
    5. Fill the cell and advance. Cell j is reached for the first time with one jump from cell i, so assign dp[i] + 1 to it. Writing the index as j++ does the assignment with the old j and then moves j on, all in one statement.
    6. Return dp[nums.Length - 1].

    The solution in C#

    class Solution {
    public int Jump(int[] nums) {
        int[] dp = new int[nums.Length];
        int j = 1;
        for (int i = 0; i < nums.Length; ++i) {
            while (j <= nums[i] + i && j < nums.Length) {
                dp[j++] = dp[i] + 1;
            }
        }
        return dp[nums.Length - 1];
    }
}

    C# details worth knowing

    • dp[j++] = dp[i] + 1; uses the value of j before the increment as the index. With j equal to 1, it writes dp[1] and leaves j at 2. ++j would do the opposite, increment first, and write the wrong cell.
    • The two conditions in the while are joined by &&, which stops at the first false one. The order here is safe either way, because neither condition reads the array at j.
    • Arrays have a fixed length, so new int[nums.Length] allocates all the cells at once, each starting at 0.

    Complexity

    Time is O(n). The outer loop runs n times, and the inner while advances j on every iteration without ever moving it back, so it runs at most n times over the whole call. Extra space is O(n) for the dp array.

    Edge cases and common mistakes

    • A single element. With [1] the loop never fills anything, and the method returns dp[0], which is 0. You are already at the last index.
    • Forgetting the bound j < nums.Length. A large jump value would send j past the end and throw IndexOutOfRangeException.
    • Starting j at 0. That would overwrite dp[0] with 1 and shift every answer by one.
    • Counting the start. The answer counts jumps, not cells, which is why dp[0] is 0.
    • Unreachable endings. The solution assumes the last index can be reached. If a zero blocks the way, the cells behind it keep wrong or zero values, so the result can't be trusted.

    Testing

    [2, 3, 1, 1, 4]  ->  2
[1, 1, 1, 1]     ->  3
[3, 2, 1]        ->  1
[1]              ->  0
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free