Work-In-Progress
1) standardize variable naming and coding style before migrating more code.
2) improve topic naming, question categorization, and question tags.
3) introduce more high-level topics (expand System Design).
Designed to facililate retrieval, review, and recall of algorithmic techniques.
C++ Standard Library ⓘ
Questions where the solution can be reduced to simply using C++ containers or functions to do the heavy-lifting.
Move Zeroesstd::removegrind169 | leetcodetop152 | leetcode75Remove Elementstd::removeleetcode150Remove Duplicates from Sorted Arraystd::uniqueleetcodetop152 | leetcode150Remove Duplicates from Sorted Array IIstd::uniqueleetcode150Merge Sorted Arraystd::inplace_mergeleetcodetop152 | leetcode150Find Peak Elementstd::adjacent_findleetcodetop152 | leetcode75 | leetcode150Kth Largest Element in an Arraystd::nth_elementneetcode150 | grind169 | leetcodetop152 | leetcode75 | leetcode150Rotate Arraystd::rotategrind169 | leetcodetop152 | leetcode150Next Permutationstd::next_permutationgrind169Greatest Common Divisor of Stringsstd::gcdleetcode75
Data Structures ⓘ
Non-trivial usage of data structures.
Longest Palindromegrind169Contains DuplicateArrays & Hashingneetcode150 | grind169 | leetcodetop152Valid AnagramArrays & Hashingneetcode150 | grind169 | leetcodetop152 | leetcode150Two SumScan Hashneetcode150 | grind169 | leetcodetop152 | leetcode150Ransom Notegrind169 | leetcode150Find the Difference of Two Arraysleetcode75Unique Number of Occurrencesleetcode75Determine if Two Strings Are Closeleetcode75Equal Row and Column Pairsleetcode75Max Number of K-Sum PairsScan Hashleetcode75Smallest Number in Infinite Setleetcode75Insert Delete GetRandom O(1)%Randomgrind169 | leetcodetop152 | leetcode150Valid SudokuBitsetneetcode150 | grind169 | leetcodetop152 | leetcode150Longest Consecutive SequenceUnordered Setneetcode150 | grind169 | leetcodetop152 | leetcode150Copy List with Random Pointer%Linked Listneetcode150 | leetcodetop152 | leetcode150First Missing Positivegrind169 | leetcodetop152Number of Orders in the Backlog
Valid Parenthesesneetcode150 | grind169 | leetcodetop152 | leetcode150Minimum Remove to Make Valid ParenthesesLongest Valid Parenthesesgrind169Implement Queue using Stacksgrind169Removing Stars From a Stringleetcode75Min Stackneetcode150 | grind169 | leetcodetop152 | leetcode150Evaluate Reverse Polish Notationneetcode150 | grind169 | leetcodetop152 | leetcode150Decode Stringgrind169 | leetcode75Asteroid Collisiongrind169 | leetcode75Flatten Nested List IteratorFlatMapleetcodetop152Basic Calculator IIIteration | Stackgrind169 | leetcodetop152Basic CalculatorIteration | Stackgrind169 | leetcode150
Number of Recent Callsleetcode75Dota2 Senateleetcode75
Maximum Subsequence Scoreleetcode75Total Cost to Hire K Workersleetcode75Last Stone Weightneetcode150Task Schedulerneetcode150 | grind169 | leetcodetop152Design Twitterneetcode150Kth Largest Element in a Stream%Streamneetcode150Find Median from Data Stream%Streamneetcode150 | grind169 | leetcodetop152 | leetcode150Merge k Sorted Lists%Mergeneetcode150 | grind169 | leetcodetop152 | leetcode150IPOleetcode150Smallest Range Covering Elements from K Lists%Merge | Sliding Window Variable Lengthgrind169The Skyline Problemleetcodetop152Course Schedule IIITrapping Rain Water IIMinimum Number of Refueling StopsDP
Implement Trie (Prefix Tree)Trieneetcode150 | grind169 | leetcodetop152 | leetcode75 | leetcode150Design Add and Search Words Data StructureTrie | N-ary Tree Backtracking | DFSneetcode150 | grind169 | leetcode150Palindrome PairsTrie | Prefix | Suffixgrind169Prefix and Suffix SearchTrie | Prefix | Suffix
LRU Cacheneetcode150 | grind169 | leetcodetop152 | leetcode150LFU CacheBucketAll O`one Data StructureBucketMaximum Frequency StackBucketgrind169Range Sum Query - MutableFenwick Tree | Segment Tree
Position Tracking ⓘ
Cumulative Scans
2 Pointers, 3 Pointers, Shrinking Window, Sliding Window,
scanr is scanning from right, and not right-associate scan (as in haskell's)
think of it as r = reverse, instead of, r =
scans uses its previous result and an element of an array,
producing intermediate values that are used (not necessarily saved).
saved intermediate values are stored after that separately (eg. dictionary)
Kids With the Greatest Number of Candiesleetcode75Can Place Flowersleetcode75Find the Highest AltitudePrefix Sumleetcode75Maximum SubarrayKadaneneetcode150 | grind169 | leetcodetop152 | leetcode150Maximum Product SubarrayTwo Scans | Kadaneneetcode150 | grind169 | leetcodetop152Gas StationKadaneneetcode150 | grind169 | leetcodetop152 | leetcode150Contiguous ArrayMemo Umap | Scangrind169Find Pivot IndexPrefix Sumleetcode75Subarray Sum Equals KMemo Umap | Scan | Prefix Sumgrind169Product of Array Except SelfTwo Scansneetcode150 | grind169 | leetcodetop152 | leetcode75 | leetcode150Valid Parenthesis StringTwo Scansneetcode150
Maximum Average Subarray Ileetcode75Maximum Number of Vowels in a Substring of Given Lengthleetcode75Max Consecutive Ones IIIleetcode75Longest Subarray of 1's After Deleting One Elementleetcode75Jump GameTwo Pointers | Sliding Window Seek Aheadneetcode150 | grind169 | leetcodetop152 | leetcode150Jump Game IIThree Pointers | Sliding Window Seek Aheadneetcode150 | leetcode150Partition LabelsThree Pointers | Sliding Window Seek Aheadneetcode150Permutation in StringTwo Pointers | Sliding Window Fixed Lengthneetcode150Find All Anagrams in a StringTwo Pointers | Sliding Window Fixed Lengthgrind169Longest Substring Without Repeating CharactersTwo Pointers | Sliding Window Seek Behindneetcode150 | grind169 | leetcodetop152 | leetcode150Longest Repeating Character ReplacementTwo Pointers | Sliding Window Seek Behindneetcode150 | grind169Reverse Words in a StringThree Pointers | Sliding Window Seek Behindleetcode75 | leetcode150String CompressionThree Pointers | Sliding Window Seek Behindleetcode75Minimum Window SubstringTwo Pointers | Sliding Window Seek Behindneetcode150 | grind169 | leetcodetop152 | leetcode150Substring with Concatenation of All WordsMultiple Sliding Windowsleetcode150
Linked List Cycle%Linked List | Two Pointers Slow Fast | Floyd | Cycle Detectionneetcode150 | grind169 | leetcodetop152 | leetcode150Linked List Cycle II%Linked List | Two Pointers Slow Fast | Floyd | Cycle DetectionMiddle of the Linked List%Linked List | Two Pointers Slow Fastgrind169Delete the Middle Node of a Linked List%Linked List | Two Pointers Slow Fastleetcode75Palindrome Linked List%Linked List | Two Pointers Slow Fastgrind169 | leetcodetop152Reorder List%Linked List | Two Pointers Slow Fastneetcode150 | grind169Remove Nth Node From End of List%Linked List | Two Pointers Slow Fastneetcode150 | grind169 | leetcodetop152 | leetcode150Find the Duplicate NumberTwo Pointers Slow Fastneetcode150 | grind169 | leetcodetop152
Daily TemperaturesMonotonic Stackneetcode150 | grind169 | leetcode75Online Stock SpanMonotonic Stackleetcode75Remove Duplicate LettersMonotonic Stack | GreedyCar FleetMonotonic Stackneetcode150Largest Rectangle in HistogramMonotonic Stack | Segment Treeneetcode150 | grind169 | leetcodetop152Number of Visible People in a QueueMonotonic StackSliding Window MaximumMonotonic Dequeneetcode150 | grind169 | leetcodetop152
Longest Common Prefixgrind169 | leetcodetop152 | leetcode150Majority ElementBoyer Mooregrind169 | leetcodetop152 | leetcode150K Closest Points to Originneetcode150 | grind169Top K Frequent Wordsgrind169Hand of Straightsneetcode150Top K Frequent ElementsHash Count | Partial Sortneetcode150 | leetcodetop152Group AnagramsHash Index | Full Sortneetcode150 | grind169 | leetcodetop152 | leetcode150Largest NumberCustom Sort Comparatorgrind169 | leetcodetop152Search Suggestions SystemBinary Search Shrinking Windowleetcode75Median of Two Sorted Arraysneetcode150 | grind169 | leetcodetop152 | leetcode150
Insert Interval%Intervalsneetcode150 | grind169 | leetcode150Merge Intervals%Intervalsneetcode150 | grind169 | leetcodetop152 | leetcode75 | leetcode150Non-overlapping Intervals%Intervalsneetcode150 | grind169 | leetcode75Minimum Number of Arrows to Burst Balloons%Intervalsleetcode75 | leetcode150Minimum Interval to Include Each Query%Intervals | Heap | Binary Searchneetcode150
Guess Number Higher or Lowerleetcode75Successful Pairs of Spells and Potionsleetcode75Binary Searchneetcode150 | grind169Search Insert Positionleetcode150First Bad Versiongrind169 | leetcodetop152Find Minimum in Rotated Sorted Arrayneetcode150 | grind169 | leetcode150Find Minimum in Rotated Sorted Array IISearch in Rotated Sorted Arrayneetcode150 | grind169 | leetcodetop152 | leetcode150Find K Closest Elementsgrind169Search a 2D Matrixneetcode150 | grind169 | leetcode150Koko Eating Bananasstd::ranges::iota_viewneetcode150 | leetcode75Time Based Key-Value Storeneetcode150 | grind169
Is SubsequenceSubsequenceleetcode75 | leetcode150Increasing Triplet SubsequenceSubsequenceleetcodetop152 | leetcode75
Node Traversal ⓘ
Linked List, Binary Tree, N-ary Tree, Square Grid
Can the number of visits be determined up-front?
Linked List: Head Recursion
Tail Recursion
Binary Tree: Breadth First Search
Depth First Search PreOrder
Depth First Search InOrder
Depth First Search PostOrder
N-ary Tree : Depth First Search Branch Local
Grid : Breadth First Search
Depth First Search
Other Trees: Segment Tree
Interval Tree
Binary Indexed Tree
Range Tree
Merge Two Sorted Lists%Linked List | Head Recursionneetcode150 | grind169 | leetcodetop152 | leetcode150Reverse Linked List%Linked List | Tail Recursionneetcode150 | grind169 | leetcodetop152 | leetcode75Maximum Twin Sum of a Linked List%Linked List | Tail Recursionleetcode75Add Two Numbersneetcode150 | grind169 | leetcodetop152 | leetcode150Swap Nodes in Pairsgrind169Odd Even Linked Listgrind169 | leetcodetop152 | leetcode75Sort Listgrind169 | leetcodetop152 | leetcode150Rotate Listgrind169 | leetcode150Reverse Nodes in k-Groupneetcode150 | grind169 | leetcode150
Invert Binary TreeBFS | DFSneetcode150 | grind169 | leetcode150Maximum Depth of Binary TreeBFS | DFSneetcode150 | grind169 | leetcodetop152 | leetcode75 | leetcode150Diameter of Binary TreeDFSneetcode150 | grind169Balanced Binary TreeDFSneetcode150 | grind169Same TreeDFSneetcode150 | grind169 | leetcode150Subtree of Another TreeDFSneetcode150 | grind169Symmetric TreeDFSgrind169 | leetcodetop152 | leetcode150Leaf-Similar TreesBFS | DFSleetcode75Construct Binary Tree from Preorder and Inorder TraversalBinary Tree | DFS PreOrderneetcode150 | grind169 | leetcodetop152 | leetcode150Construct Binary Tree from Inorder and Postorder Traversalleetcode150Construct Binary Tree from Preorder and Postorder TraversalSerialize and Deserialize Binary TreeBinary Tree | DFS PreOrder | BFSneetcode150 | grind169 | leetcodetop152Flatten Binary Tree to Linked ListDFS PostOrderleetcode150Binary Tree Level Order TraversalBFS | DFSneetcode150 | grind169 | leetcodetop152 | leetcode150Maximum Width of Binary TreeBFSgrind169Binary Tree Right Side ViewBFSneetcode150 | grind169 | leetcode75 | leetcode150Maximum Level Sum of a Binary TreeBFS | DFSleetcode75Binary Tree Zigzag Level Order TraversalBFSgrind169 | leetcodetop152 | leetcode150Count Good Nodes in Binary TreeDFSneetcode150 | leetcode75Longest ZigZag Path in a Binary TreeDFSleetcode75Kth Smallest Element in a BSTDFS InOrderneetcode150 | grind169 | leetcodetop152 | leetcode150All Nodes Distance K in Binary TreeBFS | DFSgrind169Path Sum IIBFS | DFSgrind169Path Sum IIIDFSgrind169 | leetcode75Binary Tree Maximum Path SumDFS PostOrderneetcode150 | grind169 | leetcodetop152 | leetcode150Lowest Common Ancestor of a Binary TreeDFS PostOrdergrind169 | leetcodetop152 | leetcode75 | leetcode150
Convert Sorted Array to Binary Search TreeBinary Tree | DFS PreOrdergrind169 | leetcodetop152 | leetcode150Search in a Binary Search TreeBSTleetcode75Delete Node in a BSTBSTleetcode75Lowest Common Ancestor of a Binary Search TreeBSTneetcode150 | grind169Validate Binary Search TreeBSTneetcode150 | grind169 | leetcodetop152 | leetcode150
Flood Fillgrind16901 MatrixDPgrind169Number of IslandsDFS Gridneetcode150 | grind169 | leetcodetop152 | leetcode150Max Area of IslandDFS Gridneetcode150Pacific Atlantic Water Flowneetcode150 | grind169Surrounded RegionsDFS Gridneetcode150 | leetcodetop152 | leetcode150Nearest Exit from Entrance in MazeBFSleetcode75Rotting OrangesBFSneetcode150 | grind169 | leetcode75Word SearchDFS Gridneetcode150 | grind169 | leetcodetop152 | leetcode150Word Search IITrie | Backtracking Gridneetcode150 | grind169 | leetcodetop152 | leetcode150Swim in Rising WaterPriority Queue | Binary Search | DFS | BFS | Union Findneetcode150
Word LadderBFSneetcode150 | grind169 | leetcodetop152 | leetcode150
CombinationsCombinatoricsleetcode150Combination SumCombinatoricsneetcode150 | grind169 | leetcode150Combination Sum IICombinatoricsneetcode150Combination Sum IIICombinatoricsleetcode75Combination Sum IVCombinatorics | DPgrind169PermutationsCombinatoricsneetcode150 | grind169 | leetcodetop152 | leetcode150Permutations IICombinatoricsSubsetsCombinatoricsneetcode150 | grind169 | leetcodetop152Subsets IICombinatoricsneetcode150Palindrome PartitioningCombinatoricsneetcode150 | leetcodetop152Letter Combinations of a Phone NumberBFS | DFSneetcode150 | grind169 | leetcodetop152 | leetcode75 | leetcode150
Redundant ConnectionUnion Findneetcode150Accounts MergeUnion Findgrind169Number of ProvincesUnion Findleetcodetop152Evaluate DivisionUnion Findleetcode75 | leetcode150Maximum Number of Non-Overlapping SubstringsStrongly Connected ComponentsCritical Connections in a NetworkBridges and Articulation Points
Min Cost to Connect All Pointsneetcode150Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
Cheapest Flights Within K StopsSingle Source Shortest Pathneetcode150 | grind169Network Delay Timeneetcode150Find the City With the Smallest Number of Neighbors at a Threshold DistanceAll Pairs Shortest PathBus RoutesMulti Source Shortest Pathgrind169
Is Graph Bipartite?Bipartite GraphPossible BipartitionBipartite GraphMaximum Students Taking ExamMin Cut Max Flow | Bit Manipulation
Reconstruct ItineraryEuler Pathneetcode150
Clone Graphneetcode150 | grind169 | leetcode150
Dynamic Programming ⓘ
optimal substructure, overlapping subproblems
Fibonacci
Knapsack
Pathfinding
Position
y-axis definition
x-axis definition
base case
general case
recurrence relationship / finite state machine / choices
memoization
subarrays
subsequences
bottom-up:
// optimal substructure: build up result starting after base cases,
// overlapping subproblem: caching only relevant results for future processing.
top-down:
// overlapping subproblem: return base case or cached result if available,
// optimal substructure: otherwise calculate and cache result, before returning.
// check conditions in order: out-of-bounds, cached, base cases, general case.
Best Time to Buy and Sell StockScan | Stock Boundedneetcode150 | grind169 | leetcodetop152 | leetcode150Best Time to Buy and Sell Stock IIIScan Parallel | Stock Boundedleetcode150Best Time to Buy and Sell Stock IVScan Parallel | Stock Boundedleetcode150Best Time to Buy and Sell Stock IIStock Unboundedleetcodetop152 | leetcode150Best Time to Buy and Sell Stock with Transaction FeeStock Unboundedleetcode75Best Time to Buy and Sell Stock with CooldownStock Unboundedneetcode150 | leetcodetop152
Single Numberneetcode150 | grind169 | leetcodetop152 | leetcode75 | leetcode150Number of 1 Bitsneetcode150 | grind169 | leetcodetop152 | leetcode150Counting Bitsneetcode150 | grind169 | leetcode75Reverse Bitsneetcode150 | grind169 | leetcodetop152 | leetcode150Missing Numberneetcode150 | grind169 | leetcodetop152Minimum Flips to Make a OR b Equal to cleetcode75Sum of Two Integersneetcode150 | leetcodetop152Reverse Integerneetcode150 | grind169 | leetcodetop152Add Binarygrind169 | leetcode150
Meeting Roomsneetcode150 | grind169Meeting Rooms IIneetcode150 | grind169 | leetcodetop152Employee Free Timegrind169Encode and Decode Stringsneetcode150 | grind169Shortest Path to Get Foodgrind169Graph Valid Treeneetcode150 | grind169Number of Connected Components in an Undirected Graphneetcode150 | grind169Minimum Knight Movesgrind169Alien Dictionaryneetcode150 | grind169 | leetcodetop152Inorder Successor in BSTgrind169 | leetcodetop152Design In-Memory File Systemgrind169Design Hit Countergrind169Walls And Gatesneetcode150Missing Rangesleetcodetop152Flatten 2D Vectorleetcodetop152Design Tic-Tac-Toeleetcodetop152Find the Celebrityleetcodetop152Longest Substring with At Most K Distinct Charactersleetcodetop152Range Sum Query 2D - Mutableleetcodetop152
Intersection of Two Arrays IIleetcodetop152Reverse Stringleetcodetop152First Unique Character in a Stringleetcodetop152Find the Index of the First Occurrence in a Stringleetcodetop152 | leetcode150Delete Node in a Linked Listleetcodetop152Shuffle an Arrayleetcodetop152Fizz Buzzleetcodetop152Count Primesleetcodetop152Power of Threeleetcodetop152Hamming Distanceleetcodetop152Pascal's Triangleleetcodetop152Count and Sayleetcodetop152Intersection of Two Linked Listsleetcodetop152Binary Tree Inorder Traversalleetcodetop152Populating Next Right Pointers in Each Nodeleetcodetop152Find First and Last Position of Element in Sorted Arrayleetcodetop152 | leetcode150Search a 2D Matrix IIleetcodetop152Factorial Trailing Zeroesleetcodetop152 | leetcode150Excel Sheet Column Numberleetcodetop152Sqrt(x)leetcodetop152 | leetcode150Divide Two Integersleetcodetop152Fraction to Recurring Decimalleetcodetop1524Sum IIleetcodetop152Game of Lifeleetcodetop152 | leetcode150Count of Smaller Numbers After Selfleetcodetop152Remove Invalid Parenthesesleetcodetop152Wiggle Sort IIleetcodetop152Kth Smallest Element in a Sorted Matrixleetcodetop152Max Points on a Lineleetcodetop152 | leetcode150Queue Reconstruction by Heightleetcodetop152
H-Indexleetcode150Candyleetcode150Integer to Romanleetcode150Length of Last Wordleetcode150Zigzag Conversionleetcode150Text Justificationleetcode150Minimum Size Subarray Sumleetcode150Isomorphic Stringsleetcode150Word Patternleetcode150Contains Duplicate IIleetcode150Summary Rangesleetcode150Simplify Pathleetcode150Reverse Linked List IIleetcode150Remove Duplicates from Sorted List IIleetcode150Partition Listleetcode150Populating Next Right Pointers in Each Node IIleetcode150Path Sumleetcode150Sum Root to Leaf Numbersleetcode150Binary Search Tree Iteratorleetcode150Count Complete Tree Nodesleetcode150Average of Levels in Binary Treeleetcode150Minimum Absolute Difference in BSTleetcode150Snakes and Laddersleetcode150Minimum Genetic Mutationleetcode150Construct Quad Treeleetcode150Maximum Sum Circular Subarrayleetcode150Find K Pairs with Smallest Sumsleetcode150Single Number IIleetcode150Bitwise AND of Numbers Rangeleetcode150Triangleleetcode150
Distributed Systems ⓘ
NUS CS5223 Distributed Systems Lab.
Solutions run on the backend and are not made publicly available.
Important concepts to understand (why it matters, what useful properties):
- Exactly-Once
- Idempotency
- Monotonicity
- Linearizability
- Consensus
- Quorum
Important protocols to design, implement, and optimize for (latency, throughput, fairness):
- Asynchronous Replication
- Synchronous Failover
- Leader Election
- Multi-Paxos
- Shard Reconfigurations
- Two-Phase Commit
Part II of the book "Designing Data-Intensive Applications" can provide a starting foundation.