45. Jump Game II

"""
main idea: use right_most to record longest distance within current choice range.  since our start point is confirmed, we need to create a end point to mark that the moment is time to move to next step end at furtherest distance. 
Note here we do not need to go to the end because (1) it is guaranteened we will reached to the end (2) if our end is n-1, the moment we reached end, steps will + 1, which is no necesary 
"""
class Solution:
    def jump(self, A: List[int]) -> int:
        """ tc O(N) sc O(1)
        """
        n = len(A)
        right_most,steps,end = 0,0,0
        for i in range(n-1): # for cases [0]  
            right_most = max(right_most, A[i]+i)
            if i == end :
                steps += 1
                end = right_most
        return steps