Loading learning content...
Every algorithmic problem has a shape—a structural signature formed by what you're given and what you must produce. Expert problem-solvers learn to read this shape instinctively, recognizing that the structure of the input constrains the possible algorithms, and the structure of the output reveals which operations are actually needed.
This is more than pattern matching; it's understanding the deep relationship between data structure and algorithm. When you see a tree, certain algorithms become natural (DFS, recursion). When you see a grid, others emerge (BFS, DP over positions). When the output is "count" vs "list all" vs "find any," entirely different complexity classes may be required.
By the end of this page, you will be able to systematically analyze input structures (arrays, strings, trees, graphs, matrices) and output requirements (counts, existence, optimization, enumeration) to rapidly narrow down viable algorithmic approaches. You'll develop the intuition to see which algorithm families are natural fits before writing a single line of code.
The type of input you receive is the first and most important signal about what algorithms to consider. This correspondence is so strong that expert problem-solvers often identify the algorithm family within seconds of reading the input description.
| Input Type | Natural Algorithm Families | Why This Correspondence Exists |
|---|---|---|
| Unsorted Array | Hash tables, sorting, counting, linear scan | No inherent order → must create structure or use O(1) lookup |
| Sorted Array | Binary search, two pointers, merge-based | Order enables elimination of search space logarithmically |
| String | Hashing, pattern matching (KMP/Rabin-Karp), DP, tries | Sequential character processing, substring/subsequence problems |
| Tree | DFS/BFS, recursion, tree DP, LCA, path queries | Hierarchical structure enables divide at nodes |
| Graph (general) | BFS/DFS, Dijkstra, Union-Find, topological sort | Connectivity and path problems are natural |
| Grid/Matrix | BFS/DFS (flood fill), 2D DP, coordinate geometry | Spatial relationships, 4/8-directional movement |
| Intervals | Sorting endpoints, sweep line, interval trees | Overlap/coverage queries become ordering problems |
| Set of numbers | Two sum variants, hash sets, sorting | Pair/tuple finding, membership testing |
When problem setters choose to give you a tree instead of a general graph, or a sorted array instead of unsorted, it's intentional. The input structure is a gift that constrains the problem space. Use it.
Arrays are the most common input type, but not all arrays are alike. The specific properties of an array dramatically affect which algorithms apply.
Beyond sorting, arrays may have properties that unlock specific techniques:
| Property | What It Enables | Example Problems |
|---|---|---|
| All elements unique | Direct indexing, no duplicate handling | Find missing number, permutation operations |
| Contains duplicates | Frequency counting, group processing | Find duplicate, majority element |
| Bounded values (e.g., 1-100) | Counting sort, direct index arrays | Sort in O(n), frequency histogram |
| All positive | Sliding window feasibility, prefix sums always increasing | Subarray sum problems, shortest subarray |
| Contains negatives | Cannot use simple sliding window, need hash/DP | Subarray sum = k (need hash map) |
| Circular array | Concatenate array or handle wrap-around | Maximum circular subarray sum |
| Immutable (read-only) | Cannot sort in place, may need extra space | Answer queries without modification |
The sign of array elements often determines algorithm feasibility. Sliding window for 'subarray with sum = k' works perfectly with all-positive elements (monotonic prefix sums). With mixed signs, you need hash maps to track prefix sums seen before. Always check whether negative numbers are possible.
Graphs vary enormously in structure, and different structures demand different algorithms. Recognizing graph properties from the problem statement is crucial.
| Property | Algorithmic Implications | What's Enabled |
|---|---|---|
| General graph | Need cycle handling, may need visited array | Standard BFS/DFS, Dijkstra |
| DAG (Directed Acyclic) | Topological sort possible, DP on nodes | Critical path, longest path, scheduling |
| Tree | No cycles, unique paths, n-1 edges | Simple DFS, tree DP, LCA |
| Undirected tree | Each node reachable from any other, no visited needed for tree DP | Rooted tree algorithms |
| Bipartite graph | Two-colorable, matching possible | Maximum matching, task assignment |
| Weighted edges | Need shortest path algorithms | Dijkstra, Bellman-Ford, Floyd-Warshall |
| Unweighted edges | BFS = shortest path | Simpler BFS suffices |
| Negative weights | Dijkstra fails | Must use Bellman-Ford |
| Sparse (E ≈ V) | Adjacency list efficient | O(V + E) traversals feasible |
| Dense (E ≈ V²) | Matrix representation may be better | Floyd-Warshall may be simpler |
Many problems that don't explicitly mention graphs are actually graph problems:
State-Space Search: When you need to transform one configuration into another, states are nodes and valid moves are edges.
Grid as Graph: Any grid problem with movement is implicitly a graph.
Dependency Ordering: Any problem with prerequisites or dependencies.
Social Networks/Relationships: Any entity with relationships.
When a problem involves entities with relationships, transitions, or dependencies, always ask: "What are the nodes? What are the edges? What graph property does this have?" This reframing often reveals the algorithm immediately.
Trees are a special case of graphs that deserve dedicated analysis. Their acyclic, hierarchical nature enables powerful recursive techniques.
The specific tree structure affects implementation:
| Tree Type | Representation | Traversal Approach |
|---|---|---|
| Binary tree | Left/right child pointers | Recursive with node.left, node.right |
| N-ary tree | Children list per node | Recursive with for-each over children |
| General tree (adjacency list) | Parent array or adjacency list | DFS avoiding parent in recursion |
| BST | Binary tree with ordering property | In-order gives sorted sequence; can binary search |
| Complete binary tree | Can use array representation | Parent at i/2, children at 2i, 2i+1 |
Pre-order (root first): Process before children — useful for copying structure. In-order (left-root-right): BST gives sorted order. Post-order (children first): Process after children — useful for computing subtree values. Level-order (BFS): Process by depth — useful for level-based operations.
Strings have unique characteristics that determine which algorithms apply. Understanding string-specific patterns is essential for recognizing string algorithm problems.
| Problem Type | Key Characteristic | Typical Approaches |
|---|---|---|
| Pattern matching | Find occurrences of pattern in text | KMP, Rabin-Karp, Z-algorithm, suffix structures |
| Substring problems | Find/count/optimize over contiguous parts | Sliding window, two pointers, hash maps |
| Subsequence problems | Characters in order but not contiguous | DP (often 2D), recursion with memo |
| Palindrome problems | Symmetry-based | Expand from center, DP, Manacher's |
| Anagram/permutation | Character frequency matters, not order | Frequency arrays, sorting, hash of counts |
| String transformation | Convert one string to another | Edit distance DP, BFS on string states |
| Lexicographic problems | Ordering of strings | Sorting, greedy character selection |
The size of the character alphabet significantly affects algorithm choice:
The distinction is critical: Substring = contiguous (use sliding window, hash). Subsequence = not necessarily contiguous (usually DP). Misidentifying which one the problem asks for leads to completely wrong algorithms.
What you must produce is just as important as what you're given. Different output types require fundamentally different algorithmic approaches.
| Output Type | Complexity Implication | Typical Approach |
|---|---|---|
| Yes/No (existence) | Often O(n) or O(n log n) possible | Hash set, sorting, early termination on find |
| Count | Can't enumerate all → need smart counting | DP counting, combinatorics, inclusion-exclusion |
| Single optimal value | Optimization problem | DP, greedy (if applicable), binary search on answer |
| One valid solution | Any correct answer acceptable | May use heuristics, early termination, don't need to explore all |
| The optimal solution (structure) | Must reconstruct, not just value | Track choices in DP, parent pointers |
| All solutions | May be exponential!! | Backtracking, careful about output size |
| k-th element | Partial ordering suffices | Quickselect O(n), heap, partial sort |
| Top-k elements | Need ordering of top portion | Heap O(n log k), partial sort |
Consider the difference:
"How many subsets sum to target?" — This is a counting problem. You need DP or inclusion-exclusion. Enumerating could be exponential.
"List all subsets that sum to target." — This is an enumeration problem. If there are exponentially many answers, the problem is asking for exponential work.
Always verify: Is the output size polynomial? If the problem asks to list all solutions but constraints allow exponential solutions, the problem may be poorly designed—or there's a constraint you missed.
Before implementing enumeration, estimate the maximum output size. If it's exponential (e.g., all subsets, all permutations), verify this is expected. Sometimes problems that seem to ask for enumeration actually want counting or a single example.
Three fundamental problem types require different algorithmic strategies:
Question format: "Does X exist?" or "Is Y possible?"
Characteristics:
Approach signals:
Question format: "What is the maximum/minimum X?" or "Find the best Y."
Characteristics:
Approach signals:
Question format: "How many ways...?" or "Count all X such that..."
Characteristics:
Approach signals:
Many optimization problems can be solved via binary search on the answer: instead of directly finding the minimum X, binary search over possible X values and for each, solve the decision version "Can we achieve X?" This transforms optimization into multiple decision problems.
Real problems often combine multiple structures. Recognizing these composite patterns accelerates solution identification.
| Pattern | Input Structure | Solution Approach |
|---|---|---|
| Array + Queries | Array with multiple range queries | Preprocessing: prefix sums, sparse table, segment tree |
| Graph + Weights + Shortest Path | Weighted graph, find min cost path | Dijkstra, Bellman-Ford based on weight properties |
| Two Arrays/Strings Comparison | Compare/merge two sequences | DP (2D often), merge-based algorithms |
| Nested Structure (Tree of Trees) | Hierarchical groupings | Multi-level recursion, careful state management |
| Grid + Path Finding | 2D matrix, find optimal path | BFS (unweighted), DP (for counting), Dijkstra (weighted) |
| Intervals + Events | Start/end times, ranges | Sweep line, merge intervals, event scheduling |
| String + Pattern + Multiple Queries | Text with pattern searches | Suffix array, trie, Aho-Corasick (multiple patterns) |
When problems have this structure:
The solution almost always involves:
Total time: O(n preprocessing) + O(q × log n per query) = O((n + q) log n)
Common preprocessing structures:
When q queries of n-sized data would take O(n × q), recognize that preprocessing can trade upfront work for faster queries. The key question: "What information can I precompute once to answer all queries faster?"
Let's practice structural analysis on example problems:
Design a data structure that supports get(key) and put(key, value) in O(1), with LRU eviction when capacity is exceeded.
Structural Analysis:
Given an m×n grid of characters and a word, determine if the word exists in the grid by moving to adjacent cells.
Structural Analysis:
Given a collection of intervals, merge all overlapping intervals and return the non-overlapping intervals.
Structural Analysis:
The structure of what you receive and what you must produce forms a signature that points toward the right algorithmic approach. By analyzing input types and output requirements systematically, you can rapidly narrow down viable algorithms.
What's Next:
With input/output analysis mastered, we move to the culminating skill: relating new problems to known problems. You'll learn how to recognize that unfamiliar problems are disguised versions of classic archetypes, and how to leverage this recognition to apply proven solutions.
You now understand how to read the structural signature of any problem. Input types guide algorithm family selection; output requirements determine complexity class. Together, they form a powerful filter that eliminates wrong approaches and highlights promising ones before you write any code.