ReviseAlgo Logo

Greedy Algorithms

Classic Greedy Problems

Master classic Greedy array algorithms: Jump Game reach checks, Gas Station surplus traversals, and Fractional Knapsack density ratios.

Last Updated: August 2, 2026 • 18 min read

1. Introduction

What are Classic Greedy Problems?

Classic Greedy Problems are standard array and packing optimization tasks:
  • Jump Game: Determining if you can leap from index 0 to the last index.
  • Gas Station: Locating the starting station to complete a circular circuit.
  • Fractional Knapsack: Packing items of varying values and weights to maximize value, allowing fractional splits.

    • Why study them?

    These problems are technical interview favorites. They demonstrate how tracking a single state variable (like maximum reachable index or fuel surplus) avoids complex recursion or dynamic programming states, running in optimal O(N) time.

    2. Mental Model: The Dashboard Range Tracker

    Imagine driving a car across a desert:

  • Jump Game: At each milestone (index), you check if you have enough gas to reach the next milestone. You maintain a dashboard metric: Maximum Reachable Distance (maxReachable). If your current location exceeds this distance, you are stranded.
  • Gas Station: You drive from station to station. If your tank runs dry (tank < 0) between station A and B, it means starting at any station from A to B is impossible. You must reset your start search to station B + 1.

    • 3. Core Algorithms & Implementations

    1. Jump Game (LeetCode 55)

  • Initialize maxReachable = 0.
  • Loop through indices i. If i > maxReachable, return false (you cannot reach this index).
  • Update maxReachable = max(maxReachable, i + nums[i]).
  • If maxReachable >= n - 1, return true immediately.

    • 2. Gas Station (LeetCode 134)

  • If the total gas available is less than the total cost needed, completing the circuit is impossible. Return -1.
  • Otherwise, a unique starting index is guaranteed to exist.
  • Track a running tank = 0 and startNode = 0. Iterate through stations. If tank += gas[i] - cost[i] < 0, it means starting at startNode failed. Reset tank = 0 and update startNode = i + 1.

    • 4. Visualizing Jump Game Pointers

    Tracing array nums = [2, 3, 1, 1, 4]:

  • At index 0, we can reach up to index 2.
  • At index 1, our reach expands to index 4, which matches the goal.

    • 5. Real-World Examples

  • Route planning: Finding if electric vehicle recharging coordinates can support trips between cities.
  • Dynamic logistics routing: Merging supply loops dynamically during transport path failures.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Interviewers test index arithmetic:
  • "Given gas stations, return starting index to complete the loop." -> Prove why resetting startNode = i + 1 is correct. If starting at A fails at station B, then starting at any station between A and B will also fail because you would arrive at B with ≥ 0 gas, which was already not enough.
  • "Solve Jump Game II (Minimum jumps to reach end)." -> Maintain maxReachable, currentEnd (end of current jump range), and jumps counter. Once i reaches currentEnd, increment jumps and update currentEnd = maxReachable.

    • Common Mistakes

    Warning: 1. Using DP / Recursion: Solving Jump Game or Gas Station with recursion or 2D Dynamic Programming. While correct, it takes O(N²) time, which will result in a Time Limit Exceeded (TLE) on large inputs.
    > 2. Wrong index wrap-around bounds: Attempting to simulate circular index checks using nested loops ((i + j) % N), leading to complex O(N²) logic. The single pass totalGas >= totalCost check avoids this.

    7. Summary

  • Jump Game: Maintain running maxReachable boundary. Return false if i > maxReachable.
  • Gas Station: Sum checks guarantee solutions. Reset starting index dynamically on negative fuel surplus.
  • Complexities: Both run in optimal O(N) time and O(1) space.

    • 8. Quiz

    Question 1: What is the output of canJump([3, 2, 1, 0, 4])? Answer: false. At index 3 (value 0), maxReachable remains 3. When loop index reaches 4 (4 > 3), we return false.
    Question 2: In Gas Station, if totalGas >= totalCost, why is a unique solution guaranteed to exist? Answer: Because the net sum of gas minus cost over the entire loop is non-negative (≥ 0). Thus, there must be at least one starting station where the cumulative sum never drops below zero.
    Question 3: What is the difference between 0/1 Knapsack and Fractional Knapsack? Answer: In 0/1 Knapsack, you must either take an item fully or leave it, which is NP-hard and requires DP. In Fractional Knapsack, you can take fractions of items, which can be solved greedily by sorting by value density.
    Question 4: True or False: Jump Game II can be solved in O(N) time. Answer: True, using a greedy sliding window range tracker to update jump boundaries.
    Question 5: What is the space complexity of Gas Station? Answer: O(1) auxiliary space, since we only track running scalar tank variables.