Lessons
Free DSA lessons, level by level
40 concepts explain the idea behind each pattern from scratch. 42 tips are short lessons on spotting and using it, and 19 cover the math interviews rely on. They follow the path, easiest first.
Today's tip for you
“Have I seen this?” is a set
Checking whether you've met a value before? Put values in a set as you go: each check is O(1) instead of a scan.
Picked for your level (Beginner) and where you are on the roadmap · Arrays & Strings
1.Arrays & Strings
On the path →- Indexing and walking through an arrayConceptnums[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 mapConceptA 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?”ConceptA 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 answerConceptCollect 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²).
- “Have I seen this?” is a setTip · BeginnerChecking whether you've met a value before? Put values in a set as you go: each check is O(1) instead of a scan.
- Counting things with a hash mapTip · BeginnerAnagrams, majority element, most frequent: they're all “count each value”. A hash map from value to count does it in one pass.
- Two Sum: look up the partner, don't search for itTip · BeginnerFor each number x, the partner you need is target − x. Store what you've passed in a map and look the partner up in O(1).
- Build strings with a list, then joinTip · BeginnerAdding to a string in a loop can quietly cost O(n²). Collect pieces in a list and join once at the end.
- Prefix sums: any range sum in O(1)Tip · IntermediateStore running totals once. Then the sum of nums[i..j] is prefix[j+1] − prefix[i], no loop needed.
- % for digits, even/odd and wrapping aroundMath · Beginnern % 10 is the last digit, n // 10 drops it. i % len wraps an index back to the start. Three everyday uses of one operator.
- The pigeonhole principleMath · IntermediatePut n + 1 items into n boxes and some box gets two. It's why an array of n+1 numbers from 1..n must contain a duplicate.
2.Two Pointers
On the path →- Two pointers from opposite endsConceptStart 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 wayConceptA 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 patternConceptSorting costs O(n log n) once, but afterwards neighbours are related and two pointers, binary search or a single greedy pass become possible.
- Two pointers from both ends of a sorted arrayTip · BeginnerSorted input and you need a pair? Start at both ends: too small, move left in; too big, move right in. O(n), no extra memory.
- Checking a palindrome with two pointersTip · BeginnerCompare the first and last characters, then step both inward. No reversed copy needed, and skipping junk characters is easy.
3.Sliding Window
On the path →- Fixed-size sliding windowsConceptTo 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 windowsConceptGrow 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 windowConceptKeep 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).
- Fixed-size windows: add one, drop oneTip · BeginnerSumming every window of size k? Don't re-add k numbers each time: add the one entering and subtract the one leaving.
- Variable windows: grow right, shrink leftTip · Intermediate“Longest substring with no repeats”: grow the window on the right, and when it breaks the rule, shrink from the left until it's valid again.
- Sliding window maximum with a dequeTip · AdvancedKeep a deque of indices whose values decrease. The front is always the window's max; pop smaller values from the back as you go.
4.Stack
On the path →- Stacks for matching pairsConceptA 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 elementConceptKeep 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 stackConceptRecursion uses the call stack behind the scenes. Pushing work onto your own stack does the same job without recursion limits.
- Matching brackets with a stackTip · BeginnerPush every opening bracket; on a closing one, the top of the stack must be its partner. Last opened, first closed.
- Monotonic stack: the next greater elementTip · IntermediateKeep a stack of indices still waiting for a bigger value. Each new value pops everyone it beats; that's their answer.
5.Binary Search
On the path →- Binary search in a sorted arrayConceptLook 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 matchConceptWhen 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 answerConceptWhen “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.
- Binary search: halve the search spaceTip · BeginnerOn sorted data, check the middle: it tells you which half the answer can't be in. 1 billion items take about 30 steps.
- Binary search on the answerTip · IntermediateWhen “is speed k enough?” flips from no to yes as k grows, binary search over k itself, even though nothing is sorted.
- Searching a rotated sorted arrayTip · IntermediateAfter rotation, one half around mid is always sorted. Check whether the target lies in that half; if not, it's in the other.
- What log n really meansMath · Beginnerlog₂ n is how many times you can halve n before reaching 1. That's why binary search on a million items takes about 20 steps.
- Rounding up without floats: (a + b − 1) // bMath · Beginner7 bananas at 3 per hour takes 3 hours, not 2.33. Integer ceiling division gets it right without floating-point surprises.
- The safe midpoint: lo + (hi − lo) // 2Math · Intermediate(lo + hi) / 2 can overflow in Java and C++ when both are large. lo + (hi − lo) / 2 gives the same middle and never overflows.
6.Linked List
On the path →- Walking a linked listConceptEach 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 listConceptWalk 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 listConceptMove 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.
- Fast and slow pointersTip · IntermediateMove one pointer 1 step and another 2. In a cycle they must meet; in a straight list the fast one stops at the end, the slow one at the middle.
- Reversing a linked list without losing itTip · IntermediateThree pointers: prev, curr, next. Save next first, flip curr.next to prev, then step forward. Save before you flip.
- Picking at random fairly: reservoir samplingMath · AdvancedDon't know the length? Keep the i-th item with probability 1/i. Every item ends up chosen with exactly 1/n chance, in one pass.
7.Trees
On the path →- Depth-first traversal: preorder, inorder, postorderConceptVisit 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 queueConceptUse 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 treesConceptDepth 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.
- Thinking recursively about treesTip · IntermediateAsk: if my children already had their answers, how do I build mine? Then add the base case for an empty tree.
- BFS level by levelTip · IntermediateUse a queue, and at the start of each round note its size: that many nodes are exactly one level.
- Tries for prefix questionsTip · AdvancedA trie stores words letter by letter in a tree, so “does any word start with app?” takes time proportional to the prefix, not the dictionary.
8.Heap / Priority Queue
On the path →- What a heap keeps on topConceptA 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)ConceptA 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 heapConceptFor 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).
- Top K with a small heapTip · IntermediateFor the k largest, keep a min-heap of size k. Its top is the smallest of your best k, the one to kick out. O(n log k).
9.Backtracking
On the path →- Recursion: the base case and the call stackConceptA 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-chooseConceptBuild 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 workConceptBefore exploring a choice, check whether it can still lead to an answer. Cutting dead branches early is what makes backtracking fast enough.
- Backtracking: choose, explore, un-chooseTip · IntermediateMake a choice, recurse, then undo it before trying the next. That one template generates subsets, permutations and combinations.
- Backtracking without duplicate answersTip · AdvancedSort first, then at each level skip a number equal to the one just tried. Duplicates never get generated in the first place.
10.Graphs
On the path →- Representing graphs: adjacency lists and gridsConceptA 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 DFSConceptDFS 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 setConceptGraphs 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.
- A grid is a graph: counting islands with DFSTip · IntermediateEach cell is a node joined to its 4 neighbours. Every time you find unvisited land, flood it with DFS and count one island.
- Shortest path in a grid is BFSTip · AdvancedIn an unweighted grid or graph, BFS reaches every cell by the fewest steps first. Mark cells visited when you enqueue them.
- Topological sort for dependenciesTip · AdvancedTake courses with no remaining prerequisites first, then unlock what depends on them. If some never unlock, there's a cycle.
- Union-Find: are these connected?Tip · AdvancedGive every node a parent pointer; union joins two groups' roots. With path compression, each operation is nearly O(1).
- Dijkstra: shortest paths with weightsTip · AdvancedAlways expand the closest unfinished node next, using a min-heap of (distance, node). Works for non-negative weights only.
11.Dynamic Programming
On the path →- Memoization: recursion that remembersConceptWrite the natural recursion, then cache each result so repeated calls become lookups. Exponential often becomes linear.
- Defining the DP stateConceptBefore 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 tableConceptStart from the smallest cases and fill the table in an order where everything you need is already there. No recursion, and often less memory.
- Dynamic programming starts with one sentenceTip · AdvancedBefore any code, finish this sentence: “dp[i] is …”. The recurrence, base cases and loop order follow from it.
- Most 1-D DP needs only two variablesTip · AdvancedIf dp[i] only looks back one or two steps, you don't need the whole array: keep two variables and roll them forward.
- 2-D DP: a grid of subproblemsTip · AdvancedFor two strings, dp[i][j] = the answer for the first i chars of one and the first j of the other. Each cell looks left, up and diagonally.
- Memoization: recursion that remembersTip · AdvancedWrite the natural recursion first, then cache each result. Exponential time often drops to polynomial with one decorator.
- Why answers are “mod 10⁹ + 7”Math · IntermediateCounts can grow astronomically, so problems ask for the answer mod 10⁹+7. Take the mod after every + and ×, not just at the end.
- Choosing k of n: nCr and Pascal's triangleMath · IntermediateC(n, k) = n! / (k!(n−k)!) counts ways to choose. Unique Paths on an m×n grid is C(m+n−2, m−1): no DP needed.
- Catalan numbers: 1, 1, 2, 5, 14, 42…Math · AdvancedValid bracket strings, distinct BSTs, polygon triangulations: all Catalan numbers. Spot it and a hard count becomes a formula.
12.Greedy & Intervals
On the path →- Sort first, then decide in one passConceptMany 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 safeConceptGreedy 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 intervalsConceptSort intervals by start. Then each one either overlaps the last merged interval (extend it) or starts a new one.
- Kadane's algorithm: the best subarrayTip · IntermediateAt each number, either extend the run you're on or start fresh from here, whichever is bigger. One pass finds the max subarray.
- Intervals: sort by start, then sweepTip · IntermediateSort intervals by start. Then each one either overlaps the last merged interval (extend it) or starts a new one.
- When is greedy safe?Tip · AdvancedGreedy is right when taking the locally best move can never hurt later. Try to argue that, or find a counterexample, before coding.
13.Bit Manipulation & Math
On the path →- Binary numbers and AND, OR, XORConceptEvery 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 shiftsConceptx << 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 tricksConceptx ^ 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.
- Three bit tricks worth knowingTip · Advancedx ^ x = 0 finds the odd one out, n & (n − 1) drops the lowest 1-bit, and (n >> i) & 1 reads bit i.
- GCD with Euclid's algorithm (and LCM for free)Math · Intermediategcd(a, b) = gcd(b, a % b) until b is 0. It's O(log) fast, and lcm(a, b) = a × b / gcd(a, b).
- Primes: check up to √n, or sieve them allMath · IntermediateIf n has a divisor, one of them is ≤ √n, so checking stops there. For all primes below n, cross out multiples: the Sieve of Eratosthenes.
- Fast power: xⁿ in O(log n)Math · Advancedx¹³ = x⁸ · x⁴ · x¹: square x repeatedly and multiply in the squares where n's binary has a 1. With a mod, it also gives modular inverses.
- Two's complement: how negative numbers live in bitsMath · Advanced−x is ~x + 1, so −1 is all ones. x & −x isolates the lowest set bit. And Python needs a mask to act like 32-bit ints.
Habits & complexity
- What Big O actually measuresTip · BeginnerBig O isn't seconds: it's how the work grows as the input grows. Double n and see what happens to the steps.
- Read the constraints before you codeTip · BeginnerThe input size tells you how fast your solution must be. n ≤ 10⁵ means an O(n²) double loop will time out.
- The five edge cases to always tryTip · BeginnerEmpty, one element, all the same, negatives, and the biggest allowed input. Most wrong answers hide in these five.
- Dry-run your code on paperTip · BeginnerTrace your code line by line on a tiny input, writing every variable down. It finds bugs faster than re-reading.
- Say the brute force firstTip · BeginnerIn an interview, start with the simple slow solution and its Big O. It shows you understand the problem and gives you something to improve.
- Why some “nested loops” are still O(n)Tip · AdvancedCount total work, not loop nesting. If each element enters and leaves a stack or window once, the whole thing is O(n).
- 1 + 2 + … + n = n(n+1)/2Math · BeginnerThis one formula explains why “for j in range(i, n)” inside a loop is O(n²), and it solves Missing Number in one line.
- Powers of two you should know by heartMath · Beginner2¹⁰ ≈ 1 thousand, 2²⁰ ≈ 1 million, 2³⁰ ≈ 1 billion, 2³¹ − 1 is the int limit. They turn constraints into quick decisions.
- 1 + 2 + 4 + … + n < 2nMath · IntermediateDoubling sizes add up to less than twice the last one. That's why dynamic arrays are O(1) per append and a full tree has 2ʰ⁺¹ − 1 nodes.
- Reading recurrences: T(n) = 2T(n/2) + nMath · AdvancedDivide and conquer cost = (number of calls) × (work per call), level by level. Merge sort: log n levels × n work = O(n log n).
- n/1 + n/2 + n/3 + … ≈ n ln nMath · AdvancedLooping over multiples of every i up to n costs n/1 + n/2 + … ≈ n log n, not n². It's why the sieve and “all divisors” loops are fast.
- Inclusion–exclusion: count the overlap onceMath · Advanced|A or B| = |A| + |B| − |A and B|. Numbers ≤ 100 divisible by 2 or 3: 50 + 33 − 16 = 67.