Greedy Pattern: LeetCode Guide & Problems

Make the locally optimal choice at each step to achieve a globally optimal solution.

✓ Pattern Solutions & Guides Practice Mode Enabled

8 Problem 0 Easy 7 Medium 1 Hard

Overview

Greedy algorithms work when a locally optimal choice leads to a globally optimal solution. They are typically O(n log n) due to sorting, and proving correctness often requires an exchange argument.

When to Use

Jump game
Gas station
Meeting rooms
Task scheduler
Assign cookies
Minimum number of platforms

Common Mistakes

Applying greedy when it does not guarantee optimality
Forgetting to sort the input
Not proving the greedy choice property

Complexity

Time

O(n log n) — dominated by sorting

Space

O(1)

// Jump Game II — greedy
public int jump(int[] nums) {
    int jumps = 0, currentEnd = 0, farthest = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]);
        if (i == currentEnd) {
            jumps++;
            currentEnd = farthest;
        }
    }
    return jumps;
}

Problems (8)

Hide completed

Problem	Difficulty	Companies	Freq	Solution	Link
Jump Game #Array #Greedy #DP	Medium	AmazonMicrosoft +1	High	Solution
Jump Game II #Array #Greedy #DP	Medium	AmazonGoogle +1	High	Solution
Gas Station #Array #Greedy	Medium	AmazonUber +1	Medium	Solution
Non-overlapping Intervals #Array #Greedy #Dynamic Programming	Medium	GoogleFacebook	High	Solution
Meeting Rooms II ★ #Array #Greedy #Sorting	Medium	FacebookAmazon +4	High	Solution	★
Queue Reconstruction by Height #Array #Greedy #Sorting	Medium	GoogleFacebook	Medium	Solution
Minimum Number of Arrows to Burst Balloons #Array #Greedy #Sorting	Medium	MicrosoftAmazon	Medium	Solution
Candy #Array #Greedy	Hard	AmazonGoogle	Medium	Solution

🧠

Mastering the Greedy Pattern for Coding Interviews

1. Mental Model & Visual Intuition

The Greedy pattern is designed to eliminate redundant work and reduce search spaces. Rather than evaluating every possible state using a naive brute-force approach, this pattern relies on an invariant that allows you to safely discard subproblems that cannot lead to an optimal answer. When encountering an interview question, look for core triggers such as monotonicity, contiguous constraints, optimal substructure, or overlapping subproblems.

2. Algorithmic Invariants & Step-by-Step Execution

To implement this pattern flawlessly under interview conditions, structure your thought process into three discrete steps:

State Initialization: Define your boundaries, pointers, or memoization tables clearly before entering loops.
State Transition: Update tracking variables incrementally as new elements enter or leave your active evaluation window.
Feasibility Check: When constraints are violated, systematically shrink or adjust your state until the valid invariant is restored.

3. Time and Space Complexity Trade-Offs

In top-tier technical interviews at Google, Meta, and Amazon, arriving at a working solution is only half the battle. You must explicitly justify why your approach achieves optimal Big-O bounds. For Greedy, the target time complexity is typically O(n log n) — dominated by sorting while maintaining an auxiliary space complexity of O(1). Always discuss whether an in-place modification or two-pass traversal can save memory.

4. Common Interview Edge Cases to Test

Before informing your interviewer that you have completed coding, trace your logic against these standard high-failure test cases:

Empty inputs, single-element collections, or all-identical values.
Inputs with negative numbers, duplicates, or extreme values that could cause integer overflow.
Odd versus even length inputs when dealing with pointer convergence or tree midpoints.

Master greedy algorithms for interviews: intuition, exchange argument proofs, interval scheduling, a…