CodingGyan

Jump Game

medium Data Structures and Algorithms

Problem

You stand at index 0. a[i] is the maximum jump length from index i. Print true if you can reach the last index, else false.

Constraints

  • 1 <= n <= 10^5
  • 0 <= a[i] <= 10^5

Examples

Input

5
2 3 1 1 4

Output

true

Solutions

Best approachTime O(n)Space O(1)

A greedy idea: we only need to know the farthest reachable index. If we ever stand at an index beyond it, the way is blocked.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Process an array.
 * Input   : n, then n integers.
 * Output  : true or false.
 * Approach: Track the farthest reach.
 * Time    : O(n)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static boolean solve(int[] a) {
        // Step 1: farthest = the farthest index we can reach so far.
        int farthest = 0;

        for (int i = 0; i < a.length; i++) {
            // Step 2: If index i is beyond the farthest reachable index, we are stuck.
            if (i > farthest) {
                return false;
            }

            // Step 3: From i we can reach i + a[i]. Keep the maximum.
            farthest = Math.max(farthest, i + a[i]);
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = scanner.nextInt();
        }
        System.out.println(solve(a));
    }
}
Hints (1)
  1. What does it mean if i is larger than farthest?

Try these next