Greedy Coding Problems: 163 Questions with Solutions

How greedy works, step by step

1. reach is the farthest index known to be reachable. It starts at 0, where we stand; every index up to reach can be landed on, and nothing past it is known to be reachable yet.
2. From index 0 a jump of up to 1 lands as far as 1, so reach = 1. Shorter jumps land inside the stretch already covered, which is why only the farthest point matters.
3. Index 1 is within reach, and from it a jump of 3 lands at 4, so reach grows to 4: every index from 0 to 4 is now reachable.
4. nums[2] = 0 goes nowhere, but that is no trap: reach is already 4, so index 3 is still reachable and the scan carries on.
5. nums[3] = 0 adds nothing either, since 3 + 0 = 3 is behind reach = 4; a zero only traps the scan when reach stops at it.
6. From index 4 a jump of 2 lands at 6, the last index, so reach = 6 covers the end and the scan can stop.
7. The end is reachable, so the answer is true: 0 → 1 → 4 → 6 works, using the jumps that pushed reach forward. Had i ever passed reach, it would be false. One pass and one number kept: O(n) time, O(1) space.

Greedy study plan

14 of the 163 Greedy problems (4 easy, 7 medium and 3 hard) over 8 days, about 8 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 149 in the full list below are practice at your own pace. Then move on to Recursion.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.

• Assign Cookies Easy
• Lemonade Change Easy
• Largest Perimeter Triangle Easy

Day 2

Medium problems: the same pattern with one twist each. Name the twist before you code.

• Valid Palindrome II Easy
• Container With Most Water Medium

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

• Capacity To Ship Packages Within D Days Medium
• Jump Game Medium

Day 4

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

• Gas Station Medium
• Partition Labels Medium

Day 5

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

• Task Scheduler Medium
• Non-overlapping Intervals Medium

Day 6

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

• Candy Hard

Day 7

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

• Wildcard Matching Hard

Day 8

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

• Largest Multiple of Three Hard

Next topic: Recursion

Greedy: the essentials

When to reach for it

An optimisation over a sequence of choices with an obvious local rule — the interval that ends earliest, the farthest reachable index, the smallest item that still fits — and an input size (10⁵ or more) that rules out a table over every state. The first line of the solution is usually a sort by the key the rule uses.

The pattern

State the rule, then try to break it before coding: hunt for a small input where the local choice blocks a better total. If you cannot, sketch the exchange argument — take any optimal solution, swap its first choice for the greedy one, and show the result is no worse. The code is then one pass that commits to each choice and never looks back.

def can_jump(nums):
    reach = 0                       # farthest index reachable so far
    for i, step in enumerate(nums):
        if i > reach:
            return False
        reach = max(reach, i + step)
    return True

Cost

Usually O(n log n) for the sort plus O(n) for the pass, with O(1) extra space; rules that keep the best few candidates in a heap stay at O(n log n).

Common mistakes

• Trusting a rule because it passes the examples. Coins {1, 3, 4} making 6: largest-first gives 4 + 1 + 1, but 3 + 3 needs only two coins — that problem is DP.
• Sorting by the wrong key: selecting the most non-overlapping intervals needs end times, not start times or lengths.
• Ties the proof never considered.
• Committing for good to a choice the problem lets you revise; keep the candidates in a heap and swap the worst one out instead.

Start with

• Assign Cookies: sort both sides, match the smallest that fits.
• Jump Game: the farthest reach as the only state.
• Gas Station: a rule that needs its proof to be believed.

All greedy problems

Easy (35)

• Apple Redistribution into Boxes Array, Sorting
• Maximum Difference by Remapping a Digit Math
• Best Poker Hand Array, Hash Table, Counting
• Minimum Moves to Convert String String
• Maximum Height of a Triangle Array, Enumeration, Simulation
• Minimum Amount of Time to Fill Cups Array, Math, Heap
• Take Gifts From the Richest Pile Array, Heap, Simulation
• DI String Match Array, Two Pointers, String
• Split With Minimum Sum Math, Sorting
• Minimum Changes to Make Alternating Binary String String
• Convert Array Into Zig-Zag Fashion Array
• Maximum Sum With Exactly K Elements Array
• Maximum Odd Binary Number String
• Distribute Money to Maximum Children Math
• Furthest Point From Origin String
• Largest Odd Number in String String, Math
• Minimum Sum of Four Digit Number After Splitting Digits Math, Sorting
• Minimum Number of Operations to Convert Time String
• Minimum Operations to Make the Array Increasing Array
• Minimum Subsequence in Non-Increasing Order Array, Sorting
• Partition Array Into Three Parts With Equal Sum Array, Prefix Sum
• Largest Perimeter Triangle Array, Math, Sorting
• Minimum Cost to Move Chips to The Same Position Array, Math
• Maximum Units on a Truck Array, Sorting
• Assign Cookies Array, Two Pointers, Sorting
• Minimum Number of Moves to Seat Everyone Array, Sorting, Counting Sort
• Maximum Product Difference Between Two Pairs Array, Sorting
• Array Partition Array, Sorting, Counting Sort
• Split a String in Balanced Strings String, Counting
• Longest Palindrome Hash Table, String
• Distribute Candies Array, Hash Table
• Can Place Flowers Array
• Maximum 69 Number Math
• Lemonade Change Array
• Valid Palindrome II String, Two Pointers

Medium (106)

• Minimum Number of Increments on Subarrays to Form a Target Array Array, Dynamic Programming, Stack
• Longest Subsequence With Limited Sum Array, Binary Search, Sorting
• Maximum Number of Non-overlapping Palindrome Substrings String, Dynamic Programming
• Delete Characters to Make Fancy String String
• Construct String With Repeat Limit Hash Table, String, Heap (Priority Queue)
• Minimum Number of Changes to Make Binary String Beautiful String
• Lexicographically Minimum String After Removing Stars String, Heap (Priority Queue), Stack
• Determine the Minimum Sum of a k-avoiding Array Array, Math
• Maximum Number of Eaten Apples Array, Heap (Priority Queue)
• Maximum Subsequence Score Array, Sorting, Heap (Priority Queue)
• Maximum Number of Events That Can Be Attended Array, Sorting, Heap (Priority Queue)
• Maximal Score After Applying K Operations Array, Heap (Priority Queue)
• Maximum Score From Removing Stones Math, Heap (Priority Queue)
• Minimum Cost to Connect Sticks Array, Heap (Priority Queue)
• Maximum Star Sum of a Graph Array, Graph, Sorting
• Maximum Matrix Sum Array, Matrix
• Minimum Cost Tree From Leaf Values Array, Dynamic Programming, Stack
• Longest Binary Subsequence Less Than or Equal to K String, Dynamic Programming, Memoization
• Minimum Additions to Make Valid String String, Dynamic Programming, Stack
• Partition String Into Substrings With Values at Most K String, Dynamic Programming
• Stone Game IX Array, Math, Counting
• Minimum Operations to Make Median of Array Equal to K Array, Sorting
• Smallest Missing Non-negative Integer After Operations Array, Hash Table, Math
• Separate Black and White Balls String, Two Pointers
• Find the Maximum Number of Marked Indices Array, Two Pointers, Sorting
• Maximum Split of Positive Even Integers Math
• Maximum Consecutive Floors Without Special Floors Array, Sorting
• Count Collisions on a Road String, Stack, Simulation
• Video Stitching Array, Dynamic Programming, Intervals
• Eliminate Maximum Number of Monsters Array, Sorting
• Removing Minimum and Maximum From Array Array
• Minimum Number of Operations to Move All Balls to Each Box Array, String, Prefix Sum
• Minimum Number of Arrows to Burst Balloons Array, Sorting, Intervals
• Divide Chocolate Array, Binary Search
• House Robber IV Array, Binary Search
• Minimize the Maximum Difference of Pairs Array, Binary Search, Sorting
• Maximum Value at a Given Index in a Bounded Array Binary Search, Math
• Magnetic Force Between Two Balls Array, Binary Search, Sorting
• Frequency of the Most Frequent Element Array, Sliding Window, Sorting
• Most Profit Assigning Work Array, Two Pointers, Sorting
• Partition Array Such That Maximum Difference Is K Array, Sorting, Two Pointers
• Bag of Tokens Array, Two Pointers, Sorting
• Maximum OR Bit Manipulation, Array, Prefix Sum
• Minimum Array End Bit Manipulation
• Minimize XOR Bit Manipulation
• Minimum Time to Repair Cars Array, Binary Search
• Minimum Moves to Reach Target Score Math
• Integer Replacement Bit Manipulation, Dynamic Programming
• Minimum Operations to Reduce an Integer to 0 Bit Manipulation, Dynamic Programming
• Maximum Product After K Increments Array, Heap
• Prime Subtraction Operation Array, Math, Number Theory
• Minimum Number of Operations to Make Array Empty Hash Table, Counting
• Group the People Given the Group Size They Belong To Hash Table, Array
• Optimal Partition of String Hash Table, String
• Maximum Number of Integers to Choose From a Range I Hash Table, Binary Search
• Can Convert String in K Moves String, Hash Table
• Minimum Number of Frogs Croaking String, Counting
• Check If a String Can Break Another String String, Sorting
• Divide Array Into Arrays With Max Difference Array, Sorting
• Find Original Array From Doubled Array Array, Sorting, Hash Table
• Non-decreasing Array Array
• Maximum Total Importance of Roads Graph, Sorting, Heap
• Minimum Insertions to Balance a Parentheses String String, Stack
• The Number of Weak Characters in the Game Array, Sorting, Stack
• Maximum Score From Removing Substrings String, Stack
• Minimum Number of Swaps to Make the String Balanced String, Stack, Two Pointers
• Max Chunks To Make Sorted Array, Stack, Monotonic Stack
• Dota2 Senate String, Queue
• Minimum Add to Make Parentheses Valid String, Stack
• Minimum Number of Platforms Array, Sorting, Two Pointers
• Partition Array into Disjoint Intervals Array
• Minimum Time to Make Rope Colorful Array, String, Dynamic Programming
• Remove Duplicate Letters String, Stack, Monotonic Stack
• Monotone Increasing Digits Math
• Maximum Swap Math
• Valid Triangle Number Array, Two Pointers, Binary Search
• Maximum Number of Coins You Can Get Array, Math, Sorting
• Largest Number Array, String, Sorting
• Maximum Ice Cream Bars Array, Sorting, Counting Sort
• Remove Covered Intervals Array, Sorting
• Minimum Deletions to Make Character Frequencies Unique String, Hash Table, Sorting
• Reduce Array Size to The Half Array, Hash Table, Sorting
• Queue Reconstruction by Height Array, Sorting, Binary Indexed Tree
• Two City Scheduling Array, Sorting
• Maximum Length of Pair Chain Array, Dynamic Programming, Sorting
• Wiggle Subsequence Array, Dynamic Programming
• Best Time to Buy and Sell Stock with Transaction Fee Array, Dynamic Programming
• Max Increase to Keep City Skyline Array, Matrix
• Valid Parenthesis String String, Dynamic Programming, Stack
• Increasing Triplet Subsequence Array
• Integer to Roman Hash Table, Math, String
• Minimum Number of Arrows to Burst Balloons Array, Sorting, Intervals
• Non-overlapping Intervals Array, Sorting, Intervals
• Furthest Building You Can Reach Array, Heap
• Least Number of Unique Integers after K Removals Array, Heap, Hash Table
• Task Scheduler Array, Heap, Counting
• Partition Labels String, Hash Table, Two Pointers
• Boats to Save People Array, Two Pointers, Sorting
• Best Time to Buy and Sell Stock II Array, Dynamic Programming
• Hand of Straights Array, Hash Table, Sorting
• Gas Station Array
• Jump Game II Array, Dynamic Programming
• Jump Game Array, Dynamic Programming
• Remove K Digits String, Stack, Monotonic Stack
• Capacity To Ship Packages Within D Days Array, Binary Search
• Container With Most Water Array, Two Pointers

Hard (22)

• Minimum Replacements to Sort the Array Array, Math
• Special Binary String String, Recursion, Divide and Conquer
• Smallest K-Length Subsequence With Occurrences of a Letter String, Stack, Monotonic Stack
• Apply Operations to Maximize Score Array, Math, Stack
• Smallest Range Covering Elements from K Lists Array, Hash Table, Sliding Window
• Minimize Deviation in Array Array, Heap (Priority Queue), Ordered Set
• Maximum Performance of a Team Array, Sorting, Heap (Priority Queue)
• Put Marbles in Bags Array, Sorting, Heap (Priority Queue)
• Maximum Number of Groups With Increasing Length Array, Sorting, Binary Search
• Minimum Time to Complete All Tasks Array, Sorting
• Minimum Number of Refueling Stops Array, Dynamic Programming, Heap
• IPO Array, Sorting, Heap
• Minimum Number of Taps to Open to Water a Garden Array, Dynamic Programming, Intervals
• Maximum Number of Tasks You Can Assign Array, Binary Search, Sorting
• Maximum Running Time of N Computers Array, Binary Search, Sorting
• Split Array Largest Sum Array, Binary Search, Dynamic Programming
• Minimum Number of Flips to Make the Binary String Alternating String, Sliding Window, Dynamic Programming
• Minimum Number of K Consecutive Bit Flips Array, Sliding Window, Prefix Sum
• Minimum Number of Moves to Make Palindrome String, Two Pointers
• Largest Multiple of Three Array, Dynamic Programming, Math
• Wildcard Matching String, Dynamic Programming
• Candy Array

Companies that ask greedy problems

• Amazon 144 problems on greedy
• Google 108 problems on greedy
• Adobe 32 problems on greedy
• Microsoft 24 problems on greedy
• Meta 14 problems on greedy
• Flipkart 12 problems on greedy
• Zoho 8 problems on greedy
• TCS 6 problems on greedy
• Bloomberg 5 problems on greedy
• Uber 5 problems on greedy
• Infosys 4 problems on greedy
• Cognizant 3 problems on greedy

Other topics

• Arrays 667 problems
• Strings 282 problems
• Math 213 problems
• Hash Table 202 problems
• Dynamic Programming 195 problems
• Sorting 156 problems
• Two Pointers 113 problems
• Matrix 107 problems
• Binary Search 95 problems
• Simulation 88 problems
• Bit Manipulation 83 problems
• Sliding Window 71 problems