Data Structures

This plan is about picking the right container for the job. Prefix sums and difference arrays answer range questions without looping, heaps keep the smallest item ready, and union-find tracks which elements belong together.

The 13 chapters open with common enumeration tricks, then work through prefix sums, difference arrays, stacks, queues and deques, heaps, tries, union-find, Fenwick and segment trees, and finish with splay trees, square root decomposition, offline algorithms and other advanced structures. It is the largest plan on Track 1, so take it a chapter at a time.

366 problemsRating 1161–311213 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.

0. Common Enumeration Techniques

§0.1 Enumerate Right, Maintain Left

Problem	Rating
1. Two Sum	1161
1512. Number of Good Pairs	1161
2441. Largest Positive Integer That Exists with Its Negative	1168
2016. Maximum Difference Between Increasing Elements	1246
624. Maximum Distance in Arrays	1246
2342. Max Sum of a Pair with Equal Sum of Digits	1309
1128. Number of Equivalent Domino Pairs Description	1333
1679. Max Number of K Sum Pairs	1346
219. Contains Duplicate II	1365
2260. Minimum Consecutive Cards to Pick Up	1365
2001. Number of Pairs of Interchangeable Rectangles	1436
2815. Max Pair Sum in an Array	1436
3623. Count Number of Trapezoids I	1580
2364. Count Number of Bad Pairs	1622
3371. Identify the Largest Outlier in an Array	1644
3761. Minimum Absolute Distance Between Mirror Pairs	1669
1014. Best Sightseeing Pair	1730
1814. Count Nice Pairs in an Array	1738
3584. Maximum Product of First AND Last Elements of a Subsequence	1763
2905. Find Indices with Index AND Value Difference II	1764

§0.1.2 Advanced

Problem	Rating
1010. Pairs of Songs with Total Durations Divisible by 60	1787
3185. Count Pairs That Form a Complete Day II	1787
2748. Number of Beautiful Pairs	1787
2506. Count Pairs of Similar Strings	1787
1497. Check If Array Pairs Are Divisible by K	1787
2555. Maximize Win From Two Segments	2081
3267. Count Almost Equal Pairs II	2545
3480. Maximize Subarrays After Removing One Conflicting Pair	2764

§0.2 Enumerate Middle

Problem	Rating
3128. Right Triangles	1541
447. Number of Boomerangs	1583
456. 132 Pattern	1583
3067. Count Pairs of Connectable Servers in a Weighted Tree Network	1909
1534. Count Good Triplets	1909
3455. Shortest Matching Substring	2303
2867. Count Valid Paths in a Tree	2428

§0.3 Diagonal Traversal

Problem	Rating
3446. Sort Matrix by Diagonals	1373
1329. Sort the Matrix Diagonally	1548
498. Diagonal Traverse	1548

I. Prefix Sums

§1.1 Fundamentals

Problem	Rating
303. Range Sum Query Immutable	1209
3427. Sum of Variable Length Subarrays	1209
2559. Count Vowel Strings in Ranges	1435
3152. Special Array II	1523
3652. Best Time to Buy AND Sell Stock Using Strategy	1557
3361. Shift Distance Between Two Strings	1557

§1.2 Prefix Sums with Hash Tables

Problem	Rating
560. Subarray Sum Equals K	1592
930. Binary Subarrays with Sum	1592
1524. Number of Sub Arrays with Odd Sum	1611
974. Subarray Sums Divisible by K	1676
523. Continuous Subarray Sum	1676
525. Contiguous Array	1697
3755. Find Maximum Balanced XOR Subarray Length	1697
3026. Maximum Good Subarray Sum	1817
1546. Maximum Number of Non Overlapping Subarrays with Sum Equals Target	1855
1124. Longest Well Performing Interval	1908
3728. Stable Subarrays with Equal Boundary AND Interior Sum	1909
2488. Count Subarrays with Median K	1999
1590. Make Sum Divisible by P	2039
2845. Count of Interesting Subarrays	2073
3739. Count Subarrays with Majority Element II	2090
1074. Number of Submatrices That Sum to Target	2189
3714. Longest Balanced Substring II	2202
2025. Maximum Number of Ways to Partition an Array	2218
3729. Count Distinct Subarrays Divisible by K in Sorted Array	2248
2949. Count Beautiful Substrings II	2445

§1.3 Distance Sums

Problem	Rating
1685. Sum of Absolute Differences in a Sorted Array	1496
2615. Sum of Distances	1793
2602. Minimum Operations to Make All Array Elements Equal	1903
2968. Apply Operations to Maximize Frequency Score	2444
1703. Minimum Adjacent Swaps for K Consecutive Ones	2467
3086. Minimum Moves to Pick K Ones	2673

§1.4 Bitmask Prefix Sums

Problem	Rating
1177. Can Make Palindrome From Substring	1848
1371. Find the Longest Substring Containing Vowels in Even Counts	2041
1542. Find Longest Awesome Substring	2222
1915. Number of Wonderful Substrings	2235
2791. Count Paths That Can Form a Palindrome in a Tree	2677

§1.5 Advanced Prefix Sums

Problem	Rating
3709. Design Exam Scores Tracker	1648
1895. Largest Magic Square	1781
2055. Plates Between Candles	1819
1744. Can You Eat Your Favorite Candy on Your Favorite Day	1859
1878. Get Biggest Three Rhombus Sums in a Grid	1898
3756. Concatenate Non Zero Digits AND Multiply by Sum II	1968
2245. Maximum Trailing Zeros in a Cornered Path	2037
1712. Ways to Split Array Into Three Subarrays	2079
1862. Sum of Floored Pairs	2170
3748. Count Stable Subarrays	2209
2281. Sum of Total Strength of Wizards	2621
3445. Maximum Difference Between Even AND Odd Frequency II	2694
2983. Palindrome Rearrangement Queries	2780

§1.6 2D Prefix Sums

Problem	Rating
304. Range Sum Query 2D Immutable	1484
1314. Matrix Block Sum	1484
3070. Count Submatrices with Top Left Element AND Sum Less Than K	1499
1738. Find Kth Largest XOR Coordinate Value	1671
3212. Count Submatrices with Equal Frequency of X AND Y	1673
1292. Maximum Side Length of a Square with Sum Less Than OR Equal to Threshold	1735

II. Difference Arrays

§2.1 1D Difference Array

Problem	Rating
2848. Points That Intersect with Cars	1230
1893. Check If All the Integers in a Range Are Covered	1307
1854. Maximum Population Year	1370
2960. Count Tested Devices After Test Operations	1370
1094. Car Pooling	1441
1109. Corporate Flight Bookings	1570
3355. Zero Array Transformation I	1591
2381. Shifting Letters II	1793
995. Minimum Number of K Consecutive Bit Flips	1835
1589. Maximum Sum Obtained of Any Permutation	1871
1526. Minimum Number of Increments on Subarrays to Form a Target Array	1872
3356. Zero Array Transformation II	1913
1943. Describe the Painting	1969
3224. Minimum Array Changes to Make Differences Equal	1996
2251. Number of Flowers in Full Bloom	2022
2772. Apply Operations to Make All Array Elements Equal to Zero	2029
3229. Minimum Operations to Make Array Equal to Target	2067
3529. Count Cells in Overlapping Horizontal AND Vertical Substrings	2105
798. Smallest Rotation with Highest Score	2130
3347. Maximum Frequency of an Element After Performing Operations II	2156
1674. Minimum Moves to Make Array Complementary	2333
3362. Zero Array Transformation III	2424
3655. XOR After Range Multiplication Queries II	2454
3017. Count the Number of Houses at a Certain Distance II	2709

§2.2 2D Difference Array

Problem	Rating
2536. Increment Submatrices by One	1583
850. Rectangle Area II	2236
2132. Stamping the Grid	2364

III. Stacks

§3.1 Fundamentals

Problem	Rating
1441. Build an Array with Stack Operations	1180
844. Backspace String Compare	1228
682. Baseball Game	1228
2390. Removing Stars From a String	1348
1472. Design Browser History	1454
946. Validate Stack Sequences	1462
3412. Find Mirror Score of a String	1578
71. Simplify Path	1578

§3.2 Advanced

Problem	Rating
3170. Lexicographically Minimum String After Removing Stars	1772
155. Min Stack	1772
1381. Design a Stack with Increment Operation	1772
636. Exclusive Time of Functions	1772
2434. Using a Robot to Print the Lexicographically Smallest String	1953
895. Maximum Frequency Stack	2028
1172. Dinner Plate Stacks	2110
2589. Minimum Time to Complete All Tasks	2381

§3.3 Adjacent Cancellation

Problem	Rating
2696. Minimum String Length After Removing Substrings	1282
1047. Remove All Adjacent Duplicates in String	1286
1544. Make the String Great	1344
3561. Resulting String After Adjacent Removals	1397
1003. Check If Word Is Valid After Substitutions	1427
2216. Minimum Deletions to Make Array Beautiful	1510
1209. Remove All Adjacent Duplicates in String II	1542
3703. Remove K Balanced Substrings	1802
1717. Maximum Score From Removing Substrings	1868
2197. Replace Non Coprime Numbers in Array	2057
735. Asteroid Collision	2057
2751. Robot Collisions	2092

§3.4 Valid Parentheses Strings (RBS)

Problem	Rating
20. Valid Parentheses	1242
921. Minimum Add to Make Parentheses Valid	1242
1021. Remove Outermost Parentheses	1311
1614. Maximum Nesting Depth of the Parentheses	1323
1190. Reverse Substrings Between Each Pair of Parentheses	1486
856. Score of Parentheses	1563
1249. Minimum Remove to Make Valid Parentheses	1657
1963. Minimum Number of Swaps to Make the String Balanced	1689
678. Valid Parenthesis String	1700
1111. Maximum Nesting Depth of Two Valid Parentheses Strings	1749
1541. Minimum Insertions to Balance a Parentheses String	1759
2116. Check If a Parentheses String Can Be Valid	2038

§3.5 Expression Parsing

Problem	Rating
1006. Clumsy Factorial	1408
150. Evaluate Reverse Polish Notation	1408
394. Decode String	1408
8. String to Integer Atoi	1408
224. Basic Calculator	1408
227. Basic Calculator II	1408
726. Number of Atoms	1408
1106. Parsing a Boolean Expression	1880
591. Tag Validator	1880
736. Parse Lisp Expression	1880
1096. Brace Expansion II	2349
65. Valid Number	2532
770. Basic Calculator IV	2863

§3.6 Two Stacks

Problem	Rating
2296. Design a Text Editor	1912

IV. Queues & Deques

§4.1 Fundamentals

Problem	Rating
933. Number of Recent Calls	1338
950. Reveal Cards in Increasing Order	1686
649. Dota2 Senate	1686

§4.2 Data Structure Design

Problem	Rating
1670. Design Front Middle Back Queue	1610
225. Implement Stack Using Queues	1851
232. Implement Queue Using Stacks	1851
622. Design Circular Queue	1851
641. Design Circular Deque	1851

§4.3 Deque

Problem	Rating
2810. Faulty Keyboard	1851

§4.4 Monotonic Queue

Problem	Rating
239. Sliding Window Maximum	1851
1438. Longest Continuous Subarray with Absolute Diff Less Than OR Equal to Limit	1672
2762. Continuous Subarrays	1672
2398. Maximum Number of Robots Within Budget	1917
3589. Count Prime Gap Balanced Subarrays	2235
862. Shortest Subarray with Sum at Least K	2307
1499. Max Value of Equation	2456

V. Heaps & Priority Queues

§5.1 Fundamentals

Problem	Rating
1046. Last Stone Weight	1173
3264. Final Array State After K Multiplication Operations I	1178
2558. Take Gifts From the Richest Pile	1277
2336. Smallest Number in Infinite Set	1375
2530. Maximal Score After Applying K Operations	1386
3066. Minimum Operations to Exceed Threshold Value II	1400
1962. Remove Stones to Minimize the Total	1419
703. Kth Largest Element in a Stream	1419
3275. K Th Nearest Obstacle Queries	1420
1845. Seat Reservation Manager	1429
2208. Minimum Operations to Halve Array Sum	1550
2233. Maximum Product After K Increments	1686
1942. The Number of the Smallest Unoccupied Chair	1695
1801. Number of Orders in the Backlog	1711
2406. Divide Intervals Into Minimum Number of Groups	1713
3478. Choose K Elements with Maximum Sum	1753
2462. Total Cost to Hire K Workers	1764
1834. Single Threaded Cpu	1798
1792. Maximum Average Pass Ratio	1818

§5.2 Advanced

Problem	Rating
23. Merge K Sorted Lists	1818
2931. Maximum Spending After Buying Items	1822
355. Design Twitter	1822
502. Ipo	1822
1705. Maximum Number of Eaten Apples	1930
1882. Process Tasks Using Servers	1979
1354. Construct Target Array with Multiple Sums	2015
1353. Maximum Number of Events That Can Be Attended	2016
632. Smallest Range Covering Elements From K Lists	2023
2542. Maximum Subsequence Score	2056
1383. Maximum Performance of a Team	2091
2402. Meeting Rooms III	2093
2503. Maximum Number of Points From Grid Queries	2196
857. Minimum Cost to Hire K Workers	2260
1606. Find Servers That Handled Most Number of Requests	2276
1851. Minimum Interval to Include Each Query	2286
407. Trapping Rain Water II	2286
2940. Find Building Where Alice AND Bob Can Meet	2327
2589. Minimum Time to Complete All Tasks	2381
3266. Final Array State After K Multiplication Operations II	2509
1675. Minimize Deviation in Array	2533
2532. Time to Cross a Bridge	2589

§5.3 K-th Element

Problem	Rating
264. Ugly Number II	1818
23. Merge K Sorted Lists	1818

§5.4 Rearranging Elements

Problem	Rating
984. String Without Aaa OR Bbb	1474
767. Reorganize String	1681
1054. Distant Barcodes	1702
1405. Longest Happy String	1821
3081. Replace Question Marks in String to Minimize Its Value	1905
621. Task Scheduler	1905

§5.5 Regret Heap

Problem	Rating
630. Course Schedule III	2074
3362. Zero Array Transformation III	2424
2813. Maximum Elegance of a K Length Subsequence	2582
3049. Earliest Second to Mark Indices II	3111

§5.6 Lazy Deletion Heap

Problem	Rating
2349. Design a Number Container System	1540
3607. Power Grid Maintenance	1700
2353. Design a Food Rating System	1782
3092. Most Frequent Ids	1793
3408. Design Task Manager	1807
2034. Stock Price Fluctuation	1832
1172. Dinner Plate Stacks	2110
218. The Skyline Problem	2110
3510. Minimum Pair Removal to Sort Array II	2608

§5.7 Two Heaps (K-th Smallest/Largest in a Window)

Problem	Rating
2102. Sequentially Ordinal Rank Tracker	2159
295. Find Median From Data Stream	2159
480. Sliding Window Median	2159
2653. Sliding Subarray Beauty	2159
1825. Finding Mk Average	2396
3013. Divide an Array Into Subarrays with Minimum Cost II	2540
3321. Find X Sum of All K Long Subarrays II	2598

VI. Trie (Prefix Trees)

§6.1 Fundamentals

Problem	Rating
208. Implement Trie Prefix Tree	1180
3597. Partition String	1180
648. Replace Words	1180
720. Longest Word in Dictionary	1180
2416. Sum of Prefix Scores of Strings	1725
677. Map Sum Pairs	1725
1268. Search Suggestions System	1725
1233. Remove Sub Folders From the Filesystem	1725
820. Short Encoding of Words	1725
2261. K Divisible Elements Subarrays	1725

§6.2 Advanced

Problem	Rating
211. Design Add AND Search Words Data Structure	1725
676. Implement Magic Dictionary	1725
212. Word Search II	1725
3093. Longest Common Suffix Queries	2118
745. Prefix AND Suffix Search	2118
3045. Count Prefix AND Suffix Pairs II	2328
336. Palindrome Pairs	2328
1948. Delete Duplicate Folders in System	2534

§6.3 Trie-Optimized DP

Problem	Rating
140. Word Break II	1725

§6.4 0-1 Trie (XOR Trie)

Problem	Rating
1707. Maximum XOR with an Element From Array	2359
1938. Maximum Genetic Difference Query	2503

VII. Disjoint Set Union (DSU)

§7.1 Fundamentals

Problem	Rating
3493. Properties Graph	1565
990. Satisfiability of Equality Equations	1638
3532. Path Existence Queries in a Graph I	1725

§7.2 Advanced

Problem	Rating
3551. Minimum Swaps to Sort by Digit Sum	1507
2471. Minimum Number of Operations to Sort a Binary Tree by Level	1635
1202. Smallest String with Swaps	1855
1061. Lexicographically Smallest Equivalent String	1855
1722. Minimize Hamming Distance After Swap Operations	1892
3608. Minimum Time for K Connected Components	1893
765. Couples Holding Hands	1999
947. Most Stones Removed with Same Row OR Column	2035
839. Similar String Groups	2054
1970. Last Day Where You Can Still Cross	2124
2076. Process Restricted Friend Requests	2131
959. Regions Cut by Slashes	2136
2503. Maximum Number of Points From Grid Queries	2196
2867. Count Valid Paths in a Tree	2428
2421. Number of Good Paths	2445
2157. Groups of Strings	2499
1632. Rank Transform of a Matrix	2530
803. Bricks Falling When Hit	2765
3235. Check If the Rectangle Corner Is Reachable	2765

§7.3 GCD Union-Find

Problem	Rating
2709. Greatest Common Divisor Traversal	2172
1627. Graph Connectivity with Threshold	2221
952. Largest Component Size by Common Factor	2272
1998. Gcd Sort of an Array	2429
3378. Count Connected Components in Lcm Graph	2532

§7.4 Union-Find on Arrays

Problem	Rating
1562. Find Latest Group of Size M	1928
1488. Avoid Flood in the City	1974
1353. Maximum Number of Events That Can Be Attended	2016
2382. Maximum Segment Sum After Removals	2136
2334. Subarray with Elements Greater Than Varying Threshold	2381

§7.5 Interval Union-Find

Problem	Rating
3244. Shortest Distance After Road Addition Queries II	2270
1851. Minimum Interval to Include Each Query	2286

§7.6 Weighted Union-Find

Problem	Rating
399. Evaluate Division	1725

VIII. Fenwick & Segment Trees

§8.1 Fenwick Tree (Binary Indexed Tree)

Problem	Rating
307. Range Sum Query Mutable	1725
3072. Distribute Elements Into Two Arrays II	2053
3624. Number of Integers with Popcount Depth Equal to K II	2086
3187. Peaks in Array	2154
1649. Create Sorted Array Through Instructions	2208
1409. Queries on a Permutation with Key	2208
2250. Count Number of Rectangles Containing Each Point	2208
2179. Count Good Triplets in an Array	2272
1395. Count Number of Teams	2272
2659. Make Array Empty	2282
2653. Sliding Subarray Beauty	2282
3515. Shortest Path in a Weighted Tree	2312
1505. Minimum Possible Integer After at Most K Adjacent Swaps on Digits	2337
2736. Maximum Sum Queries	2533
3382. Maximum Area Rectangle with Point Constraints II	2723
3590. Kth Smallest Path XOR Sum	2646
3245. Alternating Groups III	3112
3027. Find the Number of Ways to Place People II	2020
60. Permutation Sequence	2020

§8.2 Inversion Pairs

Problem	Rating
315. Count of Smaller Numbers After Self	1725
493. Reverse Pairs	1725
327. Count of Range Sum	1725
2426. Number of Pairs Satisfying Inequality	2030
1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number	2030
2193. Minimum Number of Moves to Make Palindrome	2030

§8.3 Segment Tree (Point Updates)

Problem	Rating
3479. Fruits Into Baskets III	2178
2940. Find Building Where Alice AND Bob Can Meet	2327
2286. Booking Concert Tickets in Groups	2470
3161. Block Placement Queries	2513
2213. Longest Substring of One Repeating Character	2629
3525. Find X Value of Array II	2645
3165. Maximum Sum of Subsequence with Non Adjacent Elements	2697
3501. Maximize Active Section with Trade II	2941

§8.4 Lazy Segment Tree (Range Updates)

Problem	Rating
2569. Handling Sum Queries After Update	2398
1622. Fancy Sequence	2476
2502. Design Memory Allocator	2476
2589. Minimum Time to Complete All Tasks	2381
850. Rectangle Area II	2236
3454. Separate Squares II	2671
3569. Maximize Count of Distinct Primes After Split	2697
3721. Longest Balanced Subarray II	2724

§8.5 Dynamic Segment Tree

Problem	Rating
699. Falling Squares	2286
715. Range Module	2286
729. My Calendar I	2286
731. My Calendar II	2286
732. My Calendar III	2286
2276. Count Integers in Intervals	2222
3590. Kth Smallest Path XOR Sum	2646

§8.6 Persistent Segment Tree

Problem	Rating
3762. Minimum Operations to Equalize Subarrays	2497

§8.7 Sparse Table

Problem	Rating
3501. Maximize Active Section with Trade II	2941

IX. Splay Trees

§9.1 Fundamentals

Problem	Rating
2296. Design a Text Editor	1912

X. Square Root Decomposition (Mo's)

§8.1 Square Root Decomposition

Problem	Rating
3655. XOR After Range Multiplication Queries II	2454

§8.2 Mo's Algorithm

Problem	Rating
3636. Threshold Majority Queries	2451
3590. Kth Smallest Path XOR Sum	2646

§8.3 Miscellaneous

Problem	Rating
3234. Count the Number of Substrings with Dominant Ones	2557

XI. Offline Algorithms

§10.1 Fundamentals

Problem	Rating
2343. Query Kth Smallest Trimmed Number	1652
3607. Power Grid Maintenance	1700
1847. Closest Room	2082
2503. Maximum Number of Points From Grid Queries	2196
1851. Minimum Interval to Include Each Query	2286
2940. Find Building Where Alice AND Bob Can Meet	2327
2747. Count Zero Request Servers	2405
1938. Maximum Genetic Difference Query	2503
2736. Maximum Sum Queries	2533
3590. Kth Smallest Path XOR Sum	2646
3382. Maximum Area Rectangle with Point Constraints II	2723

XII. Advanced Data Structures

Part A

Problem	Rating
2532. Time to Cross a Bridge	2589
2056. Number of Valid Move Combinations on Chessboard	2611

Part B

Problem	Rating
2468. Split Message Based on Limit	2382
68. Text Justification	2382
13. Roman to Integer	1209
12. Integer to Roman	1209
273. Integer to English Words	2382
420. Strong Password Checker	2382
8. String to Integer Atoi	1408
65. Valid Number	2863
146. Lru Cache	2863
460. Lfu Cache	2863

If you set a rating ceiling of 1600 or 1900, harder problems here wait in your challenge list, and your heroine asks before raising the limit.

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

Open the study room