Interview 150
Jump Game II
- Problem
- LC 45
- File
- interview150_LC45JumpGameII.java
- Path
- pkg5leetcode/interview150/interview150_LC45JumpGameII.java
- Package
- pkg5leetcode.interview150
- Command
- java pkg5leetcode/interview150/interview150_LC45JumpGameII.java
- Approach
- Greedy BFS layers; count jumps when reaching current layer end.
- Complexity
- Time O(n), Space O(1)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.interview150;2 3/*4 * Jump Game II | LC 455 * APPROACH: Greedy BFS layers; count jumps when reaching current layer end.6 * COMPLEXITY: Time O(n), Space O(1)7 */8public class interview150_LC45JumpGameII {9 static int jump(int[] nums) {10 int jumps = 0, end = 0, farthest = 0;11 for (int i = 0; i < nums.length - 1; i++) {12 farthest = Math.max(farthest, i + nums[i]);13 if (i == end) { jumps++; end = farthest; }14 }15 return jumps;16 }17 18 public static void main(String[] args) {19 check(jump(new int[]{2, 3, 1, 1, 4}) == 2, "case1");20 check(jump(new int[]{2, 1, 1, 1, 1}) == 3, "case2");21 System.out.println("all tests passed");22 }23 24 static void check(boolean cond, String name) {25 if (!cond) throw new AssertionError("FAILED: " + name);26 System.out.println(" PASS " + name);27 }28}