Jump Game


  • 1

    Click here to see the full article post


  • 0
    J

    I would like to know how to reach the time complexity for the first approach (backtracking). Since there is no memorization, the same position can be visited multiple times. I would think the time complexity is O(2^N) because T(N) = T(N-1) + T(N-2) + ... + T(1) & T(N-1) = T(N-2) + T(N-3) + ... + T(1). => T(N) = 2T(N-1) => O(2^N).


  • 0
    A

    @jied333 You are correct. My reasoning would only have been valid if the jump could happen both to the left and to the right. I will amend the article to reflect the correct complexity analysis.


  • 0
    P

    This is a brilliant article. Not only does it contain the solution but also the thought process of how to break it down and conclude one thing after the other


  • 0

    @piy9 Thanks, glad that you like it! Thanks @andreifirst for writing this brilliant article.


  • 0
    P

    In the first solution

    // Old
    for (int nextPosition = position + 1; position <= furthestJump; position++)
    // New
    for (int nextPosition = furthestJump; nextPosition > position; position--)

    The for loop is slightly incorrect. It should be nextposition++ and not position++


  • 1

    @piy9 Thanks for pointing that out! Just fixed. FYI @andreifirst .


  • 0
    G

    The code, that checks cutom test cases, throws exceptions when null or [] is specified as an input for the custom test case. Shouldn't such things always be checked?


  • 0

    approach #1 recursion is not constant space


  • 0
    H

    The space complexity of Approach #3 (Dynamic Programming Bottom-up) [Time limit exceeded] is O(n), not O(2n) = O(n), because there is no recursion.


  • 0
    F

    I approached it using different but simple, linear algorithm, It got accepted and was placed in beats 88% of results in terms of execution time. Let me explain,

    The task is to just verify if reaching last index of possible/impossible, exact paths are not needed, so let's rephrase the problem - when is it impossible to reach last index?

    The answer is very simple - when you get stuck on element with value 0 and it is impossible to take a step back and jump over this element (you could say that value 0 is sort of a trap). If value is >0 then you can always proceed further until you get to the last index.

    So algorithm is following:

    1. start at the end of array-1 (we don't care what is the value of very last element) - pointer 'i':
      1.1) if current element (nums[i]) is zero , take another pointer 'j' and look to the left (initate at i-1) for element which allows you to jump over this trap (so element which has value > (i-j))
      1.1.1) if you can't find it and you reach beginning of array - return false as you can't avoid the trap
      1.1.2) if you found such element, set 'i' to j-1 (where j points to element you just found) and go back to step 1
      1.2) if current element (nums[i]) is not zero - decrease 'i' by 1 (move further to the left/start)

    This algorithm never scans the same element twice therefore it is linear and one pass (when in doubt see 1.1.2 - we skip the entire area that we just scanned in 1.1)
    There is one corner case which is easy to miss - first element being 0 - so you can check for it right in the beginning.


  • 0
    K

    These answers, while interesting, seem far more complex than it needs to be. This code works
    def check(i):
    j = min(i, 9)
    for k in range(i-j, i):
    if A[k] > i-k:
    return True
    return False

        for i, v in enumerate(A[:len(A)-1]):
            if v == 0 and not check(i):
                return False
        
        return True
    

    The idea is to check every 0 to see if it can be jumped over. That's all it takes.


  • 0
    W

    Thanks for the article!
    Learned a lot.


  • 0
    W

    I learned a lot from this problem and solution. Thank you !


  • 0
    S

    class Solution {
    public:
    bool canJump(vector<int>& A) {
    int max_jump = 0;
    for (int i =0; i < A.size(); ++i){
    if(max_jump >= i){
    max_jump = max(max_jump,A[i] + i);
    }
    }
    return (max_jump >= A.size() - 1);
    }
    };


  • 0
    D

    I came up with a linear solution that passed all the test and ran faster than 87% of all solutions and I would like to share it because I think it is very simple. The idea is to compute if the end of the array is reachable from the i-th element (tracing backward). Starting at any position in the array, the end is reachable if: jumping from the current element, one can reach the end or another position that can reach the end. The algorithm is as followed:

    1. Start with a pointer at the end of the array, and store the last index as the NeedToReach Index
    2. Tracing backward the entire array, if a position's index plus its value is >= NeedToReach, update NeedToReach as the current index
    3. Return if (NeedToReach==0)

  • 0
    J

    Learned a lot! Thank you so much for explaining this.


  • 0
    S

    I think the run time of approach#2 is O(n) and not O(n^2). Indeed, because of array memo, each element of the array nums is visited at most once.


  • 0
    S

    first thank you! it's been very helpful I have only one question, there is an option to wright the Approach #1 (Backtracking) [Stack Overflow] without any loop?


  • 0
    2

    So at first, I solved it using BFS (time limit exceeded), then I solved it using DFS (same), then I solved it using BFS coming from both ends. This time, the input that made my solution exceed the time allotted was [1,1,...,1,1]. This made me think of another solution which is fast enough, but a bit more complex. My observation was that only 0's result in arrays that have no solution, so I my approach was to only handle 0's.

    My approach is to start with index = 0

    • Iterate from i = index to n - 1 over all the numbers
    • Only if 0 is found at some index i, walk back looking for a number at j that takes me to an index beyond i.
    • now, look forward from i + i until the index that the number at j allows to jump to
    • recursively call self with nums and index = the valid index found at the previous step

    As for the complexity of this solution, I haven't analyzed it.


Log in to reply
 

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