Start learning free

LESSON 330 OF 347 · GREEDY

Jump Game in C#: Minimum Jumps with a Greedy Scan in O(n)

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 8
    Ctrl + Enter to check

    C# · GREEDY

    Jump Game in C#, explained

    Problem overview

    You are given an int[] nums of non-negative numbers. You start at index 0, and nums[i] is the farthest you can jump forward from index i: any jump of length 1 up to nums[i] is allowed. Jump(int[] nums) 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. One jump is not enough, because index 0 reaches at most index 2.

    Approach: jump only when you must

    Trying every sequence of jumps is exponential, and a table of the fewest jumps to every index takes O(n²) time. A greedy scan does it in one pass by thinking in layers. All the indexes reachable with 1 jump form the first layer, those that need exactly 2 jumps form the second, and so on. The answer is the number of the layer holding the last index.

    The scan keeps two numbers:

    • curMax is the farthest index reachable with the jumps counted so far.
    • nextMax is the farthest index reachable with one more jump, from any index visited so far.

    Moving through the array, you stay within the current jump as long as i <= curMax. The first time i is beyond curMax, one more jump is unavoidable. It is best taken from whichever earlier index reached the farthest, which is exactly what nextMax remembers, so curMax becomes nextMax and the jump count goes up by one.

    Take [2, 3, 1, 1, 4]. The first jump is counted at the start, so result = 1 and curMax = nextMax = 2. At index 1, nextMax becomes 1 + 3 = 4. At index 2, nothing changes (2 + 1 = 3). At index 3, curMax is 2, which is less than 3, so a second jump is counted and curMax becomes 4. Index 4 is within reach, and the loop ends with result = 2.

    Why is waiting until the last moment correct? Any index inside the current layer can be the launch point of the next jump, and a launch point that reaches farther can never be worse than one that reaches less. Delaying the decision until i passes curMax lets the scan see every candidate in the layer first and pick the best, instead of committing early to an index that turns out to be a poor one.

    Step by step

    1. Handle the trivial case. With one index (or none), you are already on the last one, so return 0.
    2. Start the jump count at 1. With at least two indexes, one jump is needed, so it is counted straight away.
    3. Set curMax to nums[0], the farthest index that first jump can reach.
    4. Set nextMax to nums[0] too. It will grow as you see more indexes.
    5. Loop from index 1 to the end, visiting each index once.
    6. Check whether index i is out of reach. If curMax < i, increment result and set curMax to nextMax.
    7. Update nextMax with Math.Max(nextMax, i + nums[i]). This runs for every index, including the one that just triggered a jump, because that index may start the following jump.
    8. Return result.

    The solution in C#

    class Solution {
    public int Jump(int[] nums) {
        if (nums.Length <= 1) {
            return 0;
        }
        int result = 1;
        int curMax = nums[0];
        int nextMax = nums[0];
        for (int i = 1; i < nums.Length; ++i) {
            if (curMax < i) {
                ++result;
                curMax = nextMax;
            }
            nextMax = Math.Max(nextMax, i + nums[i]);
        }
        return result;
    }
}

    C# details:

    • Length, not Length(). The size of an array is a property, so it takes no parentheses.
    • ++result versus result++. As a standalone statement they do the same thing. The prefix form is just the style this solution uses.
    • i + nums[i] is an index-sized value. It is the farthest index reachable from i, and it can be larger than the last index. That is fine, since it is only compared, never used to index the array.

    Complexity

    Time: O(n). One pass, with constant work per index.

    Space: O(1). Four integers: result, curMax, nextMax and the loop index.

    Edge cases and common mistakes

    • A single element. [0] returns 0, because you are already at the last index.
    • One big first jump. For [5, 1, 1, 1, 1, 1] the first jump covers everything, curMax is never less than i, and the answer is 1.
    • Steps of one. [1, 1, 1, 1] needs 3 jumps, one per move.
    • Counting a jump per index. The jump count only goes up when the current reach runs out, not whenever a better nextMax is found.
    • Skipping the nextMax update on the trigger index. If it were in an else branch, the index that forced the jump would not contribute its own reach.
    • Unreachable arrays. The method assumes the last index can be reached. For something like [1, 0, 0] it still returns a number, which does not mean the end is reachable. When reachability is not guaranteed, test it separately.

    Testing

    • [2, 3, 1, 1, 4] gives 2.
    • [0] gives 0.
    • [1, 1, 1, 1] gives 3.
    • [5, 1, 1, 1, 1, 1] gives 1.
    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