aman_naughty's blog

Minimum Jump Game DP Using BFS
By aman_naughty, history, 5 years ago, In English

Problem Link — problem

code —

code

Why is this giving TLE? I am only visiting each array index only once.I am considering this as a graph problem where the neighbors of a node are all the indices reachable from that index.Then BFS will clearly result in the shortest path to reach index n-1.Can someone help me please..

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You are visiting each index only once, but for every index you do a loop. If the there are N elements your worstcase in O(N^2), for example if all the values are greater tha N.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks mate . Is there any workaround I can modify BFS solution for this problem or is DP the only approach to solve this problem and BFS is wrong??

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can use the same trick that I used for my solution, but consider that for the nature of the problem you will update the values in the same order as I do, from left to right so I dont think that BFS is a good idea.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution is much simpler and works: The distance of the first value is 0, after that you will update the distance of every value once. I iterate over all values keeping the next value that I have not visited yet, when I update the next values I don't iterate over the value for which I have already found the minimum distance.

int n=A.size();
vector<int> dist(n,-1);
dist[0]=0;
int li=1; //next value to update
for(int i=0;i<n;i++){
    if(dist[i]==-1) return -1; //I cant'arrive here 
    for(;li<=i+A[i] && li<n;li++) dist[li]=dist[i]+1; //updating only new values
}
return dist[n-1];
→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Instead of running loop inside, you can keep track from where you need to start.

Modified Code
→ Reply