Algorithmic Problem-Solving and Data Structure Selection Questions

Direct answer

Before writing any code, look for two structural signals: does the problem have overlapping subproblems and optimal substructure (an optimal solution is built from optimal solutions to smaller versions of itself)? If yes, it is a dynamic programming (DP) problem, not a greedy one. Within DP, whether you reach for memoization (caching recursive-call results, computed top-down) or tabulation (filling a table iteratively, bottom-up) is a secondary implementation choice, not a correctness question: both compute the same recurrence.

Structured elaboration

Signal 1: does a locally optimal choice guarantee a globally optimal one? Greedy algorithms make one irrevocable choice at each step and never reconsider it. That is only correct when the problem has the "greedy-choice property": committing to the best-looking option right now cannot make the final answer worse. You test this by trying to construct a counterexample where the locally-best choice forecloses a better global outcome (an exchange argument): if you can build one, greedy is wrong and you need DP; if every attempt to build a counterexample fails and you can sketch why (an exchange argument that any optimal solution can be rearranged to match the greedy choice without loss), greedy is likely correct.

Signal 2: overlapping subproblems and optimal substructure. If solving the problem for a larger input naturally requires solving the same smaller subproblem many times (for example, "the best way to reach state k" depends on "the best way to reach state k-1", but state k-1 also gets asked about from other paths), you have overlapping subproblems. If, in addition, an optimal solution to the whole problem is composed of optimal solutions to its subproblems (no locally-suboptimal subproblem answer can still lead to a globally optimal whole), you have optimal substructure. Both together mean DP applies: cache each subproblem's answer once, reuse it everywhere it recurs.

Signal 3: what does the recurrence look like? Write the recurrence in terms of "the answer for state X depends on the answer for smaller states Y, Z, ...", before touching code. If you can write this recurrence but it does not have an ordering where "smaller" always resolves before "larger" (a genuine dependency cycle), you likely need a different technique entirely (graph shortest-path with cycles, for instance).

Once you know it's DP: memoization vs tabulation. These are the same recurrence expressed two ways, not two different algorithms:

Worked example

Take "minimum coins to make amount 6 from denominations {1, 3, 4}" (the coin change problem). The recurrence is: minCoins(a) = 1 + min(minCoins(a - c) for c in coins if c <= a), with minCoins(0) = 0. Overlapping subproblems are visible immediately: computing minCoins(6) needs minCoins(5), minCoins(3), minCoins(2); computing minCoins(5) also needs minCoins(2). minCoins(2) gets requested from two different callers, so caching it once and reusing it is exactly what turns an exponential naive recursion into a linear-in-target one. That overlap is the tell that this is DP, not greedy: a greedy "always take the largest coin" would take 4 then 1 then 1 (3 coins), while the true optimum is 3 + 3 (2 coins), because taking the largest coin first forecloses the better pairing, a real exchange-argument counterexample, confirming greedy is unsafe here and DP (with either memoization or tabulation) is required.

Trade-offs & pitfalls

Key points

• The most common mistake is reaching for greedy because a locally-best choice feels right; the discipline is to actively try to break it with a counterexample before trusting it, not to trust it by default.
• A DP recurrence existing does not by itself tell you whether to memoize or tabulate; that choice depends on whether the reachable state space is sparse (favors memoization) or dense with a clean iteration order (favors tabulation), and on language-specific recursion-depth limits.
• Some problems only look like DP: if there is no genuine overlap (each subproblem is only ever needed once), plain recursion or divide-and-conquer is simpler and DP's caching buys you nothing.

Complexity

• These are meta-level signals, not a specific algorithm, so there is no single complexity here; once you commit to DP, complexity is (number of distinct states) times (work per state), whether computed top-down with a cache or bottom-up with a table.

Edge cases

• A problem with optimal substructure but no overlapping subproblems (each subproblem solved once) does not need DP's memoization; plain recursion or divide-and-conquer suffices and adding a cache only adds overhead.
• A problem where you cannot write a clean dependency order for tabulation (irregular, data-dependent state transitions) may force memoization even in a dense-looking state space, since an explicit iteration order is hard to construct correctly.

Direct answer

All three (permutations, subsets, and valid combinations of balanced parentheses) share the same backtracking template: make one choice, recurse into the smaller remaining problem, then undo the choice before trying the next one (a "choose, explore, un-choose" loop). What changes between them is only the branching rule (what counts as a legal next choice at each step) and the pruning rule (what makes a partial choice already invalid, so you can abandon that branch immediately instead of completing it and checking at the end).

Structured elaboration

The shared template. Every backtracking search builds a partial solution incrementally. At each step: try each legal next choice, add it to the partial solution, recurse, then remove it (backtrack) before trying the next choice. Pruning means checking a partial solution's validity before recursing further into it, so invalid branches are cut off early rather than discovered only once fully built.

Permutations (branching rule: any not-yet-used element; no pruning needed since every partial arrangement of distinct elements is inherently valid):

def permute(nums):
    """All permutations of distinct integers via backtracking. O(n * n!) time."""
    res = []
    n = len(nums)
    used = [False] * n
    path = []

    def backtrack():
        if len(path) == n:
            res.append(path.copy())
            return
        for i in range(n):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack()
            path.pop()
            used[i] = False

    backtrack()
    return res

Subsets (branching rule: include or exclude each element in turn, in index order; no pruning needed since every partial inclusion/exclusion choice is valid):

def subsets(nums):
    """All subsets via backtracking: at each element, branch into
    include/exclude. O(2^n) subsets, O(n) recursion depth."""
    res = []
    path = []
    n = len(nums)

    def backtrack(i):
        if i == n:
            res.append(path.copy())
            return
        backtrack(i + 1)          # exclude nums[i]
        path.append(nums[i])
        backtrack(i + 1)          # include nums[i]
        path.pop()

    backtrack(0)
    return res

Balanced parentheses (branching rule: add ( or add ); pruning rule: never add ) unless fewer closes than opens have been placed, and never add ( once n opens are already placed, since either violation can never be repaired later):

def generate_parentheses(n):
    """
    All valid combinations of n balanced parenthesis pairs. Prunes any
    branch that would produce an invalid prefix.
    """
    res = []

    def backtrack(current, open_count, close_count):
        if len(current) == 2 * n:
            res.append(''.join(current))
            return
        if open_count < n:
            current.append('(')
            backtrack(current, open_count + 1, close_count)
            current.pop()
        if close_count < open_count:   # pruning rule: never let ')' outnumber '('
            current.append(')')
            backtrack(current, open_count, close_count + 1)
            current.pop()

    backtrack([], 0, 0)
    return res

The same family, different pruning rule and branching factor. Several other classic problems are this exact generate-and-prune shape with only the branching and pruning rules swapped:

• k-combinations (choose k elements from n, order irrelevant): branch only on elements after the last one chosen (to avoid generating the same combination in different orders), and prune once fewer than the remaining needed elements are available from the rest of the input.
• Partition into k equal-sum subsets: branch by assigning the next number to one of k running buckets, and prune a branch the moment any bucket's running sum exceeds the target per-bucket sum (target = total sum divided by k); sorting the input largest-first before starting makes this pruning fire earlier, since big numbers overflow a bucket's budget sooner.
• N-Queens: branch on which column to place the next row's queen in, and prune immediately if that placement attacks any already-placed queen (same column, or same diagonal). A common refinement is the minimum-remaining-value (MRV) heuristic from constraint-satisfaction search: instead of always filling rows in a fixed order, place the next queen in whichever row currently has the fewest legal remaining columns, since that row is the most likely to fail fast if the branch is doomed, cutting off bad branches sooner.
• Expensive black-box feature-subset search: choosing which features to include for a model is structurally a subset search, but each branch's "cost" (evaluating a model with that feature subset) is expensive, so pruning matters even more: bound-based pruning (stop exploring a subset once a cheap proxy score shows it cannot beat the current best) plays the same role that the diagonal-attack check plays in N-Queens, just with a learned or estimated bound instead of an exact rule.

Worked example

print(permute([1, 2, 3]))
print(subsets([1, 2, 3]))
print(generate_parentheses(3))

Output:

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
['((()))', '(()())', '(())()', '()(())', '()()()']

permute([1, 2, 3]) produces all 3! = 6 orderings. subsets([1, 2, 3]) produces all 2^3 = 8 subsets (including the empty one). generate_parentheses(3) produces exactly 5 valid strings, matching the third Catalan number (the count of valid balanced-parenthesis arrangements for n pairs grows as the Catalan numbers: 1, 1, 2, 5, 14, ... for n = 0, 1, 2, 3, 4); the pruning rule (never let a close-paren outnumber an open-paren so far) is exactly what keeps every generated string valid, so no post-filtering step is needed.

Trade-offs & pitfalls

Key points

• Permutations and subsets need no mid-search pruning because every partial state is automatically valid; balanced parentheses, N-Queens, and partition-into-k-subsets all need an explicit prune check, and skipping it (checking validity only once a candidate is fully built) still gives correct output but wastes enormous work exploring doomed branches to completion.
• Sorting input before backtracking (largest-first for partition-into-k-subsets, or a fixed variable order for N-Queens with the minimum-remaining-value heuristic) does not change correctness, but it changes how quickly invalid branches get pruned, which can be the difference between a search finishing quickly and one that effectively never terminates for larger n.
• For repeated elements in permutations, sort first and skip choosing the same value at the same recursion depth if the previous identical value at that depth was not used, to avoid generating duplicate permutations.

Complexity

• Permutations: time $O(n \cdot n!)$ (n! permutations, each costing O(n) to copy), space $O(n)$ recursion depth plus $O(n \cdot n!)$ to store all results.
• Subsets: time and space $O(n \cdot 2^n)$ (2^n subsets, each up to length n).
• Balanced parentheses: the valid-string count is the n-th Catalan number, so output size and total work are bounded by that count times $O(n)$ per string; no invalid branch is ever explored to completion because of the pruning rule.

Edge cases

• Empty input (n = 0 for parentheses, or an empty list for permutations/subsets): permutations of an empty list is a single empty permutation; subsets of an empty list is a single empty subset; generate_parentheses(0) returns a single empty string.
• Duplicate values in the input for permutations or subsets: without the sort-and-skip guard, the same output can appear multiple times; decide up front whether duplicates in the output are acceptable.
• Large n for any of these: all of them have output sizes that grow factorially or exponentially, so even a perfectly pruned search becomes impractical well before n reaches the double digits for permutations, or a few dozen for subsets.

Direct answer

The 0/1 knapsack DP state is dp[c] meaning "maximum total value achievable using a budget of exactly (or up to) c," updated per item by dp[c] = max(dp[c], dp[c - weight] + value), iterating capacities in descending order so each item is only used once. If the question changes from "maximize value" to "is some exact target sum achievable at all," the state becomes a boolean reachable[s] instead of a running maximum, using the identical recurrence shape (reachable[s] = reachable[s] or reachable[s - weight]) but tracking reachability instead of an optimum. This exact-sum variant is the same shape as the well-known Partition Equal Subset Sum problem, which asks whether a set of numbers can be split into two subsets with equal totals.

Structured elaboration

Value-maximization DP.

def knapsack_max_value(weights, values, capacity):
    """
    0/1 knapsack: maximum total value without exceeding capacity, each item
    at most once. dp[c] = best value achievable with budget c.
    Time O(n * capacity), Space O(capacity) (rolling 1D array).
    """
    dp = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        for c in range(capacity, w - 1, -1):   # descending: each item used at most once
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[capacity]

Feasibility (exact-sum) DP. Change the table's meaning from "best value so far" to "is this sum reachable," and change the update from a max to a boolean OR:

def subset_sum_feasible(weights, target):
    """
    Can some subset of weights sum to exactly target?
    reachable[s] = True if sum s is achievable using a subset of items seen
    so far. Same 0/1 recurrence as knapsack, but the DP value is a boolean
    "reachable" flag instead of a running maximum.
    Time O(n * target), Space O(target).
    """
    reachable = [False] * (target + 1)
    reachable[0] = True
    for w in weights:
        for s in range(target, w - 1, -1):
            if reachable[s - w]:
                reachable[s] = True
    return reachable[target]

Partition Equal Subset Sum is exactly this feasibility check with target set to half the total sum of the input numbers (if the total is odd, an equal split is impossible immediately, no DP needed). The same feasibility shape also applies to budget-constrained subset-selection outside pure combinatorics: for example, choosing dashboard KPIs or metrics under a display-cost budget, where each metric has a fixed "screen cost" and you want to know whether some subset exactly fills an allotted display budget (or, with the max-value version, which subset of metrics maximizes total business value within that budget).

Worked example

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack_max_value(weights, values, 5))

Output: 7 (taking the weight-2/value-3 and weight-3/value-4 items exactly fills the capacity-5 budget for total value 7; no other combination of these items reaches higher value within capacity 5).

nums = [1, 5, 11, 5]
total = sum(nums)
print(total, total % 2 == 0, subset_sum_feasible(nums, total // 2) if total % 2 == 0 else None)

Output: 22 True True. The total is 22 (even), so an equal split needs a subset summing to 11; subset_sum_feasible confirms 11 is reachable (via 5 + 5 + 1), so [1, 5, 11, 5] can be partitioned into two equal-sum halves.

Trade-offs & pitfalls

Key points

• Greedy selection by value-to-weight ratio is optimal for the fractional knapsack (where you can take a fraction of an item) but is not guaranteed optimal for 0/1 knapsack, since taking a high-ratio item can leave awkward leftover capacity that a different combination would have used better.
• The feasibility DP is strictly cheaper to reason about than the value-maximization DP (booleans instead of running maxima), but it answers a narrower question: it tells you whether a target is reachable, not which subset achieves it, unless you also track parent pointers or reconstruct the choice by scanning backward through the table.
• Both DP variants are pseudo-polynomial: their cost scales with the numeric capacity or target value, not just the number of items, so a very large capacity or target (in the millions) can make the DP impractical even though the item count is small; that is where a greedy approximation or a meet-in-the-middle exact method becomes attractive.

Complexity

• Value-maximization: time $O(n \cdot W)$, space $O(W)$, where n is the item count and W is the capacity.
• Feasibility: time $O(n \cdot T)$, space $O(T)$, where T is the target sum.

Edge cases

• Target or capacity of 0: dp[0]/reachable[0] are the trivial base cases (empty selection), both handled directly.
• An item heavier than the remaining capacity: naturally excluded by the descending-range guard (w - 1 lower bound), never considered for smaller capacities.
• Odd total sum in the partition-equal-subset-sum framing: no DP needed at all, an equal-value split is impossible by simple arithmetic before touching the table.

Direct answer

A recursive factorial mirrors the mathematical definition directly (n! = n * (n-1)!) and is easy to read, but every call adds a stack frame that must stay alive until its recursive call returns (so it can perform the pending multiplication), costing $O(n)$ call-stack space. An iterative version computes the same result in a simple loop with $O(1)$ extra space and no risk of hitting a language's recursion-depth limit. Convert to iteration (or, in languages that support it, tail-recursive form with an accumulator) whenever input size could be large or unpredictable enough to threaten stack depth, and keep plain recursion where it makes a naturally tree-shaped or divide-and-conquer problem clearer to read.

Structured elaboration

Recursive (not tail-recursive).

def factorial_recursive(n):
    """Compute n! recursively. Not tail-recursive: the multiplication by n
    happens AFTER the recursive call returns, so a frame must stay on the
    call stack waiting for that multiplication."""
    if n < 0:
        raise ValueError("n must be non-negative")
    if n == 0:
        return 1
    return n * factorial_recursive(n - 1)

Tail-recursive form. A call is "tail recursive" when the recursive call is the very last action taken, with nothing left to do after it returns. factorial_recursive above is not tail recursive: after factorial_recursive(n - 1) returns, the function still has to multiply by n. Rewriting with an accumulator argument that carries the running product forward makes the recursive call itself the last action:

def factorial_tail(n, accumulator=1):
    """Tail-recursive form: the recursive call is the last action, and the
    running product is threaded through as an argument instead of being
    computed after the call returns. (Python does not optimize tail calls,
    so this still uses O(n) stack frames in CPython -- the rewrite only
    pays off in languages/runtimes with tail-call elimination.)"""
    if n < 0:
        raise ValueError("n must be non-negative")
    if n == 0:
        return accumulator
    return factorial_tail(n - 1, accumulator * n)

Iterative form.

def factorial_iterative(n):
    """Compute n! iteratively. O(1) extra space (excluding the result)."""
    if n < 0:
        raise ValueError("n must be non-negative")
    result = 1
    for k in range(2, n + 1):
        result *= k
    return result

Whether the tail-recursive rewrite actually saves stack space depends entirely on the runtime: languages and runtimes that implement tail-call elimination reuse the current frame for the tail call, giving true $O(1)$ space; CPython does not do this, so factorial_tail still consumes one stack frame per call in Python, and the accumulator rewrite is mainly a stepping stone toward the fully iterative version rather than a real fix on its own in this language.

Naive recursive Fibonacci as a cautionary contrast. Recursion's clarity can hide a much worse problem than stack depth: naive recursive Fibonacci recomputes the same subproblems exponentially many times, because fib(n) calls both fib(n-1) and fib(n-2), and those calls each re-derive overlapping smaller values independently instead of sharing them.

call_count = 0

def fib_naive(n):
    global call_count
    call_count += 1
    if n < 2:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

Worked example

print(factorial_recursive(10), factorial_tail(10), factorial_iterative(10))

for n in (10, 20, 30):
    call_count = 0
    result = fib_naive(n)
    print(f"fib_naive({n}) = {result}, calls = {call_count}")

import sys
print("current recursion limit:", sys.getrecursionlimit())

Output:

3628800 3628800 3628800
fib_naive(10) = 55, calls = 177
fib_naive(20) = 6765, calls = 21891
fib_naive(30) = 832040, calls = 2692537
current recursion limit: 1000

All three factorial implementations agree on 10! = 3628800. The Fibonacci call counts show the exponential blowup directly: going from n=10 to n=20 (10 more) multiplies the call count by roughly 124x, and from n=20 to n=30 (10 more again) by roughly 123x, consistent with call count growing on the order of $O(\varphi^n)$ where $\varphi \approx 1.618$ is the golden ratio (memoizing or converting to an iterative bottom-up loop would fix this in $O(n)$ time, but that is a dynamic-programming technique, not a recursion-vs-iteration one).

Trade-offs & pitfalls

Key points

• Recursion's main cost is call-stack depth, not raw runtime: factorial_recursive and factorial_iterative do the same $O(n)$ multiplications, but only the recursive version risks a stack-depth error for large n.
• Rewriting to tail-recursive form is a code-shape change, not a guaranteed performance fix; check whether your language and runtime actually perform tail-call elimination before relying on it to save stack space.
• Naive recursive Fibonacci is a different failure mode entirely: it is not a stack-depth problem but a wasted-work problem, caused by recomputing identical overlapping subproblems; the fix (memoization or an iterative bottom-up loop) is a dynamic-programming technique, separate from the recursion-vs-iteration question this answer is centered on.

Complexity

• Recursive and iterative factorial: both $O(n)$ time; recursive uses $O(n)$ call-stack space, iterative uses $O(1)$ extra space.
• Naive recursive Fibonacci: $O(\varphi^n)$ time (exponential), $O(n)$ call-stack space (the deepest single call chain).

Edge cases

• Negative input: all three factorial functions raise ValueError explicitly rather than recursing or looping incorrectly.
• n = 0 or n = 1: all three correctly return 1 as the base case.
• Very large n for the recursive forms: Python's default recursion limit (commonly 1000) will raise a RecursionError well before overflowing the actual OS thread stack, since CPython enforces its own configurable limit; the iterative form has no such ceiling beyond available memory and integer size.

Direct answer

Slide a window over the string with two pointers, and keep a hash map from character to the index right after its most recent occurrence. When the character at the right pointer has been seen before at or after the current window's left edge, jump the left pointer forward to just past that previous occurrence, but never backward, and track the widest window seen along the way. Because the left pointer only ever advances and the right pointer sweeps the string once, the whole scan is $O(n)$ time using $O(\min(n, \text{alphabet size}))$ space for the map.

Approach

• Maintain last_seen, mapping each character to one past the index of its most recent occurrence (storing index + 1 lets an unseen character default cleanly to 0).
• Maintain left, the window's start, and best, the longest valid window length so far.
• For each right, if the current character was seen before, set left = max(left, last_seen[char]); the max is essential, not optional.
• Update best with the current window length right - left + 1, then record last_seen[char] = right + 1.

def length_of_longest_substring(s: str) -> int:
    """O(n) time, O(min(n, alphabet size)) space sliding window."""
    last_seen: dict[str, int] = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last_seen:
            left = max(left, last_seen[ch])
        best = max(best, right - left + 1)
        last_seen[ch] = right + 1
    return best


if __name__ == "__main__":
    print(length_of_longest_substring("abcabcbb"))  # 3
    print(length_of_longest_substring("bbbbb"))      # 1
    print(length_of_longest_substring("pwwkew"))     # 3
    print(length_of_longest_substring(""))           # 0

Running this prints 3, 1, 3, 0, matching the well-known cases for this problem.

Key points

• Why max, not a direct jump, is required: dropping the max and always jumping left = last_seen[ch] breaks correctness whenever a repeated character's earlier occurrence already fell outside the current window, because that would move left backward, re-including characters that had already been correctly excluded. Concretely, on "abba" a buggy version without max reports length 3, while the correct version reports 2 (the true answer, since "ab" and "ba" are the longest repeat-free substrings, both length 2). Verifying this directly:

def buggy_longest(s: str) -> int:
    last_seen: dict[str, int] = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last_seen:
            left = last_seen[ch]  # missing max(): can move left backward
        best = max(best, right - left + 1)
        last_seen[ch] = right + 1
    return best


def correct_longest(s: str) -> int:
    last_seen: dict[str, int] = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last_seen:
            left = max(left, last_seen[ch])
        best = max(best, right - left + 1)
        last_seen[ch] = right + 1
    return best


if __name__ == "__main__":
    print("abba ->", buggy_longest("abba"), "vs correct", correct_longest("abba"))

Running this prints abba -> 3 vs correct 2: the buggy version claims a length-3 window exists in "abba", but no 3-character substring of "abba" is actually repeat-free, so 3 is wrong.

• An alternative that uses a set instead of a map (shrinking left one character at a time until the repeat is gone, rather than jumping straight to the right position) is also correct and still $O(n)$ overall, since each character enters and leaves the set at most once, but it does more per-step work whenever the repeat is far behind the current position.

Complexity

Time: $O(n)$, since right advances once per character and left never moves backward, so together they make at most $O(n)$ total steps. Space: $O(\min(n, \text{alphabet size}))$ for the map.

Edge cases

• Empty string: returns 0.
• All identical characters (e.g., "bbbbb"): returns 1.
• All unique characters: returns the full length of the string.
• A single character: returns 1.