Before the problems
DSA concepts
Every problem page starts with “Know these before you start”. These are those 40 ideas, each explained from scratch: what it is, a worked example, short Python code, what it costs, when you'll use it and the usual mistakes. They follow the roadmap, easiest first. Mark one as known here and it's ticked on the roadmap too.
1.Arrays & Strings
On the roadmap →- Indexing and walking through an arraynums[i] reads any position instantly. A loop from 0 to n − 1 visits every item once: the building block of almost every solution.
- Counting with a hash mapA hash map (dict) stores key → value with O(1) lookups. Use the item as the key and how many times you've seen it as the value.
- A set for “have I seen this?”A set holds unique items and answers “is x in here?” in O(1). Check it before adding as you walk, and duplicates jump out.
- Building a new string or array as the answerCollect pieces in a list and join (or return) it at the end. Strings can't change in place, so adding to one in a loop silently costs O(n²).
2.Two Pointers
On the roadmap →- Two pointers from opposite endsStart one index at each end and move them toward each other. Each step rules something out for good, so one pass is enough.
- Two pointers moving the same wayA fast pointer reads every item; a slow pointer marks where the next kept item goes. Rewrites arrays in place in one pass.
- When sorting first unlocks the patternSorting costs O(n log n) once, but afterwards neighbours are related and two pointers, binary search or a single greedy pass become possible.
3.Sliding Window
On the roadmap →- Fixed-size sliding windowsTo look at every block of k items, don't recompute each one: slide by one, add the item coming in and remove the one going out.
- Variable-size sliding windowsGrow the window on the right every step; whenever it breaks the rule, shrink it from the left until it's valid again. Track the best valid window.
- Tracking what's inside a windowKeep a hash map (or set) of what's in the window, updated as items enter and leave, so checking the window's rule is O(1).
4.Stack
On the roadmap →- Stacks for matching pairsA stack takes and gives back items last-in, first-out. Push each opener; a closer must match the opener on top.
- Monotonic stacks: the next greater elementKeep a stack whose values only decrease. Each new value pops everything smaller: for each popped item, this is its next greater element.
- Replacing recursion with your own stackRecursion uses the call stack behind the scenes. Pushing work onto your own stack does the same job without recursion limits.
5.Binary Search
On the roadmap →- Binary search in a sorted arrayLook at the middle: it tells you which half the target can't be in. Each step halves what's left, so a million items take about 20 steps.
- Binary search for the first or last matchWhen the target appears several times, don't stop at the first hit: remember it and keep searching left (for the first) or right (for the last).
- Binary search on the answerWhen “can it be done with x?” flips from no to yes as x grows, binary search over x itself, even if no array is sorted.
6.Linked List
On the roadmap →- Walking a linked listEach node holds a value and a link to the next. Start at the head and follow .next until None: that's how every list problem moves.
- Reversing a linked listWalk with three pointers (prev, current, next): save next, point current back at prev, then step forward. The old tail becomes the head.
- Fast and slow pointers on a linked listMove one pointer two steps and another one step. When fast reaches the end, slow is in the middle; if there's a loop, they meet inside it.
7.Trees
On the roadmap →- Depth-first traversal: preorder, inorder, postorderVisit a node, its left subtree and its right subtree; the three orders only differ in when you handle the node itself.
- Breadth-first traversal with a queueUse a queue to visit a tree level by level. Read the queue's size at the start of each round: that many nodes are exactly one level.
- Height, depth and binary search treesDepth counts edges down from the root, height counts the longest path down to a leaf. In a BST, everything left is smaller and everything right is bigger.
8.Heap / Priority Queue
On the roadmap →- What a heap keeps on topA heap always knows its smallest item (min-heap) or largest (max-heap), right at the top, without keeping everything sorted.
- Why heap push and pop are O(log n)A new item bubbles up and a removed top is replaced and sifts down, each along one path of a balanced tree: about log₂ n steps.
- Keeping only the k best with a heapFor the k largest, keep a min-heap of size k: whenever it grows past k, pop the smallest. What's left are the k largest. O(n log k).
9.Backtracking
On the roadmap →- Recursion: the base case and the call stackA recursive function solves a problem by calling itself on a smaller version. It needs a base case that stops, and every call waits on the call stack.
- Backtracking: choose, explore, un-chooseBuild answers one decision at a time: make a choice, recurse for the rest, then undo the choice so the next option starts clean.
- Pruning: stop branches that can't workBefore exploring a choice, check whether it can still lead to an answer. Cutting dead branches early is what makes backtracking fast enough.
10.Graphs
On the roadmap →- Representing graphs: adjacency lists and gridsA graph is nodes and edges. Store each node's neighbours in a list (an adjacency list); a grid is a graph where each cell's neighbours are up, down, left, right.
- Graph BFS and DFSDFS goes as deep as it can before backing up (recursion or a stack). BFS spreads out in rings by distance (a queue) and finds shortest paths in unweighted graphs.
- The visited setGraphs can loop back on themselves. Remember every node you've reached in a set and never process one twice, or you'll go round forever.
11.Dynamic Programming
On the roadmap →- Memoization: recursion that remembersWrite the natural recursion, then cache each result so repeated calls become lookups. Exponential often becomes linear.
- Defining the DP stateBefore any code, finish the sentence “dp[i] is …”. The recurrence, base cases and loop order all follow from that sentence.
- Bottom-up DP: filling a tableStart from the smallest cases and fill the table in an order where everything you need is already there. No recursion, and often less memory.
12.Greedy & Intervals
On the roadmap →- Sort first, then decide in one passMany greedy problems become easy after sorting by the right key: then a single left-to-right pass makes each decision once.
- When the locally best choice is safeGreedy is correct when taking the best-looking option now can never block a better final answer. Argue it, or find a counterexample, before coding.
- Merging and overlapping intervalsSort intervals by start. Then each one either overlaps the last merged interval (extend it) or starts a new one.
13.Bit Manipulation & Math
On the roadmap →- Binary numbers and AND, OR, XOREvery integer is a row of bits. AND keeps bits set in both, OR in either, XOR in exactly one: fast tools for flags, masks and tricks.
- Bit shiftsx << 1 moves every bit left: ×2. x >> 1 moves them right: halves and drops the remainder. 1 << i is a number with only bit i set.
- XOR and other bit tricksx ^ x = 0 and x ^ 0 = x, so XOR-ing everything cancels pairs. n & (n − 1) drops the lowest 1-bit. These solve a family of interview problems in O(1) space.