LeetCode Pattern/Greedy Algorithm/Greedy State Tracking: Jump Game, Gas Station, and Cumulative Greedy Patterns

Greedy State Tracking: Jump Game, Gas Station, and Cumulative Greedy Patterns

LeetCopilot Team

Dec 30, 2025

14 min read

Greedy AlgorithmState TrackingReachabilityTemplatesInterview Prep

Master greedy problems that track cumulative state (balance, reach, fuel). Learn single-pass templates, understand why tracking state greedily works, and solve Jump Game, Gas Station, and all reachability problems.

Complete Guide

The Complete Greedy Algorithm Guide: Master All Patterns, Proofs, and Recognition Techniques

The ultimate comprehensive guide to greedy algorithms. Learn all patterns (interval scheduling, sorting, state tracking), when to use greedy vs DP, complete templates in multiple languages, proof techniques, and a systematic approach to solve any greedy problem.

Read the complete guide

Greedy state tracking is the most elegant greedy pattern. No sorting. No complex data structures. Just a single pass through the array, tracking cumulative state.

But here's what makes it powerful: if you can't reach a position with the best possible state so far, you can never reach it. This simple insight unlocks O(n) solutions to problems that seem to require O(n²) dynamic programming.

In this guide, you'll learn when to track state greedily, complete templates, rigorous proofs, and how to recognize this pattern instantly.

TL;DR

Use greedy state tracking when:

Reachability problems (can you reach the end?)
Balance/accumulation problems (cumulative sum, fuel)
Can determine feasibility in one pass
Want O(n) time, O(1) space

Template:

python

state = initial_value

for i, val in enumerate(arr):
    # Check if current position is reachable
    if not is_reachable(state, i):
        return False
    
    # Update state based on current element
    state = update_state(state, val, i)

return is_goal_reached(state)

Time: O(n), Space: O(1)

Key insight: Track maximum/cumulative state greedily. If you can't reach position i with best state, you can never reach it.

What Is Greedy State Tracking?

The Core Concept

Problem type: Determine if something is achievable (reach end, complete circuit, etc.) by tracking cumulative state in a single pass.

Greedy insight: At each position, track the best possible state (maximum reach, cumulative balance, etc.). If current position is unreachable with best state, it's impossible.

Example (Jump Game):

code

Array: [2, 3, 1, 1, 4]
Goal: Can you reach index 4?

Track maximum reach:
  i=0: nums[0]=2, max_reach = max(0, 0+2) = 2
  i=1: nums[1]=3, max_reach = max(2, 1+3) = 4
  i=2: nums[2]=1, max_reach = max(4, 2+1) = 4
  i=3: nums[3]=1, max_reach = max(4, 3+1) = 4
  i=4: max_reach=4 ≥ 4 → Can reach! ✓

Result: True

Why One Pass Is Enough

Key insight: If you can't reach position i with maximum possible reach from positions 0..i-1, you can never reach position i (or anything beyond).

Proof:

Let max_reach be the farthest position reachable from 0..i-1
If i > max_reach, position i is unreachable
No future position can help you reach i (they're beyond i)
Therefore, one pass tracking max_reach is sufficient ✓

Contrast with DP:

DP: Build up solutions for all subproblems (O(n²))
Greedy: Track best state in one pass (O(n))
When greedy works, it's exponentially faster

The Universal Template

Python Template

python

def greedy_state_tracking(arr):
    """
    Template for greedy state tracking (reachability, balance, etc.).
    
    Args:
        arr: Input array
    
    Returns:
        True if goal is achievable, False otherwise
    
    Time: O(n)
    Space: O(1)
    """
    # Initialize state
    state = 0  # Could be max_reach, balance, etc.
    
    for i in range(len(arr)):
        # Check if current position is reachable/valid
        if i > state:  # Or other condition
            return False
        
        # Update state based on current element
        state = max(state, i + arr[i])  # Or other update
        
        # Early exit if goal reached
        if state >= len(arr) - 1:
            return True
    
    return True  # Or check final state

# Example: Jump Game
def canJump(nums):
    max_reach = 0
    
    for i in range(len(nums)):
        if i > max_reach:
            return False
        
        max_reach = max(max_reach, i + nums[i])
        
        if max_reach >= len(nums) - 1:
            return True
    
    return True

JavaScript Template

javascript

function greedyStateTracking(arr) {
    let state = 0;
    
    for (let i = 0; i < arr.length; i++) {
        if (i > state) {
            return false;
        }
        
        state = Math.max(state, i + arr[i]);
        
        if (state >= arr.length - 1) {
            return true;
        }
    }
    
    return true;
}

// Example: Jump Game
function canJump(nums) {
    let maxReach = 0;
    
    for (let i = 0; i < nums.length; i++) {
        if (i > maxReach) return false;
        
        maxReach = Math.max(maxReach, i + nums[i]);
        
        if (maxReach >= nums.length - 1) return true;
    }
    
    return true;
}

Java Template

java

public boolean greedyStateTracking(int[] arr) {
    int state = 0;
    
    for (int i = 0; i < arr.length; i++) {
        if (i > state) {
            return false;
        }
        
        state = Math.max(state, i + arr[i]);
        
        if (state >= arr.length - 1) {
            return true;
        }
    }
    
    return true;
}

// Example: Jump Game
public boolean canJump(int[] nums) {
    int maxReach = 0;
    
    for (int i = 0; i < nums.length; i++) {
        if (i > maxReach) return false;
        
        maxReach = Math.max(maxReach, i + nums[i]);
        
        if (maxReach >= nums.length - 1) return true;
    }
    
    return true;
}

Pattern 1: Tracking Maximum Reach

Problem: Jump Game (LeetCode #55)

Problem: Determine if you can reach the last index.

Greedy insight: Track maximum reachable position. If current position is beyond max reach, it's unreachable.

Solution:

python

def canJump(nums: List[int]) -> bool:
    """
    Determine if you can reach the last index.
    
    Args:
        nums: Array where nums[i] = max jump length from position i
    
    Returns:
        True if can reach last index, False otherwise
    
    Time: O(n)
    Space: O(1)
    """
    max_reach = 0
    
    for i in range(len(nums)):
        # Current position is unreachable
        if i > max_reach:
            return False
        
        # Update maximum reachable position
        max_reach = max(max_reach, i + nums[i])
        
        # Early exit if we can reach the end
        if max_reach >= len(nums) - 1:
            return True
    
    return True

# Examples
print(canJump([2,3,1,1,4]))  # True
# Path: 0 → 1 → 4 (or 0 → 2 → 3 → 4)

print(canJump([3,2,1,0,4]))  # False
# Stuck at index 3 (value 0, can't jump further)

Why it works:

max_reach tracks farthest position reachable so far
If i > max_reach, position i is unreachable
If max_reach ≥ last index, we can reach the end

Proof:

Base case: max_reach = 0 initially (can reach position 0)
Inductive step: If we can reach position i, we can reach any j ≤ i + nums[i]
max_reach = max of all reachable positions
If i > max_reach at any point, position i (and beyond) is unreachable ✓

See detailed guide: Jump Game: Greedy vs DP

Problem: Jump Game II (LeetCode #45)

Problem: Find minimum jumps to reach the end.

Greedy insight: BFS-style greedy. Track current range and farthest reach, increment jumps when leaving current range.

Solution:

python

def jump(nums: List[int]) -> int:
    """
    Find minimum jumps to reach the end.
    
    Args:
        nums: Array where nums[i] = max jump length from position i
    
    Returns:
        Minimum number of jumps
    
    Time: O(n)
    Space: O(1)
    """
    jumps = 0
    current_end = 0  # End of current jump range
    farthest = 0     # Farthest position reachable
    
    # Don't need to jump from last position
    for i in range(len(nums) - 1):
        # Update farthest reachable position
        farthest = max(farthest, i + nums[i])
        
        # Reached end of current jump range
        if i == current_end:
            jumps += 1
            current_end = farthest
            
            # Early exit if we can reach the end
            if current_end >= len(nums) - 1:
                break
    
    return jumps

# Examples
print(jump([2,3,1,1,4]))  # 2
# Jump 1: 0 → 1, Jump 2: 1 → 4

print(jump([2,3,0,1,4]))  # 2
# Jump 1: 0 → 1, Jump 2: 1 → 4

Why it works:

Think of it as BFS levels
current_end = end of current level
farthest = farthest position in next level
When we reach end of current level, increment jumps

Visualization:

code

Array: [2, 3, 1, 1, 4]

Level 0: [0]
  From 0, can reach: 1, 2
  
Level 1: [1, 2]
  From 1, can reach: 2, 3, 4
  From 2, can reach: 3
  Farthest: 4
  
Reached end in 2 jumps ✓

Pattern 2: Tracking Cumulative Balance

Problem: Gas Station (LeetCode #134)

Problem: Find starting gas station to complete circuit (or -1 if impossible).

Greedy insight: If you can't reach station j from station i, you can't reach j from any station between i and j.

Solution:

python

def canCompleteCircuit(gas: List[int], cost: List[int]) -> int:
    """
    Find starting gas station to complete circuit.
    
    Args:
        gas: gas[i] = gas at station i
        cost: cost[i] = gas needed to travel from station i to i+1
    
    Returns:
        Starting station index, or -1 if impossible
    
    Time: O(n)
    Space: O(1)
    """
    total_tank = 0    # Total gas balance
    current_tank = 0  # Current gas balance
    start = 0         # Starting station
    
    for i in range(len(gas)):
        total_tank += gas[i] - cost[i]
        current_tank += gas[i] - cost[i]
        
        # Can't reach next station from current start
        if current_tank < 0:
            # Try starting from next station
            start = i + 1
            current_tank = 0
    
    # If total gas >= total cost, circuit is possible
    return start if total_tank >= 0 else -1

# Example
gas  = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
print(canCompleteCircuit(gas, cost))  # 3

# Start at station 3:
#   3→4: gas=4, cost=1, balance=+3
#   4→0: gas=5, cost=2, balance=+3+3=+6
#   0→1: gas=1, cost=3, balance=+6-2=+4
#   1→2: gas=2, cost=4, balance=+4-2=+2
#   2→3: gas=3, cost=5, balance=+2-2=0 ✓

Why it works:

Claim: If you can't reach station j from station i, you can't reach j from any station k where i < k < j.

Proof:

Assume we can't reach j from i: cumulative balance from i to j is negative
For any station k between i and j:
- Balance from i to k is non-negative (otherwise we'd have failed earlier)
- Balance from k to j = (balance from i to j) - (balance from i to k)
- Since balance i→j is negative and balance i→k is non-negative
- Balance k→j must be negative
Therefore, can't reach j from k either ✓

Conclusion: If we fail at station j, next candidate is j+1.

See detailed guide: Gas Station: Why Greedy Works

Pattern 3: Tracking Minimum/Maximum State

Problem: Best Time to Buy and Sell Stock (LeetCode #121)

Problem: Maximize profit from one buy and one sell.

Greedy insight: Track minimum price seen so far, calculate profit at each position.

Solution:

python

def maxProfit(prices: List[int]) -> int:
    """
    Find maximum profit from one transaction.
    
    Args:
        prices: prices[i] = price on day i
    
    Returns:
        Maximum profit
    
    Time: O(n)
    Space: O(1)
    """
    min_price = float('inf')
    max_profit = 0
    
    for price in prices:
        # Update minimum price seen so far
        min_price = min(min_price, price)
        
        # Calculate profit if we sell today
        profit = price - min_price
        
        # Update maximum profit
        max_profit = max(max_profit, profit)
    
    return max_profit

# Example
print(maxProfit([7,1,5,3,6,4]))  # 5
# Buy at 1, sell at 6, profit = 5

print(maxProfit([7,6,4,3,1]))  # 0
# No profit possible (prices always decreasing)

Why it works:

To maximize profit, buy at minimum price before selling
Track minimum price seen so far
At each day, calculate profit if we sell today
Maximum profit is the best across all days

When to Use Greedy State Tracking

✅ Use When:

Reachability problems
- "Can you reach the end?"
- "Can you complete the circuit?"
Balance/accumulation problems
- Cumulative sum
- Running balance
- Fuel tracking
Single-pass feasibility
- Can determine answer in one pass
- Don't need to explore all paths
Want O(n) time, O(1) space
- Optimal efficiency
- No extra data structures

❌ Don't Use When:

Need to count/find all solutions
- Greedy only determines feasibility
- Use DP or backtracking
State depends on future elements
- Can't make greedy decision
- Need lookahead or DP
Multiple interdependent choices
- Greedy choice property doesn't hold
- Use DP

Common Mistakes

Mistake 1: Resetting State Too Early

❌ Wrong:

python

# Gas Station
if current_tank < 0:
    start = i + 1
    # Forgot to reset current_tank!

✅ Correct:

python

if current_tank < 0:
    start = i + 1
    current_tank = 0  # Reset balance

Mistake 2: Not Considering Negative Balances

❌ Wrong:

python

# Jump Game
max_reach = max(max_reach, i + nums[i])
# Didn't check if i > max_reach first!

✅ Correct:

python

if i > max_reach:
    return False
max_reach = max(max_reach, i + nums[i])

Mistake 3: Wrong Early Exit Condition

❌ Wrong:

python

# Jump Game
if max_reach >= len(nums):  # Should be len(nums) - 1
    return True

✅ Correct:

python

if max_reach >= len(nums) - 1:  # Last index
    return True

Complexity Analysis

Time Complexity: O(n)

Single pass through array
Constant work per element
Total: O(n)

Space Complexity: O(1)

Only track state variables
No extra data structures
Total: O(1)

Comparison:

Approach	Time	Space	When to Use
Greedy State Tracking	O(n)	O(1)	Reachability, balance
DP	O(n²)	O(n)	Need all subproblems
Backtracking	O(2^n)	O(n)	Need all solutions

Practice Problems

Master greedy state tracking:

Beginner:

Jump Game (#55) - basic template
Best Time to Buy and Sell Stock (#121) - track minimum
Can Place Flowers (#605) - track state

Intermediate:
4. Jump Game II (#45) - minimum jumps
5. Gas Station (#134) - cumulative balance
6. Minimum Deletions to Make String Balanced (#1653)

Advanced:
7. Jump Game III (#1306) - bidirectional
8. Jump Game IV (#1345) - with teleportation
9. Jump Game VII (#1871) - with constraints

FAQ

Q: How do I know if greedy state tracking works?

A: If you can determine feasibility by tracking cumulative/maximum state in one pass, greedy works. Test with examples.

Q: What's the difference from DP?

A: Greedy tracks best state in one pass (O(n)). DP builds up all subproblems (O(n²)). Greedy is faster when it works.

Q: Can I use this for "minimum jumps" problems?

A: Yes! Jump Game II uses greedy state tracking with BFS-style levels.

Q: What if I need to track multiple states?

A: You can track multiple variables (e.g., current_tank and total_tank in Gas Station).

Conclusion

Greedy state tracking is the most elegant greedy pattern—simple, fast, and powerful.

Key principles:

Track best state in single pass
If unreachable with best state, impossible
O(n) time, O(1) space - optimal efficiency
Prove correctness with induction or contradiction

The template:

python

state = 0
for i, val in enumerate(arr):
    if i > state:
        return False
    state = max(state, i + val)
return True

When to use:

Reachability problems
Balance/accumulation
Single-pass feasibility

Master this pattern, and you'll solve state tracking problems with confidence. For more patterns, see the complete greedy guide, Jump Game: Greedy vs DP, and Gas Station: Why Greedy Works.

Next time you see "can you reach," reach for greedy state tracking.

Want to Practice LeetCode Smarter?

LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.

Learn More About LeetCopilot

Add to Chrome for free

Also compatible with Edge, Brave, and Opera

Greedy State Tracking: Jump Game, Gas Station, and Cumulative Greedy Patterns

The Complete Greedy Algorithm Guide: Master All Patterns, Proofs, and Recognition Techniques

Table of Contents

TL;DR

What Is Greedy State Tracking?

The Core Concept

Why One Pass Is Enough

The Universal Template

Python Template

JavaScript Template

Java Template

Pattern 1: Tracking Maximum Reach

Problem: Jump Game (LeetCode #55)

Problem: Jump Game II (LeetCode #45)

Pattern 2: Tracking Cumulative Balance

Problem: Gas Station (LeetCode #134)

Pattern 3: Tracking Minimum/Maximum State

Problem: Best Time to Buy and Sell Stock (LeetCode #121)

When to Use Greedy State Tracking

✅ Use When:

❌ Don't Use When:

Common Mistakes

Mistake 1: Resetting State Too Early

Mistake 2: Not Considering Negative Balances

Mistake 3: Wrong Early Exit Condition

Complexity Analysis

Practice Problems

FAQ

Conclusion

Want to Practice LeetCode Smarter?

Related Tutorials

Why Greedy Fails on Coin Change (And When You Need Dynamic Programming Instead)

Interval Scheduling: Why Sort by End Time Works (Proof and Intuition)

Wrong Sorting Criterion: The #1 Greedy Mistake (And How to Fix It)