Greedy Coding Problems: 264 Questions with Solutions
264 greedy coding problems — 43 easy · 174 medium · 47 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 8-day plan.
- Problems: 264
- By difficulty: 43 easy · 174 medium · 47 hard
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
- Cost: Free on every plan; sign in to run and submit
A greedy algorithm makes the locally best choice at each step and never revisits it. It is fast and simple when it is right — scheduling by earliest finish, jumping as far as possible, taking the largest coin — and quietly wrong when it is not. The problems here practise both halves: spotting the exchange argument that proves the greedy choice safe, and recognising the cases where only dynamic programming or search will do.
New to greedy? Read the Greedy Algorithms tutorial first.
How greedy works, step by step
nums = [1, 3, 0, 0, 2, 0, 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.
- 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.
- 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.
- 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.
- 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.
- From index 4 a jump of 2 lands at 6, the last index, so reach = 6 covers the end and the scan can stop.
- 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 264 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 250 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.
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 (43)
- Make Array Zero by Subtracting Equal Amounts Array, Hash Table, Sorting
- Maximize Sum Of Array After K Negations Array, Sorting
- Remove Digit From Number to Maximize Result String, Enumeration
- Minimum Time to Type Word Using Special Typewriter String
- Latest Time by Replacing Hidden Digits String
- Minimum Cost of Buying Candies With Discount Array, Sorting
- Two Furthest Houses With Different Colors Array
- Remove One Element to Make the Array Strictly Increasing Array
- 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 (174)
- Design an ATM Machine Array, Design
- Maximum Number of Non-Overlapping Subarrays With Sum Equals Target Array, Hash Table, Prefix Sum
- Minimum Seconds to Equalize a Circular Array Array, Hash Table
- Minimum Operations to Make the Array Alternating Array, Hash Table, Counting
- Construct K Palindrome Strings Hash Table, String, Counting
- Rabbits in Forest Array, Hash Table, Math
- Minimum Spanning Tree Graph, Union Find, Minimum Spanning Tree
- Maximum Frequency After Subarray Operation Array, Hash Table, Dynamic Programming
- Largest Submatrix With Rearrangements Array, Sorting, Matrix
- Minimum Swaps to Arrange a Binary Grid Array, Matrix
- Minimum Sideway Jumps Array, Dynamic Programming
- Stone Game VI Array, Sorting, Game Theory
- Minimize Maximum Pair Sum in Array Array, Two Pointers, Sorting
- Maximum Strength of a Group Array, Sorting, Enumeration
- Minimum Cost to Make All Characters Equal String, Dynamic Programming
- Maximum Number of Weeks for Which You Can Work Array
- Delete Columns to Make Sorted II Array, String
- Score After Flipping Matrix Array, Bit Manipulation, Matrix
- Broken Calculator Math
- Construct the Longest New String Math, Brainteaser
- Minimum Cost to Make Array Equalindromic Array, Math, Sorting
- Minimum Number of Groups to Create a Valid Assignment Array, Hash Table
- Maximum Matching of Players With Trainers Array, Two Pointers, Sorting
- Maximum Element After Decreasing and Rearranging Array, Sorting
- Minimum Number of Coins to be Added Array, Sorting
- Divide Intervals Into Minimum Number of Groups Array, Sorting, Heap (Priority Queue)
- Remove Stones to Minimize the Total Array, Heap (Priority Queue)
- Check if a Parentheses String Can Be Valid String, Stack
- Find the Most Competitive Subsequence Array, Stack, Monotonic Stack
- Largest Number After Mutating Substring Array, String
- Minimum Sum of Squared Difference Array, Binary Search, Sorting
- Earliest Second to Mark Indices I Array, Binary Search
- Maximum Tastiness of Candy Basket Array, Binary Search, Sorting
- Minimized Maximum of Products Distributed to Any Store Array, Binary Search
- Maximum Sum Obtained of Any Permutation Array, Sorting, Prefix Sum
- Maximum Length of Subarray With Positive Product Array, Dynamic Programming
- Maximum Xor Product Math, Bit Manipulation
- Minimum Non-Zero Product of the Array Elements Math, Recursion
- Maximum Number of Consecutive Values You Can Make Array, Sorting
- Find the Minimum Number of Fibonacci Numbers Whose Sum Is K Math
- Smallest Range II Array, Math, Sorting
- Lexicographically Smallest String After Substring Operation String
- Append Characters to String to Make Subsequence Two Pointers, String
- Using a Robot to Print the Lexicographically Smallest String Hash Table, String, Stack
- Largest Palindromic Number Hash Table, String, Counting
- Construct Smallest Number From DI String String, Stack, Backtracking
- Maximize Number of Subsequences in a String String, Prefix Sum
- Longest Palindrome by Concatenating Two Letter Words Array, Hash Table, String
- Remove Colored Pieces if Both Neighbors are the Same Color Math, String, Game Theory
- Maximum Value after Insertion String
- Minimum Number of Swaps to Make the Binary String Alternating String, Counting
- Largest Merge Of Two Strings Two Pointers, String
- Maximum Binary String After Change String
- Smallest String With A Given Numeric Value String
- Minimum Suffix Flips String
- Break a Palindrome String
- Maximize Greatness of an Array Array, Two Pointers, Sorting
- Rearrange Array to Maximize Prefix Score Array, Sorting, Prefix Sum
- Minimize Maximum of Array Array, Binary Search, Prefix Sum
- Maximum Number of Groups Entering a Competition Array, Math, Binary Search
- Maximum Bags With Full Capacity of Rocks Array, Sorting
- Minimum Rounds to Complete All Tasks Array, Hash Table, Counting
- Minimum Elements to Add to Form a Given Sum Array
- Decrease Elements To Make Array Zigzag Array
- Minimum Domino Rotations For Equal Row Array
- Previous Permutation With One Swap Array
- Array of Doubled Pairs Array, Hash Table, Sorting
- Minimum Increment to Make Array Unique Array, Sorting, Counting
- 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 (47)
- Binary Tree Cameras Tree, Depth-First Search, Dynamic Programming
- Stamping the Grid Array, Matrix, Prefix Sum
- Longest Chunked Palindrome Decomposition Two Pointers, String, Dynamic Programming
- Minimum Number of Removals to Make Mountain Array Array, Binary Search, Dynamic Programming
- Remove Max Number of Edges to Keep Graph Fully Traversable Graph, Union Find
- Pizza With 3n Slices Array, Dynamic Programming, Heap (Priority Queue)
- Minimum Operations to Form Subsequence With Target Sum Array, Bit Manipulation
- Rearranging Fruits Array, Hash Table, Sorting
- Minimum Number of Operations to Make Arrays Similar Array, Sorting
- Minimum Initial Energy to Finish Tasks Array, Sorting
- Couples Holding Hands Union Find, Graph
- Create Maximum Number Array, Stack, Monotonic Stack
- Patching Array Array
- Set Intersection Size At Least Two Array, Sorting
- Minimum Amount of Damage Dealt to Bob Array, Sorting
- Maximum Spending After Buying Items Array, Sorting, Heap (Priority Queue)
- Earliest Possible Day of Full Bloom Array, Sorting
- Course Schedule III Array, Sorting, Heap (Priority Queue)
- Max Chunks To Make Sorted II Array, Stack, Monotonic Stack
- Minimum Operations to Make a Subsequence Array, Hash Table, Binary Search
- Minimum Cost to Make Array Equal Array, Binary Search, Sorting
- Maximize the Minimum Powered City Array, Binary Search, Prefix Sum
- Apply Operations on Array to Maximize Sum of Squares Array, Hash Table, Bit Manipulation
- Find the String with LCP String, Dynamic Programming, Matrix
- Lexicographically Smallest Beautiful String String
- 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 242 problems on greedy
- Google 190 problems on greedy
- Microsoft 43 problems on greedy
- Adobe 34 problems on greedy
- Meta 17 problems on greedy
- Flipkart 14 problems on greedy
- Uber 8 problems on greedy
- Zoho 8 problems on greedy
- Rubrik 6 problems on greedy
- TCS 6 problems on greedy
- Arcesium 5 problems on greedy
- Bloomberg 5 problems on greedy
Next topic: Recursion