educative.io

Educative

Java O(N) time O(1) space solution

class ArrayJump {

  public int countMinJumps(int[] jumps) {
    int n = jumps.length;
    int res = 0;
    int left = 0, right = 0;
    while( right < n - 1){
      int farthest = 0;
      for(int i = left; i <= right; i++){
        farthest = Math.max(i + jumps[i], farthest);
      }
      left = right + 1;
      right = farthest;
      res += 1;
    }
    return res;
  }

  public static void main(String[] args) {
    ArrayJump aj = new ArrayJump();
    int[] jumps = {2, 1, 1, 1, 4};
    System.out.println(aj.countMinJumps(jumps));
    jumps = new int[]{1, 1, 3, 6, 9, 3, 0, 1, 3};
    System.out.println(aj.countMinJumps(jumps));
  }
}

Type your question above this line.

Course: https://www.educative.io/collection/5668639101419520/5633779737559040
Lesson: https://www.educative.io/collection/page/5668639101419520/5633779737559040/5685057352105984

Hey @Annabelle_Sun!
Your solution is correct. We appreciate learners who deep dive and explore new solutions to problems. We hope educative has inspired you to further your learning😊

1 Like