Greedy Algorithms: Code Templates in 6 Languages

Coding Patterns - Guide to 30 Core Algorithm Patterns

Greedy Algorithms: Complete Guide with Code Examples

If you have not read the concept guide yet, start there for the greedy choice property and the intuition. This page gives you templates you can adapt during an interview. The main template runs in

O(N)

time with

O(1)

extra space. The variations cover the other common greedy shapes.

Main Template: Furthest-Reach Scan

This is the greedy loop in its purest form. One state variable holds the best outcome reachable so far. Each element either extends it or does not. The template decides, for every index, whether the jumps seen so far can still reach it.

Use this for Jump Game .

function canJump(nums) {
    // maxReach is the furthest index we can get to
    // with the jumps we have seen so far.
    let maxReach = 0;

    for (let i = 0; i < nums.length; i++) {
        // If the current index is beyond our reach, a gap
        // exists and the last index is unreachable.
        if (i > maxReach) return false;

        // The greedy decision: keep the largest reach.
        // No other jump can improve on this value.
        maxReach = Math.max(maxReach, i + nums[i]);
    }

    return true;
}

def can_jump(nums: List[int]) -> bool:
    # max_reach tracks the furthest index reachable
    # using the jumps examined so far.
    max_reach = 0

    for i in range(len(nums)):
        # Once an index lies beyond max_reach, no future
        # jump can help: we can never stand on that index.
        if i > max_reach:
            return False

        # Extend the reach when the current jump beats it.
        # This is the greedy choice property in code.
        max_reach = max(max_reach, i + nums[i])

    return True

public boolean canJump(int[] nums) {
    // maxReach holds the furthest index we can reach
    // with the jumps processed so far.
    int maxReach = 0;

    for (int i = 0; i < nums.length; i++) {
        // An index beyond our reach means a gap that
        // no later jump can bridge.
        if (i > maxReach) return false;

        // Keep the larger reach. The current jump either
        // extends it or is dominated by an earlier one.
        maxReach = Math.max(maxReach, i + nums[i]);
    }

    return true;
}

bool canJump(vector<int>& nums) {
    // maxReach is the furthest index reachable with the
    // jumps examined so far.
    int maxReach = 0;

    for (size_t i = 0; i < nums.size(); i++) {
        // If the current index is unreachable, a gap
        // exists and the last index is unreachable too.
        if ((int)i > maxReach) return false;

        // Keep the larger reach. Extending it is never
        // worse than any alternative jump.
        maxReach = max(maxReach, (int)i + nums[i]);
    }

    return true;
}

func canJump(nums []int) bool {
    // maxReach is the furthest index reachable with the
    // jumps examined so far.
    maxReach := 0

    for i := 0; i < len(nums); i++ {
        // An index beyond our reach is a gap. No later
        // jump can bridge it, so the end is unreachable.
        if i > maxReach {
            return false
        }

        // Keep the larger reach. The greedy choice never
        // hurts because it only widens our options.
        if i+nums[i] > maxReach {
            maxReach = i + nums[i]
        }
    }

    return true
}

def can_jump(nums)
  # max_reach holds the furthest index we can reach
  # with the jumps processed so far.
  max_reach = 0

  nums.each_with_index do |jump, i|
    # An index beyond our reach is a gap that no later
    # jump can close.
    return false if i > max_reach

    # Keep the larger reach. Extending it is the greedy
    # choice and it can never shrink our options.
    max_reach = [max_reach, i + jump].max
  end

  true
end

Templates only help if you can recall them without staring at the screen. Turn these snippets into flashcards for daily mobile review.

Code Breakdown

Key Variables

nums: the input. For this template, each value is a maximum jump length from its index.
maxReach: the state variable. It holds the furthest index reachable with the jumps examined so far. It never shrinks.

Visual Mechanism

    graph TD
    A["maxReach = 0"] --> B["For each index i"]
    B --> C{"i > maxReach?"}
    C -->|Yes| D["Return false: a gap exists"]
    C -->|No| E["maxReach = max(maxReach, i + nums[i])"]
    E --> F{"More elements?"}
    F -->|Yes| B
    F -->|No| G["Return true"]

Critical Sections

The initialization sets maxReach to 0 because index 0 is always reachable by definition. No other starting value is needed.

The greedy decision is the update. Extending the reach is never worse than any alternative, because a larger reach only adds options. This is the greedy choice property applied to a single state variable.

The failure check is where the correctness lives. If an index lies beyond maxReach, no future jump can help, since every later jump starts from a position that is itself unreachable. The loop ends with true only when no such gap appears.

The same shape, with a different state variable, solves Best Time to Buy and Sell Stock II . There the state is the running profit, and the greedy decision adds each price rise as it appears.

Variations

1. Sort-Then-Scan Selection

Use this when the input must be ordered before the greedy pass can work. The sort key is the greedy choice itself, so picking the wrong key breaks the whole approach.

Use this for interval-style problems. The full treatment lives on the interval scheduling pages.

def select_max(intervals):
    # Sorting by end time is the greedy choice. The
    # earliest-finishing interval leaves the most room
    # for everything after it.
    intervals.sort(key=lambda x: x[1])

    selected = []
    last_end = float('-inf')

    for start, end in intervals:
        # Take the interval when it does not overlap the
        # last selection, then advance the boundary.
        if start >= last_end:
            selected.append((start, end))
            last_end = end

    return selected

O(N log N)

time,

O(1)

extra space. The sort dominates.

2. Greedy Matching

Use this when two sorted collections must be paired and every pair is independent. The smallest useful cookie, the cheapest available unit, the lightest feasible load. The rule is always to consume the least that satisfies the need.

Use this for Assign Cookies .

def find_content_children(g, s):
    g.sort()
    s.sort()

    child = 0
    cookie = 0

    while child < len(g) and cookie < len(s):
        # Give the child the smallest cookie that works.
        # A bigger cookie would not help anyone else more.
        if s[cookie] >= g[child]:
            child += 1
        cookie += 1

    return child

O(N log N)

time,

O(1)

extra space. Both arrays are sorted once.

3. Frequency-Block Scheduling

Use this when items must be spaced apart by a cooldown and the most frequent item decides the pace. The answer is a formula, not a simulation.

Use this for Task Scheduler .

def least_interval(tasks, n):
    freq = [0] * 26
    for task in tasks:
        freq[ord(task) - ord('A')] += 1

    max_freq = max(freq)
    # Tasks tied for the most frequent each occupy
    # one slot in the final frame.
    max_count = freq.count(max_freq)

    # max_freq - 1 full frames of n + 1 slots, plus the
    # tail frame that holds the tied tasks.
    return max(len(tasks), (max_freq - 1) * (n + 1) + max_count)

O(N)

time,

O(1)

extra space. The frequency array has a fixed size of 26.

4. Two-Pass Comparison

Use this when the constraint has two directions and each element must satisfy both neighbors. One pass handles the left direction, the second pass the right direction.

Use this for Candy .

def candy(ratings):
    n = len(ratings)
    candies = [1] * n

    # Left pass: a child rated higher than the neighbor
    # on the left must get more candy than that neighbor.
    for i in range(1, n):
        if ratings[i] > ratings[i - 1]:
            candies[i] = candies[i - 1] + 1

    # Right pass: do the same from the right. The max
    # keeps the left-pass constraint intact.
    for i in range(n - 2, -1, -1):
        if ratings[i] > ratings[i + 1]:
            candies[i] = max(candies[i], candies[i + 1] + 1)

    return sum(candies)

O(N)

time,

O(N)

space. The candy counts array is the only allocation.

Each variation above is a separate review card in the app. Drill them individually so you do not mix up the conditions under pressure.

Now head to the practice problems to apply these templates to real interview questions.

Now that you have the templates, the next step is application. Head to the practice problems or start reviewing these templates with spaced repetition .