CODEWITHSUNDEEP
c++dynamic-programmingmemoizationrecursive-backtrackingtopdown
utkarsh bajpai
utkarsh bajpai

Reputation: 33

Min Jumps Array (Top-Down Approach)

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.

Upvotes: 0

Views: 507

Answers (2)

Oleg Yablokov
Oleg Yablokov

Reputation: 835

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.

Upvotes: 1

Ayush Mahajan
Ayush Mahajan

Reputation: 649

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.

Upvotes: 1

Related Questions