Jump Game (Greedy)
Determine if you can reach the last index of an array where each element represents the maximum jump length from that position. The elegant greedy solution tracks the furthest reachable position in a single O(n) pass. Also includes the variant problem: find minimum number of jumps needed to reach the end using a BFS-like greedy approach.
Visualization
Interactive visualization for Jump Game (Greedy)
Jump Game (Greedy)
Array (value = max jump length):
• Time: O(n) - greedy approach
• Track max reachable index
• Stop if current index > max reachable
Interactive visualization with step-by-step execution
Implementation
1function canJump(nums: number[]): boolean {
2 let maxReach = 0;
3
4 for (let i = 0; i < nums.length; i++) {
5 if (i > maxReach) return false;
6 maxReach = Math.max(maxReach, i + nums[i]);
7 if (maxReach >= nums.length - 1) return true;
8 }
9 return true;
10}
11
12function minJumps(nums: number[]): number {
13 let jumps = 0, currentEnd = 0, furthest = 0;
14
15 for (let i = 0; i < nums.length - 1; i++) {
16 furthest = Math.max(furthest, i + nums[i]);
17 if (i === currentEnd) {
18 jumps++;
19 currentEnd = furthest;
20 }
21 }
22 return jumps;
23}Deep Dive
Theoretical Foundation
Jump Game uses greedy invariant: track furthest index reachable so far. At each position i, check if i is reachable (i <= furthest). If yes, update furthest = max(furthest, i + nums[i]). If at any point i > furthest, positions beyond are unreachable. For Minimum Jumps variant: use greedy BFS approach with currentEnd and furthest markers, incrementing jump count when reaching currentEnd. Both are O(n) single pass, demonstrating greedy optimality.
Complexity
Time
O(n)
O(n)
O(n)
Space
O(1)
Applications
Industry Use
Game AI pathfinding
Platform game mechanics
Network routing optimization
Resource allocation planning
Path optimization problems
Use Cases
Related Algorithms
Huffman Coding
Huffman Coding is a lossless data compression algorithm that creates optimal prefix-free variable-length codes based on character frequencies. Developed by David A. Huffman in 1952 as a student at MIT, it uses a greedy approach to build a binary tree where frequent characters get shorter codes. This algorithm is fundamental in ZIP, JPEG, MP3, and many compression formats.
Activity Selection Problem
Select the maximum number of non-overlapping activities from a set, where each activity has a start and end time. This classic greedy algorithm demonstrates the greedy choice property: always selecting the activity that finishes earliest leaves the most room for remaining activities. Used in scheduling problems, resource allocation, and interval management. Achieves optimal solution with O(n log n) time complexity.
Fractional Knapsack Problem
Given items with values and weights, and a knapsack with capacity, select items (or fractions thereof) to maximize total value. Unlike the 0/1 knapsack where items must be taken whole, the fractional knapsack allows taking fractions of items. The greedy approach of taking items in order of value-to-weight ratio yields the optimal solution in O(n log n) time. This demonstrates when greedy algorithms work vs. when dynamic programming is needed.
Job Sequencing with Deadlines
Schedule jobs with deadlines and profits to maximize total profit. Each job takes 1 unit time and has a deadline and profit. The greedy strategy is to sort jobs by profit (descending) and greedily schedule each job as late as possible before its deadline. This maximizes profit while respecting constraints. Used in task scheduling, CPU job management, and project planning.