Greedy Algorithms

A greedy algorithm makes the best-looking choice at each step and never goes back on it. The real work is convincing yourself that the local choice is safe, which is why greedy problems are quick to code and hard to trust.

The eight chapters cover general greedy strategies, interval scheduling, greedy on strings, greedy on numbers, constructive problems and brainteasers, construction problems, interactive problems, and a mixed set. It suits people who handle medium array problems and want to get better at seeing why a greedy choice holds.

254 problemsRating 1148–30778 Chapters

Open the study room

Want company while you work through this list? Sign in, open the study room, and your heroine will bring you the problems one at a time.

I. Greedy Strategies

§1.1 Greedy from Extrema

Problem	Rating
3074. Apple Redistribution Into Boxes	1198
3545. Minimum Deletions for at Most K Distinct Characters	1211
2279. Maximum Bags with Full Capacity of Rocks	1249
1833. Maximum Ice Cream Bars	1253
1005. Maximize Sum of Array After K Negations	1275
1481. Least Number of Unique Integers After K Removals	1284
1403. Minimum Subsequence in Non Increasing Order	1288
3010. Divide an Array Into Subarrays with Minimum Cost I	1292
1338. Reduce Array Size to the Half	1303
1710. Maximum Units on a Truck	1310
3075. Maximize Happiness of Selected Children	1326
2554. Maximum Number of Integers to Choose From a Range I	1333
2126. Destroying Asteroids	1335
2587. Rearrange Array to Maximize Prefix Score	1337
976. Largest Perimeter Triangle	1341
1561. Maximum Number of Coins You Can Get	1406
3627. Maximum Median Sum of Subsequences of Size 3	1561
3462. Maximum Sum with at Most K Elements	1416
2099. Find Subsequence of Length K with the Largest Sum	1447
3301. Maximize the Total Height of Unique Towers	1448
945. Minimum Increment to Make Array Unique	1448
1846. Maximum Element After Decreasing AND Rearranging	1454
3727. Maximum Alternating Sum of Squares	1455
1647. Minimum Deletions to Make Character Frequencies Unique	1510
2971. Find Polygon with the Largest Perimeter	1521
2178. Maximum Split of Positive Even Integers	1538
1578. Minimum Time to Make Rope Colorful	1574
2567. Minimum Score by Changing Two Elements	1609
1509. Minimum Difference Between Largest AND Smallest Value in Three Moves	1653
3397. Maximum Number of Distinct Elements After Operations	1687
3457. Eat Pizzas	1704
948. Bag of Tokens	1762
1775. Equal Sum Arrays with Minimum Number of Operations	1850
3440. Reschedule Meetings for Maximum Free Time II	1998
2333. Minimum Sum of Squared Difference	2011
3645. Maximum Total From Optimal Activation Order	2019

§1.2 Single Sequence Pairing

Problem	Rating
2144. Minimum Cost of Buying Candies with Discount	1261
561. Array Partition	1300
1877. Minimize Maximum Pair Sum in Array	1301
881. Boats to Save People	1530
2592. Maximize Greatness of an Array	1569

§1.3 Two-Sequence Pairing

Problem	Rating
2037. Minimum Number of Moves to Seat Everyone	1357
455. Assign Cookies	1381
2410. Maximum Matching of Players with Trainers	1381
1433. Check If a String Can Break Another String	1436
870. Advantage Shuffle	1648
826. Most Profit Assigning Work	1709
2449. Minimum Number of Operations to Make Arrays Similar	2076
1889. Minimum Space Wasted From Packaging	2214
2561. Rearranging Fruits	2222

§1.4 Greedy from the Left or Right End

Problem	Rating
3402. Minimum Operations to Make Columns Strictly Increasing	1246
3191. Minimum Operations to Make Binary Array Elements Equal to One I	1312
1827. Minimum Operations to Make the Array Increasing	1315
2027. Minimum Moves to Convert String	1346
605. Can Place Flowers	1400
3111. Minimum Rectangles to Cover Points	1401
2957. Remove Adjacent Almost Equal Characters	1430
3192. Minimum Operations to Make Binary Array Elements Equal to One II	1433
1529. Minimum Suffix Flips	Unrated
2789. Largest Element in an Array After Merge Operations	1485
3576. Transform Array to All Equal Elements	1489
1144. Decrease Elements to Make Array Zigzag	1559
3228. Maximum Number of Operations to Move Ones to the End	1593
2086. Minimum Number of Food Buckets to Feed the Hamsters	1623
1536. Minimum Swaps to Arrange a Binary Grid	1881
2673. Make Costs of Paths Equal in a Binary Tree	1917
861. Score After Flipping Matrix	2000
955. Delete Columns to Make Sorted II	2000
2366. Minimum Replacements to Sort the Array	2060

§1.5 Partition Greedy

Problem	Rating
1221. Split a String in Balanced Strings	1220
2405. Optimal Partition of String	1355
2294. Partition Array Such That Maximum Difference Is K	1416
2358. Maximum Number of Groups Entering a Competition	1503
2522. Partition String Into Substrings with Values at Most K	1605
3557. Find Maximum Number of Non Intersecting Substrings	1720

§1.6 Enumerate First, Then Greedy

Problem	Rating
2171. Removing Minimum Number of Magic Beans	1748
3085. Minimum Deletions to Make String K Special	1765
1727. Largest Submatrix with Rearrangements	1927
2910. Minimum Number of Groups to Create a Valid Assignment	2132
2234. Maximum Total Beauty of the Gardens	2562

§1.7 Exchange Argument

Problem	Rating
2895. Minimum Processing Time	1352
3457. Eat Pizzas	1704
1665. Minimum Initial Energy to Finish Tasks	1901
3273. Minimum Amount of Damage Dealt to Bob	2013
2136. Earliest Possible Day of Full Bloom	2033
2561. Rearranging Fruits	2222

§1.8 Keeping Neighbors Different

Problem	Rating
2335. Minimum Amount of Time to Fill Cups	1360
3659. Partition Array Into K Distinct Groups	1440
1753. Maximum Score From Removing Stones	1488
2856. Minimum Array Length After Pair Removals	1750
1953. Maximum Number of Weeks for Which You Can Work	1804
3664. Two Letter Card Game	2158
3495. Minimum Operations to Make Array Elements Zero	2206
3139. Minimum Cost to Equalize Array	2666

II. Interval Scheduling

§2.1 Disjoint Intervals

Problem	Rating
435. Non Overlapping Intervals	1700
646. Maximum Length of Pair Chain	Unrated
1520. Maximum Number of Non Overlapping Substrings	2363
3458. Select K Disjoint Special Substrings	Unrated

§2.3 Choosing Points to Stab Intervals

Problem	Rating
452. Minimum Number of Arrows to Burst Balloons	1700
757. Set Intersection Size at Least Two	2379

§2.4 Interval Covering

Problem	Rating
45. Jump Game II	1700
1024. Video Stitching	1746
1326. Minimum Number of Taps to Open to Water a Garden	1885

§2.5 Merging Intervals

Problem	Rating
56. Merge Intervals	Unrated
57. Insert Interval	Unrated
55. Jump Game	Unrated
763. Partition Labels	1443
3169. Count Days Without Meetings	1483
2580. Count Ways to Group Overlapping Ranges	1632
3394. Check If Grid Can Be Cut Into Sections	1916

§2.6 Other Interval Greedy

Problem	Rating
1288. Remove Covered Intervals	Unrated

III. String Greedy

§3.1 Lexicographically Extrema

Problem	Rating
1323. Maximum 69 Number	1194
3216. Lexicographically Smallest String After a Swap	1243
2697. Lexicographically Smallest Palindrome	1304
3517. Smallest Palindromic Rearrangement I	1357
1881. Maximum Value After Insertion	1381
2734. Lexicographically Smallest String After Substring Operation	1405
1432. Max Difference You Can Get From Changing an Integer	1427
1946. Largest Number After Mutating Substring	1445
1663. Smallest String with a Given Numeric Value	1461
1328. Break a Palindrome	1474
2259. Remove Digit From Number to Maximize Result	Unrated
2566. Maximum Difference by Remapping a Digit	Unrated
670. Maximum Swap	Unrated
3106. Lexicographically Smallest String After Operations with Constraint	1515
3723. Maximize Sum of Squares of Digits	1537
1053. Previous Permutation with One Swap	1633
2375. Construct Smallest Number From Di String	1642
2182. Construct String with Repeat Limit	1680
738. Monotone Increasing Digits	1700
3403. Find the Lexicographically Largest String From the Box I	1762
1754. Largest Merge of Two Strings	1829
2948. Make Lexicographically Smallest Array by Swapping Elements	2047
3474. Lexicographically Smallest Generated String	2605

§3.2 Palindrome Greedy

Problem	Rating
409. Longest Palindrome	1250
2697. Lexicographically Smallest Palindrome	1304
3517. Smallest Palindromic Rearrangement I	1357
680. Valid Palindrome II	1400
1328. Break a Palindrome	1474
1400. Construct K Palindrome Strings	1530
2131. Longest Palindrome by Concatenating Two Letter Words	1557
2384. Largest Palindromic Number	1636
3035. Maximum Palindromes After Operations	1857
1616. Split Two Strings to Make Palindrome	1868
1147. Longest Chunked Palindrome Decomposition	1912
3734. Lexicographically Smallest Palindromic Permutation Greater Than Target	2330

IV. Mathematical Greedy

§4.1 Fundamentals

Problem	Rating
2160. Minimum Sum of Four Digit Number After Splitting Digits	1314
2578. Split with Minimum Sum	1351
2244. Minimum Rounds to Complete All Tasks	1372
2870. Minimum Number of Operations to Make Array Empty	1392
1217. Minimum Cost to Move Chips to the Same Position	1408

§4.2 Product Greedy

Problem	Rating
628. Maximum Product of Three Numbers	Unrated
3732. Maximum Product of Three Elements After One Replacement	1529

§4.3 Rearrangement Inequality

Problem	Rating
2285. Maximum Total Importance of Roads	1496
3016. Minimum Number of Pushes to Type Word II	1534
1402. Reducing Dishes	1679

§4.4 AM-GM Inequality

Problem	Rating
1969. Minimum Non Zero Product of the Array Elements	1967
3723. Maximize Sum of Squares of Digits	1537

§4.5 Median Greedy

Problem	Rating
462. Minimum Moves to Equal Array Elements II	Unrated
2033. Minimum Operations to Make a Uni Value Grid	1672
2448. Minimum Cost to Make Array Equal	2005

§4.6 Proof by Induction

Problem	Rating
2952. Minimum Number of Coins to Be Added	1784
330. Patching Array	Unrated
1798. Maximum Number of Consecutive Values You Can Make	1931

§4.7 Other Math Greedy

Problem	Rating
3107. Minimum Operations to Make Median of Array Equal to K	1605
754. Reach a Number	2000

V. Constructive & Brainteasers

§5.1 Special to General Case

Problem	Rating
2745. Construct the Longest New String	1607
2611. Mice AND Cheese	1663
1029. Two City Scheduling	Unrated
2645. Minimum Additions to Make Valid String	Unrated
2202. Maximize the Topmost Element After K Moves	1717
1702. Maximum Binary String After Change	1825
2350. Shortest Impossible Sequence of Rolls	1961
3660. Jump Game IX	2187
517. Super Washing Machines	Unrated
2499. Minimum Total Cost to Make Arrays Unequal	2633
3357. Minimize the Maximum Adjacent Element Difference	3077

§5.2 Brainteasers

Problem	Rating
2733. Neither Minimum Nor Maximum	1148
3432. Count Partitions with Even Sum Difference	1200
1903. Largest Odd Number in String	1249
2549. Count Distinct Numbers on Board	1266
1689. Partitioning Into Minimum Number of Deci Binary Numbers	1355
3674. Minimum Operations to Equalize Array	1369
3689. Maximum Total Subarray Value I	1371
598. Range Addition II	1400
521. Longest Uncommon Subsequence I	1400
3675. Minimum Operations to Transform String	1414
3638. Maximum Balanced Shipments	1463
3702. Longest Subsequence with Non Zero Bitwise XOR	1489
3424. Minimum Cost to Make Arrays Identical	1503
1992. Find All Groups of Farmland	1539
1007. Minimum Domino Rotations for Equal Row	1541
2811. Check If It Is Possible to Split Array	1543
463. Island Perimeter	Unrated
2211. Count Collisions on a Road	1581
3207. Maximum Points After Enemy Battles	1591
3471. Find the Largest Almost Missing Integer	Unrated
1503. Last Moment Before All Ants Fall Out of a Plank	1619
2860. Happy Students	1626
1332. Remove Palindromic Subsequences	1629
1975. Maximum Matrix Sum	1648
1145. Binary Tree Coloring Game	1741
1297. Maximum Number of Occurrences of a Substring	1748
3577. Count the Number of Computer Unlocking Permutations	1750
3282. Reach End of Array with Max Score	1772
2712. Minimum Cost to Make All Characters Equal	1791
2311. Longest Binary Subsequence Less Than OR Equal to K	1840
2332. The Latest Time to Catch a Bus	1841
2731. Movement of Robots	1923
2556. Disconnect Path in a Binary Matrix by at Most One Flip	2369

§5.3 Thinking in Reverse

Problem	Rating
2139. Minimum Moves to Reach Target Score	1417
869. Reordered Power of 2	1505
554. Brick Wall	1700
780. Reaching Points	1897
417. Pacific Atlantic Water Flow	1900
2227. Encrypt AND Decrypt Strings	1945
3614. Process String with Special Operations II	Unrated
3609. Minimum Moves to Reach Target in Grid	2419
936. Stamping the Sequence	2583

§5.4 Equivalent Reformulation

Problem	Rating
453. Minimum Moves to Equal Array Elements	Unrated
3375. Minimum Operations to Make Array Values Equal to K	1383
2914. Minimum Number of Changes to Make Binary String Beautiful	1480
3365. Rearrange K Substrings to Form Target String	1514
1657. Determine If Two Strings Are Close	1530
2551. Put Marbles in Bags	2042
1585. Check If String Is Transformable with Substring Sort Operations	2333
1040. Moving Stones Until Consecutive II	2456
49. Group Anagrams	Unrated

VI. Construction Problems

§6.1 Construction Problems

Problem	Rating
1304. Find N Unique Integers Sum Up to Zero	1167
942. Di String Match	1444
1253. Reconstruct a 2 Row Binary Matrix	1506
3513. Number of Unique XOR Triplets I	1663
2182. Construct String with Repeat Limit	1680
969. Pancake Sorting	Unrated
1605. Find Valid Matrix Given Row AND Column Sums	1868
2375. Construct Smallest Number From Di String	Unrated
324. Wiggle Sort II	Unrated
667. Beautiful Arrangement II	Unrated
2122. Recover the Original Array	2159
932. Beautiful Array	Unrated
3311. Construct 2D Grid Matching Graph Layout	2664
2573. Find the String with LCP	2682
1982. Find Array Given Subset Sums	2872
1980. Find Unique Binary String	Unrated

VII. Interactive Problems

Problem	Rating
1237. Find Positive Integer Solution for a Given Equation	Unrated
843. Guess the Word	2078

VIII. Miscellaneous Greedy

Problem	Rating
2740. Find the Value of the Partition	1302
1033. Moving Stones Until Consecutive	1421
3523. Make Array Non Decreasing	1435
781. Rabbits in Forest	1453
3587. Minimum Adjacent Swaps to Alternate Parity	1548
1864. Minimum Number of Swaps to Make the Binary String Alternating	1601
1899. Merge Triplets to Form Target Triplet	1636
2498. Frog Jump II	1759
3724. Minimum Operations to Transform Array	1790
134. Gas Station	Unrated
3635. Earliest Finish Time for Land AND Water Rides II	1870
3002. Maximum Size of a Set After Removals	1917
1733. Minimum Number of People to Teach	1984
659. Split Array Into Consecutive Subsequences	Unrated
2790. Maximum Number of Groups with Increasing Length	2620
782. Transform to Chessboard	Unrated

The route places this plan between Bit Manipulation and Mathematics, and you can tick off single chapters or sections here if you have already covered them.

Ratings come from zerotrac's LeetCode contest ratings. Some problems have no zerotrac rating and are marked Unrated.

Open the study room