Searching, sorting, and the graph algorithms behind route-finding and dependency resolution.
Why this stage exists
These are the named people assume you know. More usefully, each one is a worked example of a technique you can reuse — halving a search space, dividing and combining, exploring a graph in a controlled order.
NeetCode 150 · complete category
Binary Search practice lab
When the data carries an order you can trust, every comparison can throw away half of what is left.
2 problems
Pattern first
Halving needs a guarantee, not just sorted-looking data
Naive
A linear scan asks every element the same question.
Why this works
If one comparison proves the target cannot be on one side, that side never has to be examined — twenty steps cover a million items.
Picture itA club with exactly two seats and a bouncer at the door: a newcomer gets in only by beating whoever is currently weakest inside.
Conceptual blueprint
Keep a min-heap of the k largest values seen; the weakest of them is the answer.
Animated dry-runFrame 1
1 / 6
03
12▲ seeded
21
35
46
54
seeded at index 1
The first k values seed the club. heapify arranges them so the smallest, 2, sits at the door.
weakest2k2
Lookup structure
heap → 2, 3
1import heapq
2
3def find_kth_largest(nums, k):
4 smallest_k = nums[:k]
5 heapq.heapify(smallest_k)
6 for value in nums[k:]:
7 if value > smallest_k[0]:
8 heapq.heapreplace(smallest_k, value)
9 return smallest_k[0]
Check yourself before reading onCost it first
When does O(n log k) actually beat sorting's O(n log n)?
Find the bug
Why does this return 1 instead of 5?
import heapq
def find_kth_largest(nums, k):
smallest_k = []
for value in nums:
heapq.heappush(smallest_k, value)
return smallest_k[0]
Predict the next step
The heap holds 3 and 5, and the next value is 6. What happens?
Fill in the blanks
Recall each hidden line before revealing it. 3 left.
1import heapq
2
3def find_kth_largest(nums, k):
4 smallest_k = nums[:k]
5 heapq.heapify(smallest_k)
6 for value in nums[k:]:
7
8
9
Why the naive approach falls short
Sort the whole array and index from the end, arranging n values to read one.
Why the optimized approach works
Only k values can ever matter, and the smallest of those k is exactly the kth largest overall.
Time
O(n log k) — one comparison per value, and a log k repair only when it wins.
Space
O(k) — the heap never grows past k entries.
What you are learning — 6 topics
Binary search
finds a boundary by checking the middle and discarding the half that cannot contain the answer.
Reach for it whenUse binary search instead of a linear scan when the data or answer condition is ordered and random access is cheap; do not use it on unsorted data.
Think of it likeLooking up a name in a phone book. You open the middle, see whether you have gone too far, and repeat on the correct half.
The idea takes one sentence. Getting it exactly right is famously fiddly — most programmers write it wrong on their first attempt, usually by mishandling the boundaries or looping forever when two items remain.
Be deliberate about three things: whether your high boundary is included or one past the end, whether the loop condition uses less-than or less-than-or-equal, and how the boundaries move after each comparison. Pick one convention and use it every time.
Syntax you can use
low, high = 0, len(nums) - 1
Sets inclusive bounds for a sorted list.
mid = (low + high) // 2
Finds the middle index of the remaining range.
if nums[mid] < target:
low = mid + 1
else:
high = mid - 1
Checks that a bisect position really contains the target.bisect returns an insertion point even when the target is absent.
Notice that one middle comparison discards a contiguous half; the sorted order is what makes that discard safe.
Several ways to see it
What the machine doesOne comparison rewrites a closed interval
The algorithm compares the middle value, then moves either the low boundary above it or the high boundary below it. The invariant is that any possible answer remains inside the current interval.
How it breaksA one-character boundary error can preserve the interval forever
Using `low = mid` in a closed interval may stop shrinking when only two positions remain. Decide whether the high end is inclusive or exclusive before coding and make every update consistent with that choice.
Against the alternativeSorting is the entrance fee for repeated search
A single lookup in unsorted data is often cheaper as a linear scan than sorting first. Binary search pays when order already exists or many queries can amortize the O(n log n) preparation.
In the wild
Python bisect — locates an insertion boundary in a sorted list without scanning from the start.
Git bisect — repeatedly tests a midpoint commit to narrow the history containing a regression.
Commonly gets misread as
"Binary search only finds exact numbers." Correction: it can find the first or last position where a monotone condition changes.
"Sorting first is always worth it." Correction: one lookup may be cheaper as a linear scan.
What it costs. A million items takes about twenty steps. Requires the data to be sorted already.
Sorting rearranges values into an order that makes later comparison, grouping, and searching simpler.
Reach for it whenSort instead of repeatedly scanning when many later operations benefit from order; use a heap for a streaming top k and a for exact grouping.
The slow ones first, because they teach the vocabulary. Bubble sort repeatedly swaps neighbours that are out of order. Selection sort repeatedly finds the smallest remaining item. Insertion sort takes each item and slides it back into place among those already sorted. All three are O(n²) and none is used for large data.
Insertion sort is the exception worth knowing: it is genuinely fast on small or nearly-sorted input, and real sorting libraries switch to it for small chunks. Do not dismiss it.
Syntax you can use
nums.sort()
Sorts a list in place, ascending.
ordered = sorted(nums, reverse=True)
Returns a new list in descending order.
people.sort(key=lambda person: person.age)
Sorts objects by a chosen value.
words.sort(key=str.lower)
Sorts text without treating capitals separately.
pairs.sort(key=lambda pair: (pair[1], pair[0]))
Sorts by one field, then breaks ties with another.
Notice the widening gap between n log n comparison sorting and a quadratic elementary sort as input grows.
Several ways to see it
What the machine doesComparison sorts learn order one question at a time
Each comparison reveals only which of two values comes first, so a general sort needs about n log n such answers in the worst case. Counting and radix sorts escape that bound only by exploiting structure beyond pairwise comparison.
Against the alternativeMerge sort buys certainty with extra storage
Merge sort guarantees O(n log n) and preserves equal-item order, but typically needs an auxiliary . Quicksort often has better locality and small constants in memory, while a poor pivot can expose its quadratic worst case.
How it breaksStability matters when order carries prior work
If records were first sorted by name and then stably sorted by department, names remain ordered within each department. An unstable second sort may silently destroy that useful tie order.
In the wild
Python Timsort — detects existing ordered runs and merges them to sort lists stably.
PostgreSQL — uses in-memory or external sort operations for ORDER BY, merge joins, and some aggregations.
Commonly gets misread as
"The fastest sort is one algorithm everywhere." Correction: data shape, memory, stability, and storage change the choice.
"Stable means the output never changes." Correction: equal-key items keep their original relative order.
What it costsBubble, selection, insertion: O(n²). Merge and heap: O(n log n) guaranteed. Quicksort: O(n log n) typical, O(n²) worst. Counting and radix: O(n + k), with conditions.
BFS explores outward one step at a time; DFS follows one route deeply before returning to try another.
Reach for it whenUse BFS instead of DFS for the fewest edges in an unweighted graph or level order; use DFS for reachability, cycles, and work that finishes children before parents.
Breadth-first uses a queue and visits everything one step away, then everything two steps away. That ordering is exactly why it finds the shortest route when every step costs the same — the first time it reaches somewhere is by the fewest steps.
Depth-first uses a stack, or , which is the same thing. It goes as deep as it can and then backtracks. It is the natural fit for detecting cycles, finding connected components, and topological ordering.
Syntax you can use
from collections import deque
Imports the queue used by breadth-first search.
queue = deque([start])
seen = {start}
while queue:
node = queue.popleft()
for neighbour in graph[node]:
if neighbour not in seen: seen.add(neighbour); queue.append(neighbour)
The BFS shape: visit graph nodes one distance layer at a time.
stack = [start]
seen = set()
while stack:
node = stack.pop()
if node not in seen: seen.add(node); stack.extend(graph[node])
An iterative DFS, which goes deep along one path before backtracking.
seen.add(start)
Marks a node when it enters the frontier, preventing duplicate queue work.
Notice that BFS reaches every one-edge neighbour before either two-edge node; the queue creates distance layers.
Several ways to see it
Its shapeThe frontier's container determines the search shape
A FIFO queue expands an even wave of increasing distance, while a LIFO stack follows one route deeply before returning. The neighbour data is identical; only frontier removal order changes.
Against the alternativeBFS proves fewest edges; DFS exposes structure
In an unweighted graph, the first BFS arrival has used the minimum number of edges. DFS is the natural fit for cycle detection, components, and dependency ordering because its enter-and-exit nesting reveals ancestry.
What it costsThe visited set can cost more than the frontier
Both traversals are O(V + E), but BFS may hold an entire wide level at once. DFS holds a path plus pending neighbours, which can be smaller on wide graphs and dangerously deep on chain-like ones.
In the wild
Git rev-list — walks the commit graph from selected commits while applying traversal and ordering rules.
Scrapy — can schedule discovered crawl requests in breadth-first or depth-first order.
Commonly gets misread as
"BFS is always faster." Correction: both may visit every node; their order and memory needs differ.
"Visited tracking is optional on a tree-like graph." Correction: a cycle can otherwise repeat forever.
What it costsBoth are O( + edges) — each vertex and edge is looked at once.
A shortest-path algorithm keeps improving the cheapest known way to reach each place until no better route can appear.
Reach for it whenUse BFS instead of Dijkstra when every edge has equal cost, Dijkstra for non-negative weights, and Bellman-Ford when negative edges must be allowed.
finds the shortest path only when every step costs the same. Once roads have different lengths, you need something cleverer.
Dijkstra's algorithm is the one to know properly. It keeps a of places to visit next, always expanding whichever is cheapest to reach so far. It is what powers turn-by-turn navigation. Its one condition is that no connection may have a negative cost — with negative costs its central assumption breaks.
Syntax you can use
dist = {node: float("inf") for node in graph}
dist[start] = 0
Initialises every distance as unknown, except the starting point.
import heapq
pq = [(0, start)]
Starts Dijkstra's priority queue with the source at distance zero.
cost, node = heapq.heappop(pq)
Takes the next node with the cheapest known route.
Relaxes an edge when it improves a neighbour's best route.
if cost != dist[node]:
continue
Skips an old heap entry after a better route was found.Dijkstra is not correct when any edge has a negative weight.
Notice that fewer edges is not always cheaper; the two-edge route through B costs less than the direct edge.
Several ways to see it
What the machine doesDijkstra finalizes the cheapest unsettled route
A priority queue reveals the frontier vertex with the smallest known distance. With non-negative edges, no later detour can improve a vertex after that minimum is finalized.
Against the alternativeThe edge rules choose the algorithm
BFS is Dijkstra's simpler cousin when every edge has equal cost. Bellman-Ford accepts negative edges at greater cost, while A* adds a goal-directed estimate when geometry or another admissible heuristic exists.
How it breaksOne negative edge destroys Dijkstra's proof
A route finalized as cheapest may later be improved by travelling through a negative edge. The implementation can still return plausible numbers, which makes violating the precondition more dangerous than an obvious crash.
In the wild
OSPF — runs Dijkstra's shortest-path-first calculation over link-state data to build routes.
NetworkX — provides Dijkstra and Bellman-Ford routines for weighted graph paths and lengths.
Commonly gets misread as
"Fewest edges means cheapest path." Correction: weighted edges can make a longer route cheaper.
"Dijkstra handles negative weights." Correction: a later negative edge breaks its settled-node guarantee.
What it costsDijkstra with a heap: O((V+E) log V). Bellman-Ford: O(V×E). Floyd-Warshall: O(V³).
A minimum spanning tree is the cheapest set of links that connects every point without keeping any loop.
Reach for it whenUse an MST instead of shortest paths when the goal is minimum total network cost, not minimum travel cost from one source; do not use it when direction matters.
Think of it likeLaying fibre to every house in a village for the least total cable, with no cable that could be removed while leaving everyone connected.
Kruskal's algorithm sorts every connection by cost and adds them cheapest-first, skipping any that would form a loop. Checking for that loop is exactly what union-find from week 28 does, which is why the two are always taught together.
Prim's algorithm instead grows outwards from one starting point, repeatedly adding the cheapest connection that reaches somewhere new. It uses a heap, in the same way Dijkstra does.
Syntax you can use
edges.sort(key=lambda edge: edge[2])
Orders weighted edges from cheapest to most expensive for Kruskal's algorithm.
if find(a) != find(b):
Checks whether an edge would join two separate components.
union(a, b)
mst.append((a, b, weight))
Accepts an edge and merges its two components.
if len(mst) == len(vertices) - 1:
break
Stops once the spanning tree has enough edges.
Notice that three chosen edges connect four vertices without a cycle; any fourth edge would be redundant for connectivity.
Several ways to see it
Why it existsConnecting everything is different from routing one journey
Network builders needed the cheapest set of links that made every site reachable, not the shortest trip between a chosen pair. A spanning tree removes every cycle because any cycle contains an edge connectivity can survive without.
Against the alternativeKruskal grows a forest; Prim grows one island
Kruskal sorts all edges and joins components with union-find, making it attractive for sparse edge lists. Prim repeatedly takes the cheapest boundary edge from one connected region and pairs naturally with and a heap.
How it breaksThe cheapest network does not promise cheap routes
An MST minimizes the sum of installed edge weights, not travel distance between every pair. A path inside it may be much longer than the graph's original shortest path.
In the wild
NetworkX — implements Kruskal, Prim, and Boruvka algorithms for minimum spanning trees and forests.
SciPy csgraph — computes a minimum spanning tree from a sparse weighted graph with Kruskal's algorithm.
Commonly gets misread as
"An MST gives the shortest route between every pair." Correction: it minimizes the sum of chosen edges, not each journey.
"There is always one unique MST." Correction: equal edge weights can produce several equally cheap trees.
What it costsKruskal: O(E log E), dominated by the sort. Prim with a heap: O(E log V).
A topological sort lines up dependent jobs so every prerequisite comes before the work that needs it.
Reach for it whenUse it instead of ordinary sorting when order comes from dependencies in a directed acyclic graph; stop and report a cycle when no valid order exists.
Think of it likeGetting dressed. Socks before shoes, shirt before jumper. Several valid orders exist, but some are impossible.
It only works on a directed graph with no cycles. If your dependencies contain a cycle — A needs B, B needs A — there is no valid order at all, and detecting that is half the value of running it.
Two ways to do it. Kahn's algorithm repeatedly takes anything with no remaining dependencies, outputs it, and removes it. Or run and output nodes in reverse finishing order.
Syntax you can use
from graphlib import TopologicalSorter
Imports the standard-library tool for dependency ordering.
order = list(TopologicalSorter(graph).static_order())
Returns a valid order for a dependency graph.
indegree[child] += 1
Counts one prerequisite edge into child.
if indegree[neighbour] == 0:
queue.append(neighbour)
Queues work once every prerequisite has been removed.
if len(order) != len(graph):
raise ValueError("cycle")
Detects a cycle when Kahn's algorithm cannot order every node.
Notice that test and lint may swap places, but both must follow code and precede deploy.
Several ways to see it
Its shapeThe result straightens arrows into one legal line
Every directed edge `A → B` becomes the claim that A must appear before B. Several lines may satisfy the same partial order because unrelated tasks can trade places.
What the machine doesZero indegree marks work whose prerequisites are gone
Kahn's algorithm queues vertices with no incoming edges, removes one, and decrements its dependants. If vertices remain after the queue empties, a cycle is withholding every remaining candidate.
How it breaksA cycle means no valid order exists
Dependencies A before B, B before C, and C before A cannot be scheduled by a clever tie-breaker. Detect and report the cycle rather than returning a partial list that looks complete.
In the wild
GitHub Actions — uses job needs relationships to wait for prerequisite jobs before scheduling dependents.
Apache Airflow — schedules tasks from a DAG only after their configured upstream dependencies are satisfied.
Commonly gets misread as
"The result is unique." Correction: independent jobs can appear in several valid orders.
"It can order a cycle if you pick a start." Correction: a dependency cycle has no topological ordering.
Reading about this stage is not the same as finishing it. Type every one of these from a blank file rather than copying — the writing is the part that teaches.
Binary search, correct on the first attempt
Write it, then test it against an empty list, a one-item list, the first item, the last item, and a missing item. Then write the variant that finds the first position where a value could be inserted while keeping order.
Merge sort and quicksort
Write both. Then sort a list of a million random numbers with each and time them against Python's built-in sorted(). Seeing how much faster the built-in is is a useful lesson in not writing your own in production.
Dijkstra with a real map
Build a small graph of towns and road distances, then find the shortest route between two of them. Use the heapq module for the priority queue. Then print the route, not just its length — reconstructing the path is the part people forget.
A tiny build system
Take a set of tasks with dependencies and output a valid order. Then add a circular dependency and make it report a clear error instead of looping forever.
You are done with this stage when
Exit checkYou can write merge sort, quicksort, binary search correct on the first try, breadth-first and depth-first search, Dijkstra, and topological sort from a blank file. Around 200 problems solved in total.
If you cannot do this, repeat the stage rather than moving on. Nothing later gets easier by skipping it.
This stage corresponds to DSA Phase 4 — Core Algorithms in the source roadmap.