Minimum Jumps To Reach End
Python
Hard
6 views
Problem Description
For each testcase you get array where a[i] is max jump length from i. Compute minimum jumps to reach last index, else -1.
Input Format
First integer t. For each: n then n integers.
Output Format
t lines min jumps.
Sample Test Case
Input:
2
5
2 3 1 1 4
5
3 2 1 0 4
Constraints
Sum of n over all testcases
Official Solution
import sys
p=sys.stdin.read().strip().split()
if not p:
sys.exit(0)
it=iter(p)
t=int(next(it))
out=[]
for _ in range(t):
n=int(next(it))
a=[int(next(it)) for _ in range(n)]
if n<=1:
out.append('0')
continue
if a[0]==0:
out.append('-1')
continue
jumps=1
maxReach=a[0]
step=a[0]
ok=True
for i in range(1,n):
if i==n-1:
break
if i+a[i]>maxReach:
maxReach=i+a[i]
step-=1
if step==0:
jumps+=1
if i>=maxReach:
ok=False
break
step=maxReach-i
out.append(str(jumps if ok else -1))
sys.stdout.write('\
'.join(out))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!