Surprisingly Simple O(n) Solution


  • 0
    G

    This problem can be really tricky. We can either solve it with a backtracking and memoization solution, with dynamic programming (which will both result in an O(n^2) worst case scenario) or with a simple DP solution. Simple in terms of: it is simple to code ;)

    We do the following:

    1. Initialize the current position to 0 and store the maximum position you can reach from the first field.
    2. In every field, check if you can reach a "higher" field than the current highest.
    3. If the current position i exceeds your currently stored position, increase your position with the maximum reach possible at this moment.
    4. Increase the stepcounter and check if we are done.

    Since it is guaranteed to always find a solution to the problem, we don't need to apply any other checks. You should carefully discuss this with your interviewer though.

    public int jump(int[] nums) {
            if (nums == null || nums.length <= 1) {
                return 0;
            }
            
            int reach = nums[0];
            int steps = 0;
            int pos = 0;
            
            for (int i = 1; i < nums.length; i++) {
                if (i > pos) {
                    pos = reach;
                    steps++;
                    if (pos >= nums.length - 1) {
                        return steps;
                    }
                }
                
                reach = Math.max(reach, nums[i] + i);
            }
            
            return steps;
        }
    

  • 0

    Can you explain what pos stands for here?


  • 0
    G

    Sure :) pos means position and it stores the maximum position that you can currently reach. It get's updated whenever you can reach a greater position.


  • 0

    @georghennerbichler Thanks! It's clear to me now.


  • 0
    G

    Great @adam47, glad I could help.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.