Common Algorithmic Pitfalls

Most algorithmic bugs are not exotic — they are the same handful of mistakes repeated across problems: a greedy choice applied where it does not hold, an off-by-one in a DP table, a missing memoization cache turning polynomial work into exponential work, or a base case that quietly breaks recursion. This topic walks through the pitfalls that show up most often in interviews and real code, with the reasoning needed to spot and avoid each one.

You get a solution that looks correct on the examples you tried but fails on a case where the locally best choice is not globally optimal. The classic example is the 0/1 knapsack problem: greedily picking items by best value-to-weight ratio can fail because you cannot take a fractional item, so an earlier greedy pick can block a better later combination. Fractional knapsack, in contrast, does allow taking fractions, which restores the greedy-choice property. The fix is to check whether making the current best choice ever needs to be undone later; if yes, DP is required to consider all reachable states.

DP tables are often sized (n+1) x (m+1) to hold a base case row/column representing empty prefixes, but it is easy to index with the wrong offset — using dp[i][j] where dp[i-1][j-1] was intended, or looping range(n) instead of range(1, n+1). This is especially common in longest common subsequence and edit distance, where dp[i][j] represents the first i characters of one string and the first j of another, not indices i and j directly. The fix is to write out the exact meaning of dp[i][j] as a sentence before coding, and verify it against a tiny hand-traced example (like two 2-character strings) before trusting the loop bounds.

A recursive solution to a problem with overlapping subproblems, written without caching, recomputes the same subproblem exponentially many times. Naive recursive Fibonacci is the textbook case: fib(n) calls fib(n-1) and fib(n-2), and the call tree has O(2^n) nodes even though there are only n distinct subproblems. The same trap appears in naive recursive solutions to coin change, longest increasing subsequence, or matrix chain multiplication. The fix is to add a memo dictionary keyed by the subproblem's parameters (or convert to bottom-up tabulation), turning O(2^n) into O(n) or O(n^2) depending on the state space.

A base case that is missing, wrong, or reached too late causes infinite recursion (eventually a RecursionError / stack overflow), or a subtly wrong answer that only shows up on edge inputs like an empty list, a single element, or n=0. For example, a recursive factorial that checks 'if n == 1: return 1' will infinite-loop on n=0 because it never matches the base case as n decrements past 1 into negative numbers without a matching condition. The fix is to explicitly enumerate every base case the recursive structure implies (empty input, single element, boundary index) and test each one directly, not just the general recursive case.

Dijkstra assumes that once a node's shortest distance is finalized (popped from the priority queue with the minimum tentative distance), no future edge can improve it — that assumption only holds if all edges are non-negative. A negative edge encountered after a node is finalized can retroactively create a shorter path that Dijkstra will never revisit, producing a wrong answer without raising any error. Bellman-Ford correctly handles negative weights by relaxing every edge V-1 times and can additionally detect negative cycles, at the cost of higher time complexity, O(V * E) versus O((V+E) log V).

No — Python integers have arbitrary precision and grow automatically as needed, so classic overflow bugs (like a 32-bit int wrapping to negative after multiplication) simply do not occur in pure Python. This is a real advantage when implementing algorithms like large-number Fibonacci, factorial, or combinatorics, but it can also hide a design mistake: an algorithm that is supposed to run in bounded integer space in Java/C++ might silently work in Python while being technically incorrect if ported to a language with fixed-width integers. In interviews, if asked about overflow, mention that Python sidesteps it but that you would still guard against unexpectedly huge intermediate values for performance reasons, since arbitrary-precision arithmetic on very large integers is not O(1).

Using a mutable default argument like def helper(n, memo={}) shares the same dictionary object across every call to the function, including calls from unrelated test cases or subsequent runs, which can leak stale cached values and produce wrong answers on the second invocation. The fix is to default the memo to None and initialize a fresh dictionary inside the function body (if memo is None: memo = {}), or pass the cache explicitly from the caller.

Backtracking without pruning explores the full combinatorial search space, and a missing or weak pruning condition (checking constraints too late, or not at all until a full candidate is built) causes wasted exploration of branches that were doomed from the start. In N-Queens, for example, checking for column/diagonal conflicts only after placing all N queens instead of after each placement turns a fast pruned search into a near-exhaustive one. The fix is to validate partial state as early as possible (prune immediately upon a constraint violation) rather than validating only complete candidates.

Marking a node as visited too late — for example, adding to the visited set when a node is dequeued in BFS instead of when it is enqueued — allows the same node to be added to the queue multiple times through different paths, wasting time and, in cyclic graphs, potentially causing incorrect results or infinite loops if visited tracking is skipped entirely. The fix is to mark a node visited at the moment it is discovered (enqueued/pushed), not when it is processed.