package com.leetcode;

import java.util.HashMap;

public class JumpGame {

    //https://leetcode.com/problems/jump-game/
    /**
    Input: nums = [2,3,1,1,4]
    Output: true
    Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
    **/

    class Solution {
        public boolean canJump(int[] nums) {
            int reach=0,n=nums.length;
            for(int i=0;i=n-1)
                    return true;
                if(!(reach>i))////means cannot go ahead than current reach < i or reach == i
                    return false;
            }
            return true;
        }
    }


    // Recursion with Memo
    class SolutionTLE {

        boolean canReach;//just need one path

        public boolean canJump(int[] nums) {
            HashMap memo = new HashMap(); // to store if at index if can be reached.
            int n = nums.length;
            return backtrack(0,n-1,nums,memo);

        }

        public boolean backtrack(int start, int target , int [] nums, HashMap memo){
            if(memo.containsKey(start)) return memo.get(start);
            if(canReach) return false;//terminate if any one solution is found

            if(start == target){
                memo.put(start,true);
                canReach = true;
                return true;
            }

            int jump = nums[start];

            boolean found = false;
            for(int i = 1 ; i