Competitive Programming: Think Fast, Code Faster

Imagine you have solved a problem correctly. Your code compiles, and when you test it on the sample input the judge gave you, it prints the exact right answer. You submit it on a site like CodeChef or LeetCode, feeling confident — and the judge replies with two words that every competitive programmer dreads: Time Limit Exceeded.

Your logic was not wrong. Your approach was too slow. This is the single biggest difference between "coding" and "competitive programming": in competitive programming, a correct answer that arrives too late is treated exactly the same as a wrong answer. The judge does not care that your program would have printed the right number eventually — it only ran your code for one or two seconds, and then it gave up. Competitive programming is the skill of recognizing, before you write a single line of code, which kind of algorithm a problem needs, so that "eventually" becomes "instantly."

This chapter teaches you the single most important pattern-recognition skill in competitive programming: knowing when a problem is secretly a graph problem, and knowing which of the two classic graph-traversal algorithms — Breadth-First Search (BFS) or Depth-First Search (DFS) — actually solves it. Get this pattern wrong, and you get Time Limit Exceeded or, worse, a Wrong Answer that looks almost right. Get it right, and problems that look terrifying at first glance become a five-minute exercise in writing a template you already know cold.

Reading the Constraints Before You Read the Problem

Every competitive programming problem gives you "constraints" — limits on the size of the input, and a time limit for your program to finish. Experienced competitive programmers read these numbers first, before they even fully understand the problem statement, because the constraints tell you which algorithms are even allowed to exist.

Here is the rule of thumb the whole competitive programming community uses: a typical judge can execute roughly 10⁸ (100 million) simple operations in one second. It is not exact — it depends on the machine and the operations — but it is close enough to plan around. So if a problem gives you n = 100,000 (10⁵) and a 1-second time limit, you can quickly rule algorithms in or out:

• An algorithm that does work proportional to n² would run about (10⁵)² = 10¹⁰ operations. That is 100 times more than your 10⁸ budget — instant Time Limit Exceeded, no matter how cleanly you code it.
• An algorithm that does work proportional to n or n log n runs about 10⁵ or roughly 1.7 × 10⁶ operations. Comfortably inside the budget, with room to spare.

This is not a minor detail — it is the whole game. A problem with n ≤ 1,000 is quietly telling you "an O(n²) solution is fine, don't overthink it." A problem with n ≤ 10⁵ or n ≤ 10⁶ is telling you "you need something close to O(n) or O(n log n), and if your first idea is a nested loop over every pair, throw it away before you write it." Reading constraints first is how competitive programmers avoid wasting twenty minutes coding a solution that was mathematically doomed from the start.

Graphs: The Data Structure Hiding Inside Half of All CP Problems

A huge fraction of problems that look like they are "about" grids, maps, friendships, courses with prerequisites, or word ladders are, underneath, the same structure: a graph. A graph is just two things — a set of vertices (also called nodes: people, cities, rooms, web pages, anything) and a set of edges (connections between pairs of vertices: friendships, roads, links, doors). If the connection works in both directions — a road you can drive either way, a mutual friendship — the graph is called undirected. That is the kind of graph this chapter focuses on.

Think of a metro map. Each station is a vertex. Each direct track segment between two adjacent stations is an edge. When you ask "what is the fewest number of stops from Station A to Station F?", you are asking a graph question, whether or not the problem statement uses the word "graph" at all.

Let's build a small, simplified practice map — not a real transit line, just a clean example for tracing algorithms by hand. Six stations, A through F, connected like this:

A -- B
A -- C
B -- D
C -- D
C -- E
D -- F
E -- F

The most common way to store a graph in code — and the one you will reach for in nearly every contest — is an adjacency list: a dictionary (or array) where each vertex maps to the list of vertices it connects to directly.

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D', 'E'],
    'D': ['B', 'C', 'F'],
    'E': ['C', 'F'],
    'F': ['D', 'E'],
}

Notice each edge appears twice — once from each end — because the graph is undirected. This costs a little extra memory but makes traversal code much simpler, which is exactly the kind of trade-off competitive programmers make constantly: a little more memory for a lot less code and a lot less chance of a bug.

Breadth-First Search: Exploring in Rings, Not Chains

Suppose the question is: "starting from station A, what is the minimum number of stops to reach every other station?" This is the classic shortest-path-in-an-unweighted-graph question, and the tool for it is Breadth-First Search (BFS).

The core idea of BFS is to explore the graph in expanding rings around the start, like ripples spreading outward from a stone dropped in water. First you look at everything exactly 1 stop away. Then, without skipping ahead, everything exactly 2 stops away. Then 3, and so on. Because you finish an entire ring before moving to the next one, the very first time you reach any station, you have reached it by the shortest possible route. That guarantee is the whole reason BFS exists.

To implement "ring by ring" in code, BFS uses a queue — a first-in-first-out list, exactly like a real queue at an IRCTC ticket counter: whoever joined first gets served first. You also keep a dist record of how far each station is from the start, which doubles as your "have I already found this station?" check.

from collections import deque

def bfs(graph, start):
    dist = {start: 0}
    q = deque([start])
    while q:
        node = q.popleft()          # serve the front of the queue
        for neighbor in graph[node]:
            if neighbor not in dist:      # not reached yet
                dist[neighbor] = dist[node] + 1
                q.append(neighbor)        # join the back of the queue
    return dist

Let's trace this by hand on our six-station map, starting at A, because tracing an algorithm on paper before trusting it in a contest is a habit that saves you from silent bugs.

• Start: dist = {A: 0}, queue = [A]
• Serve A (dist 0): neighbors are B, C, neither seen before. Set dist[B]=1, dist[C]=1. Queue becomes [B, C].
• Serve B (dist 1): neighbors are A (seen), D (new). Set dist[D]=2. Queue becomes [C, D].
• Serve C (dist 1): neighbors are A (seen), D (seen), E (new). Set dist[E]=2. Queue becomes [D, E].
• Serve D (dist 2): neighbors are B (seen), C (seen), F (new). Set dist[F]=3. Queue becomes [E, F].
• Serve E (dist 2): neighbors C and F are both already seen. Nothing new. Queue becomes [F].
• Serve F (dist 3): neighbors D and E are both already seen. Queue empties. Done.

Final answer: dist = {A:0, B:1, C:1, D:2, E:2, F:3}. Station F is exactly 3 stops away, reached along the ring boundary at exactly the right moment — never guessed, never assumed, discovered layer by layer.

The Misconception: "DFS Also Finds the Shortest Path" — It Does Not

A very common mistake, made even by students who have written both BFS and DFS correctly, is assuming that Depth-First Search (DFS) — the algorithm that plunges as deep as possible down one path before backtracking — will also find the shortest route. It will find a route. It will not, in general, find the shortest one, and the reason is worth tracing carefully, because this exact bug quietly produces wrong answers in contests.

DFS uses the same adjacency list, but instead of a queue it uses a stack (or, equivalently, recursive function calls), and it commits fully to one neighbor before even glancing at the others:

def dfs(graph, start):
    visited = {start}
    parent = {start: None}
    def visit(u):
        for v in graph[u]:
            if v not in visited:
                visited.add(v)
                parent[v] = u
                visit(v)
    visit(start)
    return parent

Run this starting at A, exploring each station's neighbor list in the order it is written (['B','C'] for A, ['B','D'] — wait, A's list — for B it's ['A','D'], and so on):

• Visit A. First unvisited neighbor: B. Dive into B.
• Visit B. First unvisited neighbor: D (A is already visited). Dive into D.
• Visit D. Neighbors are B (visited), C (unvisited — dive in), F (still waiting).
• Visit C. Neighbors are A (visited), D (visited), E (unvisited — dive in).
• Visit E. Neighbors are C (visited), F (unvisited — dive in).
• Visit F. Both neighbors, D and E, are already visited. Backtrack all the way out.

DFS did reach every station, and it did find a valid path from A to F. But trace the parent pointers back from F: F ← E ← C ← D ← B ← A. That path — A, B, D, C, E, F — uses 5 edges. BFS found A, B, D, F using only 3 edges. Same graph, same start, same destination — DFS's path is nearly twice as long, because DFS has no concept of "rings" at all; it simply commits to whatever neighbor comes first and only backs out when it hits a dead end. It got lucky and reached F eventually, but through a long detour, not the short way.

The fix is not to abandon DFS — it is an excellent, faster-to-write tool for a different family of questions, which the next section covers. The fix is to memorize the actual rule: use BFS whenever a problem asks for the minimum number of steps, moves, hops, or edges in an unweighted graph. If you see the words "minimum," "fewest," or "shortest" attached to a grid or a network with no weights on the edges, your hand should reach for a queue, not a stack, before you write another line.

Why This Runs Fast: O(V + E)

Now return to the constraints discussion from the start of this chapter. In BFS, every vertex is added to the queue at most once (the dist check guarantees this), and every edge is examined at most twice — once from each of its two endpoints. If V is the number of vertices and E is the number of edges, the total work is proportional to V + E. Competitive programmers write this as O(V + E), and for graphs where E is at most a small multiple of V (true for road networks, metro maps, and most contest graphs), this is essentially linear time — exactly the speed a 10⁵-vertex constraint demands.

Compare that to the brute-force alternative someone might try instead: literally enumerate every possible path from A to F and keep the shortest one. Even on our tiny 6-station map, the number of distinct paths grows fast, and on a graph with just 20 well-connected vertices, the count of possible paths can already run into the millions — because each additional vertex roughly multiplies the number of ways to extend a path. That growth is exponential, not linear, and it is precisely the trap that turns a 5-minute BFS solution into a Time Limit Exceeded verdict for anyone who tries to "just check every path."

A Second Pattern: Counting Groups With DFS

Not every graph question asks for a shortest path. A very common contest pattern instead asks: "how many separate, disconnected groups exist in this graph?" — for example, "how many friend circles are there, given who is friends with whom?" This is where DFS genuinely shines, because you do not care about distance at all — you only care about which vertices can reach which other vertices somehow, and DFS explores an entire connected region just as completely as BFS does, with slightly simpler code.

Suppose five students are represented by a 5×5 friendship matrix, where a 1 in row i, column j means students i and j are direct friends (and everyone is trivially friends with themselves, hence the 1s on the diagonal):

matrix = [
    [1,1,0,0,0],   # student 0 is friends with 1
    [1,1,1,0,0],   # student 1 is friends with 0 and 2
    [0,1,1,0,0],   # student 2 is friends with 1
    [0,0,0,1,1],   # student 3 is friends with 4
    [0,0,0,1,1],   # student 4 is friends with 3
]

def count_friend_circles(matrix):
    n = len(matrix)
    visited = [False] * n
    circles = 0

    def explore(u):
        visited[u] = True
        for v in range(n):
            if matrix[u][v] == 1 and not visited[v]:
                explore(v)

    for student in range(n):
        if not visited[student]:
            explore(student)      # sweep the whole group in one DFS
            circles += 1          # found one more separate group

    return circles

Trace it: the outer loop starts at student 0. It is unvisited, so explore(0) runs, marking 0 visited, then following the 1 in the matrix to student 1 (marking 1 visited), which in turn follows its own row to student 2 (marking 2 visited). Students 0, 1, and 2 are now all visited in a single DFS sweep, and circles becomes 1. The outer loop continues: student 1 and 2 are already visited, skip them. Student 3 is unvisited — explore(3) runs, sweeping in student 4 as well, and circles becomes 2. Final answer: 2 friend circles — {0, 1, 2} and {3, 4} — found in O(n²) time for an n×n matrix, which comfortably fits constraints where n is a few thousand.

The Pattern-Recognition Playbook

This is the actual skill competitive programmers train for months to build instinctively. When you read a new problem, translate it into graph language first, then match it against this short list:

• "Minimum number of moves / hops / steps / clicks" in an unweighted grid or network — this is shortest path with no edge weights. Reach for BFS.
• "How many separate groups / islands / provinces / clusters exist" — this is counting connected components. Either BFS or DFS works; DFS is usually shorter to write.
• "Is it possible to reach X from Y at all" — a simple reachability check. Either traversal works; stop as soon as you find the target.
• "Shortest path, but roads have different costs/times/distances attached" — this is no longer unweighted, so plain BFS gives wrong answers here. This needs a weighted shortest-path algorithm (Dijkstra's algorithm), which builds directly on the BFS idea but replaces the plain queue with one that always serves the currently-cheapest option — a tool you will meet in a later chapter once you're comfortable with BFS itself.

Recognizing which bucket a problem falls into, in the first thirty seconds of reading it, is what separates a contestant who solves six problems in a two-hour contest from one who solves two — not typing speed, not knowing more syntax, but knowing instantly which nine-line template to reach for.

Practice: Test Your Speed

Work these on paper before checking the answer beneath each — the whole point of competitive programming practice is tracing by hand fast enough that, in a real contest, you don't need to.

1. Using the six-station map from this chapter, run BFS starting from station D instead of A. What is dist[A]? (Hint: retrace the ring method — D's direct neighbors first, then their neighbors.)
Answer: dist[A] = 2, via D → B → A or D → C → A — both are 2-edge routes, and BFS would discover A at ring 2 regardless of which one it reaches first.

2. A problem states n ≤ 2 × 10⁴ and a 2-second time limit. Is an O(n²) algorithm safe?
Answer: (2×10⁴)² = 4×10⁸. Your budget for 2 seconds is roughly 2×10⁸. It's close and risky — depends heavily on how simple the inner operation is — which is exactly the situation where a competitive programmer looks for an O(n log n) alternative rather than gambling.

3. A grid-based problem asks: "what is the minimum number of moves for a robot to reach the exit, moving one cell up/down/left/right at a time, with some cells blocked?" Which algorithm, and why?
Answer: BFS. Each move costs exactly 1, so this is shortest path in an unweighted graph where each grid cell is a vertex and each legal move is an edge — the textbook BFS signature.

4. Extend the friend-circle matrix by adding a 6th student who is friends with no one (row and column of all zeros except the diagonal). How many circles now, and why doesn't the code break?
Answer: 3 circles. The outer loop reaches student 5, finds it unvisited, calls explore(5), which marks only student 5 visited (no 1s to follow) and immediately returns — a "circle of one" is still counted correctly, because the code never assumed a group has more than one member.

Summary

Competitive programming rewards recognizing structure fast, not typing fast. A large share of problems that mention grids, maps, networks, prerequisites, or friendships are graphs in disguise, best stored as an adjacency list. BFS explores a graph ring by ring using a queue, and because it never enters a further ring before finishing the current one, it is the only traversal that guarantees the shortest path in an unweighted graph — DFS, which plunges depth-first using a stack, finds a valid path but not reliably the shortest one, as the five-edge detour in this chapter's trace showed concretely. BFS and DFS both run in O(V + E) time, dramatically faster than exponential brute-force path enumeration, which is why they scale to the constraints (n in the 10⁴–10⁶ range) that real contest judges impose. DFS remains the sharper tool for counting connected groups, where distance doesn't matter and only reachability does. The core discipline this chapter builds is reading a problem's constraints and phrasing before writing code: constraints tell you the required time complexity, and phrasing ("minimum moves" versus "how many groups") tells you whether to reach for a queue or a stack.