Learn a little every day

DSA tips

42 short lessons, each a few minutes: the idea in plain words, a worked example, code, how to spot it in a problem, the usual mistakes, and problems to practise it on. The daily tip notification picks the next one for your level and where you are on the roadmap.

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

Beginner

Arrays, hash maps, first patterns and good habits

What Big O actually measuresHabits & complexityBig O isn't seconds: it's how the work grows as the input grows. Double n and see what happens to the steps.
“Have I seen this?” is a setArrays & StringsChecking 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 mapArrays & StringsAnagrams, 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 itArrays & StringsFor 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 joinArrays & StringsAdding to a string in a loop can quietly cost O(n²). Collect pieces in a list and join once at the end.
Read the constraints before you codeHabits & complexityThe 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 tryHabits & complexityEmpty, one element, all the same, negatives, and the biggest allowed input. Most wrong answers hide in these five.
Dry-run your code on paperHabits & complexityTrace your code line by line on a tiny input, writing every variable down. It finds bugs faster than re-reading.
Two pointers from both ends of a sorted arrayTwo PointersSorted 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 pointersTwo PointersCompare the first and last characters, then step both inward. No reversed copy needed, and skipping junk characters is easy.
Fixed-size windows: add one, drop oneSliding WindowSumming every window of size k? Don't re-add k numbers each time: add the one entering and subtract the one leaving.
Matching brackets with a stackStackPush every opening bracket; on a closing one, the top of the stack must be its partner. Last opened, first closed.
Say the brute force firstHabits & complexityIn an interview, start with the simple slow solution and its Big O. It shows you understand the problem and gives you something to improve.
Binary search: halve the search spaceBinary SearchOn sorted data, check the middle: it tells you which half the answer can't be in. 1 billion items take about 30 steps.

Intermediate

Windows, binary search, stacks, lists, trees and heaps

Variable windows: grow right, shrink leftSliding Window“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.
Binary search on the answerBinary SearchWhen “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 arrayBinary SearchAfter rotation, one half around mid is always sorted. Check whether the target lies in that half; if not, it's in the other.
Prefix sums: any range sum in O(1)Arrays & StringsStore running totals once. Then the sum of nums[i..j] is prefix[j+1] − prefix[i], no loop needed.
Monotonic stack: the next greater elementStackKeep a stack of indices still waiting for a bigger value. Each new value pops everyone it beats; that's their answer.
Fast and slow pointersLinked ListMove 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 itLinked ListThree pointers: prev, curr, next. Save next first, flip curr.next to prev, then step forward. Save before you flip.
Thinking recursively about treesTreesAsk: if my children already had their answers, how do I build mine? Then add the base case for an empty tree.
BFS level by levelTreesUse a queue, and at the start of each round note its size: that many nodes are exactly one level.
Top K with a small heapHeap / Priority QueueFor 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).
Kadane's algorithm: the best subarrayGreedy & IntervalsAt 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 sweepGreedy & IntervalsSort intervals by start. Then each one either overlaps the last merged interval (extend it) or starts a new one.
Backtracking: choose, explore, un-chooseBacktrackingMake a choice, recurse, then undo it before trying the next. That one template generates subsets, permutations and combinations.
A grid is a graph: counting islands with DFSGraphsEach cell is a node joined to its 4 neighbours. Every time you find unvisited land, flood it with DFS and count one island.

Advanced

Dynamic programming, graphs and the harder tricks

Dynamic programming starts with one sentenceDynamic ProgrammingBefore 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 variablesDynamic ProgrammingIf 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 subproblemsDynamic ProgrammingFor 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 remembersDynamic ProgrammingWrite the natural recursion first, then cache each result. Exponential time often drops to polynomial with one decorator.
Shortest path in a grid is BFSGraphsIn an unweighted grid or graph, BFS reaches every cell by the fewest steps first. Mark cells visited when you enqueue them.
Topological sort for dependenciesGraphsTake 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?GraphsGive every node a parent pointer; union joins two groups' roots. With path compression, each operation is nearly O(1).
Dijkstra: shortest paths with weightsGraphsAlways expand the closest unfinished node next, using a min-heap of (distance, node). Works for non-negative weights only.
Backtracking without duplicate answersBacktrackingSort first, then at each level skip a number equal to the one just tried. Duplicates never get generated in the first place.
Three bit tricks worth knowingBit Manipulation & Mathx ^ x = 0 finds the odd one out, n & (n − 1) drops the lowest 1-bit, and (n >> i) & 1 reads bit i.
Tries for prefix questionsTreesA 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.
Sliding window maximum with a dequeSliding WindowKeep a deque of indices whose values decrease. The front is always the window's max; pop smaller values from the back as you go.
When is greedy safe?Greedy & IntervalsGreedy is right when taking the locally best move can never hurt later. Try to argue that, or find a counterexample, before coding.
Why some “nested loops” are still O(n)Habits & complexityCount total work, not loop nesting. If each element enters and leaves a stack or window once, the whole thing is O(n).