O(n) solution with detailed explanation


  • 0
    T

    TL;DR

    Think of a ball game where there are N players in your team. All players have a fixed position on the ground. Each player has different "range" to throw the ball. Player 0 can throw the ball to any player in his range, than the player chosen by him will throw the ball to the next player in his range and so on. The objective is to throw the ball beyond a certain fixed target (say 1000 yards from player 0)

    If you are player 0, what will be your logic to throw the ball ? (all subsequent players have to just apply your logic)

    The logic is to throw the ball to the player who can throw it closest to the target.

    Long explanation

    The intuitive brute-force approach to this problem is to calculate all possible jump sequences and then check which is the shortest one.

    For example for an array : [2,1,1,2,1,1]

    You will always start at position 0. From position 0 you now have two options. So you can basically draw a tree like this
    2
    /
    1 1

    which then will expand into

           2
          / \
        1     1
        /       \
       1        2
      /          /\
     2         1 1 
     /\
    1 1 
    

    If you observe this tree you will realize that we are traversing the same tree at multiple nodes thus resulting into redundant computation. Hence we can do lot better than this Depth First Approach.

    But out of curiosity what is the complexity of this brute force algorithm ?

    If the array is of size M, then the first item can at max be of size M (otherwise we have a O(constant) solution). The second time can be of at max M-1 and third item can be of at max M-2 and so on.

    Since we are interested only in Asymptotic complexity we can assume that all the child nodes will have size of M-1 for node 0. The grand children of node 0 will all have M-2 nodes and so on.

    This gives us complexity of MM-1M-2 ...... O(M!). (I don't think this is 100% accurate a much tighter bound can be found).

    Efficient Solution

    The intuition for efficient solution is the following.

    Once you have a starting number, the children node that you can look at are fixed.
    For [2,1,1,2,1,1] the starting position is always 0 which has value of 2 and it gives you two children 1 & 1 at position 1 and 2 respectively.

    Now you have to select the best possible candidate from these children which means you need to look at each one of them. (when you need to look at each one of them implies that our algorithm is at least O(N))

    Now how do we determine which child is best possible candidate for hop ? In our brute-force we actually went down the path and checked but can there be a better way to get that idea WITHOUT going down the tree ?

    One possibility is to select the "largest" child but does it work ?

    For an array :
    [4,5,0,0,4,1,1,1,1]

    The node zero has 4 children out of which 5 is the largest but if you calculate you will see that 4 is a better next jump point.

    Why is 4 better than 5? Because it takes you the closest to the target.

    Aha!

    Now it is very simple. Imagine that each node has a "range of jump" select the node that has the "longest range" defined as "taking you farthest from the parent node". Read the TL;DR sports example to understand this better.

    Once you get this point coding the solution is very trivial.

    '''
    class Solution {

    public int jump(int[] nums) {
        int end = nums.length; 
        int runner = 0; 
        if(nums.length==0 || nums.length==1) return 0; 
        int hop = 1; 
        while(range(runner,nums)<end-1){
            int r = range(runner,nums); 
            int max = Integer.MIN_VALUE; 
            int nextIndex = -1; 
            for(int i=runner+1;i<=r;i++){
                int diff = range(i,nums) - r; 
                if(diff>max){
                    max = diff; 
                    nextIndex = i; 
                }
            }
            
            runner = nextIndex; hop++;
            
        }
        
        return hop; 
        
    }
    
    private int range(int runner, int[] nums){
        if(runner>=nums.length) return Integer.MAX_VALUE; 
        
        return runner+nums[runner]; 
    }
    

    }
    '''


Log in to reply
 

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