Master DSA: Greedy Approach — Jump Game I & II, Gas Station

The Greedy Approach is a powerful algorithmic paradigm used to solve optimization problems by making locally optimal choices at each step with the hope of finding a global optimum. This chapter explores the core mechanics of greedy algorithms, establishes when to use them over Dynamic Programming (DP), and provides deep-dive walkthroughs of three classic interview problems: Jump Game I, Jump Game II, and Gas Station.

1. Core Philosophy of the Greedy Approach

A greedy algorithm builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. Unlike Dynamic Programming or Backtracking, which systematically evaluate all possible future paths before making a decision, a greedy algorithm commits to a choice and never backtracks.

Real-Life Analogy: The Coin Change Problem (U.S. Currency)

If you need to make change for $41\phi$ using the fewest coins possible from standard U.S. denominations ($25\phi$, $10\phi$, $5\phi$, $1\phi$):

1. You greedily take the largest coin that is less than or equal to $41\phi$: a Quarter ($25\phi$). Remaining: $16\phi$.
2. You greedily take the largest coin less than or equal to $16\phi$: a Dime ($10\phi$). Remaining: $6\phi$.
3. You greedily take a Nickel ($5\phi$). Remaining: $1\phi$.
4. You take a Penny ($1\phi$). Remaining: $0\phi$.

This local choice yields the globally optimal solution of 4 coins: [25, 10, 5, 1]. However, if the denominations were different (e.g., $25\phi$, $20\phi$, $1\phi$) and you needed to make $40\phi$, a greedy choice would pick $25\phi$ first, leaving $15\phi$, which requires fifteen $1\phi$ coins (total 16 coins). The global optimum is actually two $20\phi$ coins. This demonstrates that greedy choices do not always yield global optima unless specific mathematical properties are met.

2. Characteristics and Conditions for Greedy Algorithms

To successfully apply a greedy strategy, a problem must exhibit two key properties:

1. Greedy Choice Property: A global optimum can be arrived at by making locally optimal (greedy) choices at each step without looking ahead or backtracking.
2. Optimal Substructure: An optimal solution to the problem contains optimal solutions to its subproblems.

Comparison: Greedy vs. Dynamic Programming vs. Backtracking

3. Real-World Analogy: Activity Selection Problem

The Activity Selection Problem is the classic textbook example of a greedy algorithm.

Problem Statement

You are given $N$ activities with their start and end times. Select the maximum number of activities that can be performed by a single person, assuming they cannot perform overlapping activities.

Greedy Strategy

1. Sort all activities by their finish times in ascending order.
2. Select the first activity from the sorted list.
3. For the remaining activities, pick the next activity whose start time is greater than or equal to the finish time of the previously selected activity.

By prioritizing the activity that finishes earliest, we maximize the remaining time available for other activities.

4. Jump Game I — Problem Statement & Mental Model

Problem Statement (LeetCode 55)

You are given an integer array nums. You are initially positioned at the array's first index (index 0). Each element in the array represents your maximum jump length at that position. Return true if you can reach the last index, or false otherwise.

Example 1

• Input: nums = [2, 3, 1, 1, 4]
• Output: true
• Explanation: Jump 1 step from index 0 to 1, then jump 3 steps to the last index.

Example 2

• Input: nums = [3, 2, 1, 0, 4]
• Output: false
• Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

5. Jump Game I — Step-by-Step Greedy Evolution & Code

The Greedy Mental Model

Instead of trying every single jump combination (which leads to an exponential $O(2^N)$ backtracking solution), we can track the farthest index we can reach at any point in time.

Let maxJump represent the maximum index we can reach. As we iterate through the array from left to right:

1. If we ever encounter an index i that is greater than maxJump, it means we can never reach this index. We must immediately return false.
2. Otherwise, we update our maxJump using the formula:

3. If maxJump reaches or exceeds the last index (nums.length - 1), we can return true early.

Vertical Workflow of Reachability Tracking

Java Implementation

public class JumpGameI {
    public boolean canJump(int[] nums) {
        int maxJump = 0;
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            // If the current index is unreachable, we cannot proceed
            if (maxJump < i) {
                return false;
            }

            // Update the furthest reachable index
            maxJump = Math.max(maxJump, i + nums[i]);

            // Optimization: If we can already reach the last index, return true
            if (maxJump >= n - 1) {
                return true;
            }
        }

        return true;
    }
}

Complexity Analysis

• Time Complexity: $O(N)$ because we traverse the array of size $N$ exactly once.
• Space Complexity: $O(1)$ as we only use a single variable maxJump to track state.

6. Jump Game II — Minimum Jumps Strategy

Problem Statement (LeetCode 45)

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0]. Each element nums[i] represents the maximum length of a forward jump from index i.

Your goal is to reach the last index in the minimum number of jumps. You can assume that you can always reach the last index.

Example

• Input: nums = [2, 3, 1, 1, 4]
• Output: 2
• Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

The Greedy Window Strategy

To find the minimum number of jumps, we can think of our search space as a series of jump windows.

[ 2,   3,   1,   1,   4 ]
  |    |____|    |____|
Window 0  Window 1   Window 2
(Jump 0)  (Jump 1)   (Jump 2)

1. From index 0 (value 2), we can jump to either index 1 or index 2. This range [1, 2] forms our first jump window.
2. To find the boundary of the second jump window, we calculate the furthest index we can reach from any index inside the first window [1, 2].
   • From index 1 (value 3), we can reach index 1 + 3 = 4.
   • From index 2 (value 1), we can reach index 2 + 1 = 3.
   • The maximum reach is 4.
3. Once we finish exploring the current window, we must make another jump. We increment our jump counter, and set our new window boundary (end) to the maximum reach we discovered.

7. Jump Game II — Step-by-Step Implementation & Code

State Variables

• maxJump: The furthest index we can reach from any index visited so far.
• end: The boundary of the current jump window.
• ans: The number of jumps taken.

Java Implementation

public class JumpGameII {
    public int jump(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return 0;
        }

        int maxJump = 0;
        int end = 0;
        int ans = 0;

        // We loop up to n - 1 because once we reach the last index, 
        // we do not need to jump again.
        for (int i = 0; i < n - 1; i++) {
            // Update the furthest index we can reach from the current position
            maxJump = Math.max(maxJump, i + nums[i]);

            // If we have reached the end of the current jump window
            if (i == end) {
                ans++;          // We must take another jump
                end = maxJump;  // Set the boundary of the next jump window

                // If our new window boundary reaches or exceeds the last index, we can stop
                if (end >= n - 1) {
                    break;
                }
            }
        }

        return ans;
    }
}

Dry Run Execution: nums = [2, 3, 1, 1, 4]

Initial State: maxJump = 0, end = 0, ans = 0, n = 5

i = 0:
  - maxJump = max(0, 0 + 2) = 2
  - i == end (0 == 0) is TRUE:
    * ans incremented to 1
    * end updated to maxJump (2)
    * end (2) is not >= 4. Continue.

i = 1:
  - maxJump = max(2, 1 + 3) = 4
  - i == end (1 == 2) is FALSE. Continue.

i = 2:
  - maxJump = max(4, 2 + 1) = 4
  - i == end (2 == 2) is TRUE:
    * ans incremented to 2
    * end updated to maxJump (4)
    * end (4) >= 4 is TRUE. Break loop.

Result: ans = 2

Complexity Analysis

• Time Complexity: $O(N)$ because we iterate through the array of size $N$ exactly once.
• Space Complexity: $O(1)$ as we only use three scalar variables.

8. Gas Station — Problem Statement & Circular Simulation

Problem Statement (LeetCode 134)

There are n gas stations along a circular route, where the amount of gas at the $i$-th station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the $i$-th station to its next $(i + 1)$-th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there is a solution, it is guaranteed to be unique.

Example

• Input:
  • gas = [1, 2, 3, 4, 5]
  • cost = [3, 4, 5, 1, 2]
• Output: 3

Circular Simulation Walkthrough (Starting at Index 3)

Station 3:
  - Gas available = 4, Cost to next = 1
  - Remaining Gas = 4 - 1 = 3
  - Move to Station 4

Station 4:
  - Gas available = 3 (remaining) + 5 (at station) = 8
  - Cost to next = 2
  - Remaining Gas = 8 - 2 = 6
  - Move to Station 0 (Circular wrap-around)

Station 0:
  - Gas available = 6 (remaining) + 1 (at station) = 7
  - Cost to next = 3
  - Remaining Gas = 7 - 3 = 4
  - Move to Station 1

Station 1:
  - Gas available = 4 (remaining) + 2 (at station) = 6
  - Cost to next = 4
  - Remaining Gas = 6 - 4 = 2
  - Move to Station 2

Station 2:
  - Gas available = 2 (remaining) + 3 (at station) = 5
  - Cost to next = 5
  - Remaining Gas = 5 - 5 = 0
  - Move to Station 3 (Back to start!)

9. Gas Station — Brute Force vs. Optimized $O(N)$ Greedy Strategy

The Naive Brute Force Approach

The naive approach is to simulate the journey starting from every single station $i \in [0, N-1]$. For each starting station, we run a nested loop to simulate the circular path. If we successfully return to the starting station, we return its index.

• Time Complexity: $O(N^2)$
• Space Complexity: $O(1)$

This approach will result in a Time Limit Exceeded (TLE) error on large datasets.

The Optimized $O(N)$ Greedy Approach

To optimize this to linear time, we must leverage two critical mathematical insights:

Insight 1: Global Feasibility Check

If the total sum of gas is strictly less than the total sum of cost, it is mathematically impossible to complete the circular journey, regardless of which station you start from.

Conversely, if $\sum \text{gas}[i] \ge \sum \text{cost}[i]$, a valid starting station is guaranteed to exist.

Insight 2: Local Failure Elimination

Suppose we start at station $A$ and fail to reach station $B$ because our tank becomes negative when trying to move from $B-1$ to $B$.

This means that any station between $A$ and $B-1$ cannot be a valid starting point either. Why? Because starting at $A$ allowed us to arrive at any intermediate station with a non-negative amount of gas (or at worst, zero). If even with this "bonus" gas from previous stations we couldn't pass station $B$, starting from any intermediate station with an empty tank will definitely fail to pass station $B$.

Therefore, we can safely skip all stations from $A$ to $B-1$ and set our next candidate starting station to $B$.

10. Gas Station — Step-by-Step Implementation & Code

Java Implementation

public class GasStation {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = 0;
        int totalCost = 0;

        // 1. Check global feasibility
        for (int i = 0; i < gas.length; i++) {
            totalGas += gas[i];
            totalCost += cost[i];
        }

        if (totalGas < totalCost) {
            return -1; // Impossible to complete the circuit
        }

        // 2. Find the unique starting point
        int remainingGas = 0;
        int position = 0;

        for (int i = 0; i < gas.length; i++) {
            remainingGas += gas[i] - cost[i];

            // If the tank becomes negative, we cannot reach station i + 1
            if (remainingGas < 0) {
                // Reset tank and set the next station as the new candidate start
                remainingGas = 0;
                position = i + 1;
            }
        }

        return position;
    }
}

Dry Run Execution: gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]

1. Global Check:

   • totalGas = $1 + 2 + 3 + 4 + 5 = 15$
   • totalCost = $3 + 4 + 5 + 1 + 2 = 15$
   • Since totalGas >= totalCost ($15 \ge 15$), a solution is guaranteed.

2. Greedy Traversal:

• Result: Returns position = 3.

Complexity Analysis

• Time Complexity: $O(N)$ because we perform two linear passes over the arrays (which can even be optimized into a single pass).
• Space Complexity: $O(1)$ auxiliary space.

11. Summary and Key Takeaways

• Greedy Choice Rule: Always make the choice that looks best at the current moment without worrying about future consequences.
• No Backtracking: Once a greedy decision is made, it is locked in. This makes greedy algorithms exceptionally fast ($O(N)$ or $O(N \log N)$) but less generally applicable than Dynamic Programming.
• Jump Game I: Solved by tracking the maximum reachable index (maxJump). If the current index i exceeds maxJump, the end is unreachable.
• Jump Game II: Solved using a sliding window approach where we count the number of jumps needed to transition from one maximum reach boundary (end) to the next.
• Gas Station: Solved by checking global feasibility ($\sum \text{gas} \ge \sum \text{cost}$) and using local failure elimination to skip invalid starting positions in $O(N)$ time.
• When to Avoid Greedy: If local choices affect the feasibility of future choices in a non-trivial way (e.g., the 0/1 Knapsack problem or non-standard coin change denominations), use Dynamic Programming or Backtracking instead.