Algorithmic Problem-Solving and Data Structure Selection Questions

Direct answer

Use the Boyer-Moore Voting algorithm: walk the array once keeping a single candidate value and a counter. Seeing the candidate again increments the counter; seeing anything else decrements it; when the counter hits zero the next element becomes the new candidate. Because a majority element (appearing more than n/2 times) exists, whatever candidate survives the final pass is guaranteed to be it, in $O(n)$ time and $O(1)$ extra space.

Structured elaboration

Approach. Think of every non-candidate occurrence as "canceling" one occurrence of the current candidate (counter decrements to 0, we drop it and pick a fresh candidate). The algorithm never allocates a counting map; it only tracks one value and one integer.

def majority_element(nums):
    """
    Boyer-Moore Voting: O(n) time, O(1) space.
    Returns the element appearing more than n/2 times (assumed to exist).
    """
    candidate = None
    count = 0
    for x in nums:
        if count == 0:
            candidate = x
            count = 1
        elif x == candidate:
            count += 1
        else:
            count -= 1
    return candidate

Why cancellation still leaves the majority standing. Pair up every occurrence of a non-majority value with one occurrence of a different value in the same "cancellation." Each such pair removes one majority occurrence and one non-majority occurrence at most (a cancellation only fires when the incoming value differs from the current candidate). Since the majority value appears more than $n/2$ times, even in the worst case where every single non-majority occurrence gets paired against a majority occurrence, there are still leftover majority occurrences that were never paired away (there are not enough non-majority elements to cancel all of them). Those survivors are exactly what keeps the counter from reaching zero on the majority value permanently, so the candidate the loop ends on must be the majority element.

Worked example

Trace nums = [2, 2, 1, 1, 1, 2, 2] (n = 7, majority threshold > 3.5, so 2 appearing 4 times is the majority):

print(majority_element([2, 2, 1, 1, 1, 2, 2]))

Output: 2, matching the trace: the candidate flips to 1 briefly at step 5 once the counter is fully canceled, but the final incoming 2's push it back and the loop ends on candidate = 2, the true majority.

Trade-offs & pitfalls

Key points

• The algorithm only guarantees correctness when a majority element (strictly more than n/2 occurrences) is known to exist; without that guarantee the final candidate can be any element, so a verification second pass is required if the existence of a majority is not already given.
• It generalizes (with more candidate/counter slots) to finding elements appearing more than n/3 times, but the proof gets more involved because more than one such element can exist simultaneously.
• It is well suited to one-pass, low-memory streaming summaries: large log or partition scans that need a frequent-item candidate without storing a full frequency map. It composes across partitions too (run it per partition, then verify candidates against the merged data), which fits reduce-style pipelines.

Complexity

• Time: $O(n)$, a single linear pass.
• Space: $O(1)$, two scalar variables regardless of input size.

Edge cases

• Single-element array: the loop returns that element immediately, correctly (it is trivially the majority).
• No true majority exists: the algorithm still returns some element, but it is not guaranteed to be correct; add a second counting pass if the existence of a majority is not guaranteed by the problem statement.
• All elements identical: counter only ever increments, returns that value.

Direct answer

For an array of length n, the smallest missing positive integer can never be larger than n + 1, so only values in [1, n] are ever candidates worth tracking. Cyclic sort exploits this bound by using the array itself as the presence table: repeatedly swap each value v in [1, n] to its "home" index v - 1 until every slot either holds its own correct value or holds something outside [1, n]. A single final scan then finds the first index whose value does not match, that index plus one is the answer, which is why this needs no separate hash set at all.

Structured elaboration

Why a hash set works but costs O(n) space

The direct approach is to insert every value into a hash set, then probe 1, 2, 3, ... until one is missing. That is correct and $O(n)$ time, but the hash set itself is $O(n)$ extra space, on top of the input array.

How cyclic sort gets the same information for free

Since the answer is guaranteed to be at most n + 1, any value outside [1, n] (zero, negative, or greater than n) is irrelevant, and any relevant value v has exactly one "correct" home, index v - 1. Instead of a separate table recording "have I seen this value," the algorithm repeatedly places each in-range value into its home slot by swapping, using the array's own indices as the presence table. After this pass, nums[i] == i + 1 for every index that is genuinely "present and correctly placed"; the first index that breaks this pattern is exactly the first missing positive integer, no auxiliary memory needed because the information that a hash set would store is now encoded directly in where each value physically sits.

The swap loop's subtlety

At each index i, keep swapping nums[i] into its home index as long as three conditions hold: the value is in range (1 <= v <= n), and the slot it wants to go to does not already hold that exact value (nums[v - 1] != v), the second check is what prevents an infinite loop on duplicate values, once a value is already correctly home, there is nothing left to do with a duplicate of it.

Worked example

def first_missing_positive(nums):
    n = len(nums)
    i = 0
    while i < n:
        v = nums[i]
        if 1 <= v <= n and nums[v - 1] != v:
            nums[i], nums[v - 1] = nums[v - 1], nums[i]
        else:
            i += 1
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

print(first_missing_positive([3, 4, -1, 1]))
print(first_missing_positive([1, 2, 0]))
print(first_missing_positive([7, 8, 9, 11, 12]))
print(first_missing_positive([1, 1]))

This prints:

2
3
1
2

Tracing [3, 4, -1, 1]: nums[0]=3 wants home index 2; swap gives [-1, 4, 3, 1]. nums[0]=-1 is out of range, advance. nums[1]=4 wants home index 3; swap gives [-1, 1, 3, 4]. nums[1]=1 wants home index 0; swap gives [1, -1, 3, 4]. nums[1]=-1 out of range, advance. nums[2]=3 is already home (nums[2] == 3), advance. nums[3]=4 already home, advance. Final array [1, -1, 3, 4]; scanning, index 1 has value -1 != 2, so the answer is 2, matching the printed result.

Key points

• The nums[v - 1] != v guard is what makes the swap loop terminate on arrays with duplicates; without it, two equal in-range values would swap forever.
• Values outside [1, n] (non-positive, or greater than n) are left exactly where they are; they can never be the answer, so there is no need to relocate them.
• The final linear scan is what actually reads off the answer; the swap pass only arranges the array so that scan is meaningful.

Complexity

Time: $O(n)$ amortized. Each swap places at least one value into its correct home permanently (a value is never moved out of a slot it is already correctly sitting in), so across the whole pass, the total number of swaps is bounded by $n$, even though a single index's while-style repositioning can trigger more than one swap before i advances.
Space: $O(1)$ extra, the rearrangement happens entirely within the input array.

Edge cases

• Empty array: the loop body never runs, and the final scan is also empty, returning n + 1 = 1.
• All non-positive values: nothing is ever swapped (nothing is in range), and the final scan immediately finds index 0 mismatched, returning 1.
• All values already 1..n in order: no swaps needed, final scan finds no mismatch, returns n + 1.
• Duplicate values, as traced above: handled by the nums[v - 1] != v guard.

Trade-offs & pitfalls

The most common bug is omitting the nums[v - 1] != v check and instead just checking 1 <= v <= n, which causes an infinite loop the moment a duplicate value's home slot already holds that same value. Another common mistake is forgetting that values greater than n must be left alone rather than causing an out-of-bounds swap attempt; the range check on v guards against both. Compared to the hash-set approach, cyclic sort is a legitimate net win in space with the same time complexity, but it does mutate the input array in place, which is a real trade-off if the caller needs the original order preserved and cannot tolerate the destructive rearrangement.

Direct answer

Push every opening bracket onto a stack. On a closing bracket, it must match whatever opener currently sits on top of the stack; if it does not, or the stack is already empty, the string is invalid. After the scan, the string is valid only if the stack is empty, meaning every opener found a partner. This runs in $O(n)$ time and $O(n)$ space.

Structured elaboration

A stack models "the most recently opened, still-unclosed bracket" exactly, because it is last-in-first-out (LIFO): whichever opener was pushed most recently is always the one that must be closed next, and that is precisely what sits on top. Checking a closer against the top of the stack is an $O(1)$ lookup through a small mapping () pairs with (, ] with [, } with {).

Counting bracket types separately (how many ( versus how many )) is not enough: a string can have perfectly equal counts of every bracket type and still be invalid because the nesting order is wrong, for example ([)]. Only a structure that remembers order, like a stack, can catch that.

Worked example

def is_valid_brackets(s: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    stack: list[str] = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
    return not stack


if __name__ == "__main__":
    tests = ["()[]{}", "(]", "([)]", "{[]}"]
    print([is_valid_brackets(t) for t in tests])

Running this prints [True, False, False, True]. Trace ([)]: push (, push [, then see ); the top of the stack is [, which does not pair with ), so the function returns False immediately, even though the overall bracket counts are balanced.

Complexity

Time: $O(n)$, one pass over the string doing $O(1)$ work per character.
Space: $O(n)$ worst case, since a string of all opening brackets pushes every character onto the stack before the scan ends.

Edge cases

• Empty string: the stack never receives a push, so it is empty at the end and the function correctly returns True.
• A lone unmatched opening bracket at the very end: the stack is non-empty when the scan finishes, so the final not stack check (not just the per-character comparisons) is what catches it.
• A closing bracket with nothing open: stack is empty when a closer arrives, so the code must check not stack before indexing stack[-1], or it raises instead of returning False cleanly.

Trade-offs & pitfalls

Using a single stack with a pairs mapping generalizes cleanly to any number of bracket types; writing a separate counter per bracket type cannot detect ordering violations no matter how many counters you add.

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

Once negative numbers are allowed, a sliding window cannot solve "longest
contiguous subarray summing to exactly k" because growing or shrinking the
window no longer moves the running sum monotonically in one direction, so
there is no reliable rule for when to expand versus contract. The fix is to
track prefix sums (the running total from the start of the array up to each
index) in a hashmap that records the earliest index each prefix sum was
seen at; whenever the current prefix sum minus k has been seen before, the
subarray between that earlier index and now sums to exactly k, and keeping
the earliest occurrence maximizes that subarray's length. This runs in O(n)
time and O(n) space.

Structured elaboration

Why sliding window needs non-negative numbers. A sliding window relies on
the window's sum changing monotonically as you move its boundaries: with only
non-negative numbers, expanding the right edge can only increase the sum, and
shrinking the left edge can only decrease it, so there is a clean rule
("if the sum is too big, shrink from the left"). With negative numbers, adding
an element could decrease the sum, so a window that currently sums to more
than k might still contain a valid subarray of exactly k further to the
right, and shrinking based on "sum too high" can skip right past it. There is
no monotonic invariant left to drive the two pointers.

Prefix-sum reasoning. Define $\text{prefix}[i] = \sum_{j=0}^{i-1} nums[j]$
with $\text{prefix}[0] = 0$ (the empty prefix). The sum of the subarray from
index $l$ to index $r$ inclusive is $\text{prefix}[r+1] - \text{prefix}[l]$.
For the sum to equal k, you need $\text{prefix}[r+1] - \text{prefix}[l] = k$,
i.e. $\text{prefix}[l] = \text{prefix}[r+1] - k$. So at each position, you
are looking for an earlier index whose prefix sum equals "current prefix sum
minus k." A hashmap from prefix-sum-value to the earliest index it occurred at
answers that lookup in O(1) average time.

Why earliest occurrence, not count or latest. This question asks for the
longest qualifying subarray, and a longer subarray corresponds to a smaller
starting index for a fixed ending index. So the hashmap should store, for each
prefix-sum value, only the first (smallest) index it was seen at, and never
overwrite it, since an earlier start with the same prefix sum always yields a
subarray at least as long as a later one would. (Contrast this with the
related but different problem "count how many subarrays sum to k," which
instead stores counts per prefix sum, since every earlier occurrence
contributes a separate valid subarray to the count, not just the longest one.)

Worked example

from typing import List

def longest_subarray_sum_k(nums: List[int], k: int) -> int:
    first_seen = {0: -1}  # prefix sum -> earliest index it was seen at
    prefix = 0
    best = 0
    for i, x in enumerate(nums):
        prefix += x
        need = prefix - k
        if need in first_seen:
            best = max(best, i - first_seen[need])
        if prefix not in first_seen:
            first_seen[prefix] = i
    return best

print(longest_subarray_sum_k([1, -1, 5, -2, 3], 3))  # [1, -1, 5, -2] sums to 3, length 4
print(longest_subarray_sum_k([-2, -1, 2, 1], 1))      # [-1, 2] sums to 1, length 2
print(longest_subarray_sum_k([1, 2, 3], 6))           # whole array, length 3
print(longest_subarray_sum_k([1, 2, 3], 100))         # no subarray sums to 100

Output (verified by running this exact code):

4
2
3
0

Tracing the first case: prefix sums (with the initial 0 at index -1) are
0, 1, 0, 5, 3, 6 at indices -1, 0, 1, 2, 3, 4. At index 3 (prefix sum 3),
need = 3 - 3 = 0, which was first seen at index -1, giving a candidate
length of 3 - (-1) = 4, matching the subarray [1, -1, 5, -2].

Key points

• Store first-seen index per prefix sum, not a count, since the goal is
  maximum length, not number of matches.
• Seed the map with {0: -1} so a subarray starting at index 0 is handled
  without a special case.
• Works identically whether or not the array contains negative numbers,
  since it never relies on monotonicity, only on hashmap lookups.

Complexity

Time: $O(n)$, one pass, each hashmap operation averages O(1).
Space: $O(n)$ in the worst case, one entry per distinct prefix sum value.

Edge cases

• Empty array: returns 0 (the loop never executes).
• No subarray sums to k: returns 0 (the initial value, never updated).
• The entire array sums to k: correctly captured because prefix[0] = 0 is
  seeded before the loop starts.
• All zeros with k = 0: every prefix sum is 0, but only the first occurrence
  is ever stored, so the length computed against the earliest zero (index -1)
  correctly gives the full array length rather than needing per-position logic.

Trade-offs & pitfalls

• The most common wrong turn is reaching for a sliding window out of habit
  (it is the right tool for the non-negative version of this problem, and
  candidates often try to patch it with ad hoc shrink rules for negative
  numbers, which do not generalize and fail on adversarial inputs).
• A second common bug is storing prefix sums with dict[prefix] = i on every
  iteration instead of if prefix not in first_seen, which silently swaps
  "longest subarray" for "shortest," since it keeps overwriting the earliest
  index with a later one.
• This is a different problem from "count the number of subarrays summing to
  k": that variant stores a running count per prefix sum and adds the count
  at each step, rather than storing only the first index. Reusing that
  count-based solution here would answer a different question than the one
  asked (a total count of matching subarrays, not the length of the longest
  one).