Min Jumps Array (Top-Down Approach)

Question

Problem Statement : Given an array of non-negative integers, A, of length N, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Return the minimum number of jumps required to reach the last index.

Input: A = [2,3,1,1,4]

Output: 2

Explanation: The shortest way to reach index 4 is Index 0 -> Index 1 -> Index 4 that requires 2 jumps.

Below is the solution :

// M is the function that gives the required minimum jumps
// nums is the vector containing jumps (here I have used nums in place of array A).
// start denoting the starting index
// map(m) STL for memoization

int M(vector<int> &nums, int start, unordered_map<int, int>&m){

    if(start == nums.size()-1){return 0;} // if we reach the last index then return 0.

    if(start >= nums.size()){return INT_MAX;} // if we reach beyond last index then return some big value that can't be the answer.

    if(nums[start] == 0){return INT_MAX;} // if in mid we get jump value = 0 then we cannot expect the min jump so again return some big value.

    if(m[start] != 0){return m[start];} // if we already stored the value (calculated the answer) then return stored value 

    int ans = INT_MAX; // assuming initially answer to be some big value. 

    for(int i=1; i<=nums[start]; i++){ // jump can be made from 1 to maximum value of that element in array i.e. nums[start]

        ans = min(ans, 1+M(nums, start+i, m)); // answer is minimum of previously calculated answer and 1 + allowed path (start + i).

        m[start] = ans; // storing it in map.
    }

    return m[start]; // returning the stored value
}

I am getting TLE for the above solution. I am not able to figure out time complexity of the solution after memoization. Can someone help me in estimating the time complexity of the above solution.

Instead of creating an arbitrary large value, why not return the absolute maximum? https://stackoverflow.com/questions/1855459/maximum-value-of-int — JohnFilleau, Mar 22 '20 at 15:40
Why using a `map` and not a `vector` ? Note that max value is less than `N`. — Damien, Mar 22 '20 at 15:55
@John yeah one can use absolute max also but using some large value like 1e7 in this case also gives the correct answer. — utkarsh bajpai, Mar 22 '20 at 16:09
@utkarsh sure, if it works it works. My suggestion was more of a best practice so the code is "self documenting". It's easier to read your intent if you set the number to max, rather than some arbitrary big number. — JohnFilleau, Mar 22 '20 at 16:12
@Damien why not use map. In this case for searching it takes constant time. — utkarsh bajpai, Mar 22 '20 at 16:19
What I mean is the the max result is less then N. So you could use N as max. But INT_MAX is good of course. — Damien, Mar 22 '20 at 16:20
@Damien sorry for the wrong interpretation. Yeah you are right. — utkarsh bajpai, Mar 22 '20 at 16:22
Vector would be faster that unordered_map, no hashing, same code here. — Damien, Mar 22 '20 at 16:22
If d is the average jump, your complexity is `O(d N)`. But two implementations with same `O(.)` can have quite different time performances. — Damien, Mar 22 '20 at 16:28
@Damien replacing the map with vector still gives TLE. Can you please be descriptive on how did you found out the time complexity in this case. — utkarsh bajpai, Mar 22 '20 at 16:31

score 1 · Answer 1 · answered Mar 22 '20 at 15:45

1

I have an approach to solve this question in O(nlogn) complexity (maybe there would be better possible approaches)

Use a lazy segment tree to store minimum value for l,r index.

On every index set dp[i] = query(i,i) and then update(i+1,dp[i]+i,dp[i]+1)

If you are confused, do comment. I will provide implementation as well.

I know there might be better possible solutions as this problem seems classical, but this is what came to my mind of the first go.

answered Mar 22 '20 at 15:45

Ayush Mahajan

639
1
5
14

Thanks for another approach but I am looking for time complexity of my designed approach as I am not able to figure it out. – utkarsh bajpai Mar 22 '20 at 16:13

Oleg Yablokov · Answer 2 · 2020-03-22T17:23:07.923

Not sure about your question, but I think I've got O(N) solution:

int M(const vector<int> &nums)
{
    int n_jumps = 0;
    int cur_pos = 0;
    int prev_pos = 0;
    int next_jump = 0;
    int max_value = 0;
    int value;
    int i;
    while (cur_pos + nums[cur_pos] < nums.size() - 1)
    {
        next_jump = 0;
        max_value = 0;
        i = cur_pos > 0 ? prev_pos + nums[prev_pos] + 1 : 1;
        for (; i <= cur_pos + nums[cur_pos]; ++i)
        {
            value = i + nums[i];
            if (value >= nums.size() - 1) return n_jumps + 2;
            if (max_value < value)
            {
                max_value = value;
                next_jump = i - cur_pos;
            }
        }
        prev_pos = cur_pos;
        cur_pos += next_jump;
        ++n_jumps;
    }
    return n_jumps + 1;
}

Every time we choose how much to jump by maximizing the distance we can cover in this and the next turn. The last jump can be just the maximum allowed jump, i.e. the value of the element we are at.

Note that when we have jumped to the next element, we don't have to check the elements that were accessible from the previous position (which gives us O(N)).

It can be proved that this algorithm finds the minimum number of jumps using mathematical induction.

thanks for the suggesting another approach but I want to find out time complexity of my approach. — utkarsh bajpai, Mar 22 '20 at 18:00

Min Jumps Array (Top-Down Approach)

2 Answers2