Blind 75
Jump Game
- Problem
- LC 55
- Category
- DP
- File
- blind75_LC55JumpGame.java
- Path
- pkg5leetcode/blind75/blind75_LC55JumpGame.java
- Package
- pkg5leetcode.blind75
- Command
- java pkg5leetcode/blind75/blind75_LC55JumpGame.java
- Approach
- Greedy track farthest reachable index.
- Complexity
- Time O(n), Space O(1)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.blind75;2 3/*4 * Jump Game | LC 555 * APPROACH: Greedy track farthest reachable index.6 * COMPLEXITY: Time O(n), Space O(1)7 */8public class blind75_LC55JumpGame {9 static boolean canJump(int[] nums) {10 int reach = 0;11 for (int i = 0; i < nums.length; i++) {12 if (i > reach) return false;13 reach = Math.max(reach, i + nums[i]);14 }15 return true;16 }17 18 public static void main(String[] args) {19 check(canJump(new int[]{2, 3, 1, 1, 4}), "case1");20 check(!canJump(new int[]{3, 2, 1, 0, 4}), "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}