Advertisement
imashutosh51

Minimum steps to reach end of array

Jul 23rd, 2022
35
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.31 KB | None | 0 0
  1. //Time complexity:O(n)
  2. //Initially the max_index we can reach is arr[0] so max_reach=arr[0] so we have to traverse till max_reach of 0th index so
  3. //steps reamining to reach max_reach=arr[0],our current jump is at 0th index,now after traversing every index,we will reduce
  4. //steps_remaining and update max_reach.
  5. //when steps_reamining==0 then you have reached the maximum position you can reach from the last jump,so increase minimum_jumps.
  6. //if i>=max_reach,it can only happen when 2 1 0,whenmax_reach and ith index equals and max_reach can be updated ahead because
  7. //cureent index element is 0,so return -1
  8. #define lli int
  9. class Solution {
  10. public:
  11.     int jump(vector<int>& arr) {
  12.         int n=arr.size();
  13.         int max_reach=arr[0];
  14.         int steps_remaining=arr[0];
  15.         int minimum_jumps=1;
  16.         if(n==1) return 0;
  17.         else if(arr[0]==0) return -1;
  18.         else{
  19.             for(int i=1;i<n;i++){
  20.                 if(i==n-1) return minimum_jumps;
  21.                 max_reach=max(max_reach,i+arr[i]);
  22.                 steps_remaining--;
  23.                 if(steps_remaining==0){
  24.                     minimum_jumps++;
  25.                     if(i==max_reach) return -1;
  26.                     steps_remaining=max_reach-i;
  27.                 }
  28.             }
  29.         }
  30.         return minimum_jumps;
  31.     }
  32. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement