Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Time complexity:O(n)
- //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
- //steps reamining to reach max_reach=arr[0],our current jump is at 0th index,now after traversing every index,we will reduce
- //steps_remaining and update max_reach.
- //when steps_reamining==0 then you have reached the maximum position you can reach from the last jump,so increase minimum_jumps.
- //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
- //cureent index element is 0,so return -1
- #define lli int
- class Solution {
- public:
- int jump(vector<int>& arr) {
- int n=arr.size();
- int max_reach=arr[0];
- int steps_remaining=arr[0];
- int minimum_jumps=1;
- if(n==1) return 0;
- else if(arr[0]==0) return -1;
- else{
- for(int i=1;i<n;i++){
- if(i==n-1) return minimum_jumps;
- max_reach=max(max_reach,i+arr[i]);
- steps_remaining--;
- if(steps_remaining==0){
- minimum_jumps++;
- if(i==max_reach) return -1;
- steps_remaining=max_reach-i;
- }
- }
- }
- return minimum_jumps;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement