How to Design Algorithms: A Step-by-Step Guide to Solving New Problems

Step 1: Understand the Problem Completely

Before writing a single line of pseudocode, make sure you understand exactly what the problem asks. Define the input precisely: what data types, what size ranges, what constraints? Define the output precisely: what format, what constitutes a valid answer, what happens with ties or edge cases? Work through several small examples by hand, including edge cases like empty input, single-element input, already-solved input, and worst-case input.

Many algorithm design failures start here. A misunderstood problem leads to a correct solution to the wrong problem. If the problem asks for "the shortest path," is it shortest by distance, time, or number of hops? If it asks for "all solutions," does it mean distinct solutions or all orderings? Clarify ambiguities before proceeding.

Drawing pictures helps enormously for problems involving graphs, trees, grids, or geometric structures. For sequence problems, writing out the input and manually tracing through possible operations builds intuition about what the algorithm must do.

Step 2: Identify the Problem Type and Related Problems

Most new problems are variations of known problem types. Recognizing the type immediately narrows the applicable techniques. Is this a sorting problem? A searching problem? A graph problem (shortest path, connectivity, flow)? A string problem (matching, alignment)? An optimization problem (maximize/minimize some quantity)? A counting problem (how many ways)? A decision problem (is this possible)?

Think about whether you have seen a similar problem before. Can the current problem be reduced to a known one? The ability to recognize that "this is really a shortest-path problem in disguise" or "this is equivalent to the knapsack problem" comes from exposure to a wide range of algorithm problems and is one of the most valuable skills in algorithm design.

Step 3: Start with a Brute Force Solution

Always begin with the simplest correct solution, even if it is hopelessly slow. The brute force approach tries all possible answers and selects the best one. For optimization problems, enumerate all candidates and evaluate each. For decision problems, check all possibilities. This solution serves three purposes: it confirms you understand the problem, it provides a correctness baseline for testing faster solutions, and it reveals the structure of the problem that more efficient algorithms can exploit.

Calculate the brute force time complexity. If it is O(n squared) and the input is small (under 1000), the brute force might be sufficient. If it is exponential and the input is large, you need a better approach. The gap between the brute force complexity and the theoretical lower bound tells you how much room for improvement exists.

Step 4: Choose an Algorithmic Strategy

Based on the problem type and structure, select a design strategy. Ask yourself these diagnostic questions:

Can the problem be divided into independent subproblems of the same type? Try divide and conquer. Does it have overlapping subproblems where the same computation is repeated? Try dynamic programming. Can you prove that a locally optimal choice is always globally optimal? Try a greedy approach. Does the problem involve exploring a tree of possibilities where dead ends can be detected early? Try backtracking. Is the problem on a graph? Use BFS, DFS, Dijkstra, or other graph algorithms. Can sorting the input make the problem easier? Many problems become simpler after sorting.

Often the key insight is a clever reformulation. Sorting the input, using a hash table for fast lookup, maintaining a running window over the data, or transforming the problem into a graph problem can dramatically simplify the algorithm. These reformulations come from experience and from asking "what would make this problem easy?"

Step 5: Write Pseudocode and Analyze Complexity

Express the algorithm in pseudocode, which is precise enough to implement but abstract enough to focus on logic rather than syntax. Name your variables clearly, specify loop bounds explicitly, and comment on the purpose of each major block. Pseudocode should be unambiguous: someone reading it should be able to implement it in any programming language.

Analyze the time complexity by counting the dominant operations (comparisons, additions, array accesses) as a function of input size. Identify nested loops, recursive calls, and their contribution to the total. Use the Master Theorem for divide-and-conquer recurrences. Analyze the space complexity by counting the auxiliary memory used: arrays, hash tables, recursion stack depth.

Compare the complexity to the brute force and to known lower bounds. If your algorithm matches the theoretical lower bound, you have an optimal solution. If there is a gap, consider whether further optimization is possible or whether the current complexity is acceptable for the expected input size.

Step 6: Implement, Test, and Optimize

Translate the pseudocode into working code. Test it against the brute force solution on many inputs, including randomly generated inputs of various sizes, to verify correctness. Pay special attention to edge cases: empty inputs, single elements, all-equal elements, maximum-size inputs, and boundary values.

If the algorithm is correct but too slow for the required input size, look for optimization opportunities. Can a hash table replace a linear search? Can sorting reduce the problem? Can unnecessary work be eliminated? Can the space usage be reduced (for example, using a rolling array in DP)? Profile the implementation to identify actual bottlenecks rather than guessing.

Document the algorithm's assumptions, limitations, and complexity. A well-documented algorithm is far more valuable than a clever but opaque one, because others (including your future self) will need to understand, maintain, and adapt it.