Algorithmic Problem-Solving and Data Structure Selection Questions

Direct answer

An array gives $O(1)$ index-based random access and is cache-friendly, because its elements sit in one contiguous block of memory that the CPU can pull into cache together. A singly linked list gives $O(1)$ insertion or deletion once you already hold a reference to the splice point, at the cost of $O(n)$ traversal to reach any given position and extra per-node memory overhead. For a workload that is mostly random reads, pick an array (or dynamic array); for a workload that is mostly insertions and deletions in the middle where you already hold the relevant node reference, a linked list wins.

Structured elaboration

The contiguous-versus-non-contiguous memory allocation framing is exactly this same dimension stated differently: contiguous storage is what gives arrays both their cache locality and their index arithmetic; non-contiguous, per-node allocation is what gives linked lists their cheap local splicing at the cost of locality. In a garbage-collected (GC) language, this also affects collector pressure: many small linked-list node objects mean more individual objects for the garbage collector to track and scan, compared to one contiguous array allocation holding the same data.

Worked example

Consider inserting a new element in the middle of a ten-item collection, repeatedly, as items are typed into an editable list. With an array, each insertion must shift every element after the insertion point one slot over, an $O(n)$ cost per insertion regardless of whether you know exactly where to insert. With a singly linked list, if the editing position is tracked by an existing reference to the node just before it (as a cursor would be in a text-editing context), each insertion is a pure $O(1)$ relink; but if you only know the position as an index and must first walk from the head to reach it, the linked list gains nothing over the array for that access, since both now cost $O(n)$ overall. This is why the deciding factor is not "array versus linked list" in the abstract, but whether the workload naturally hands you a reference to the splice point or only an index.

Trade-offs & pitfalls

Assuming "$O(1)$ insertion" for a linked list means fast in absolute terms is a common mistake: reaching the splice point is usually the dominant cost unless a reference to it is already in hand from a prior traversal or an auxiliary index. Ignoring the per-element memory overhead ratio is another: a linked list of single integers can use several times the memory of the equivalent array, because the pointer overhead per node is fixed regardless of how small the stored value is. Modern hybrid structures such as a deque (double-ended queue) or a rope address parts of this trade-off by chunking data into contiguous blocks rather than choosing purely one extreme or the other.

Direct answer

A stack is last-in-first-out (LIFO): the most recently added item comes out first. A queue is first-in-first-out (FIFO): items come out in the order they arrived. Use a stack when you need to undo or backtrack in reverse arrival order, such as a browser's back button or a function call stack; use a queue when arrival order must be preserved, such as a task scheduler or a print spooler. You can build a queue out of two stacks: push is $O(1)$ worst case, and pop is amortized (averaged over a sequence of operations) $O(1)$ because each element only ever moves between the two stacks once over its lifetime.

Structured elaboration

Queue from two stacks. Keep an in_stack that absorbs pushes and an out_stack that serves pops. Pushing always goes to in_stack in $O(1)$. When a pop or peek is requested and out_stack is empty, drain all of in_stack into out_stack; this reverses the order, so the oldest element (which was at the bottom of in_stack) ends up on top of out_stack, ready to be returned first.

Why the amortized argument holds. Use the aggregate method: over any sequence of n operations, each element is pushed onto in_stack exactly once (cost 1), moved from in_stack to out_stack at most once in its lifetime (cost 1), and popped from out_stack exactly once (cost 1). No element is ever moved more than that, so the total work across the whole sequence is bounded by a constant multiple of n, which is what "amortized $O(1)$ per operation" means, even though any single pop that triggers the drain costs $O(n)$ by itself.

Worked example

class QueueFromStacks:
    def __init__(self):
        self.in_stack: list[int] = []
        self.out_stack: list[int] = []

    def push(self, x: int) -> None:
        self.in_stack.append(x)

    def _transfer(self) -> None:
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())

    def pop(self) -> int:
        self._transfer()
        return self.out_stack.pop()

    def peek(self) -> int:
        self._transfer()
        return self.out_stack[-1]


if __name__ == "__main__":
    q = QueueFromStacks()
    q.push(1)
    q.push(2)
    q.push(3)
    seq = [q.pop(), q.peek()]
    q.push(4)
    seq += [q.pop(), q.pop(), q.pop()]
    print(seq)

Running this prints [1, 2, 2, 3, 4]. The first pop() triggers a drain (in_stack [1,2,3] becomes out_stack [3,2,1], top popped is 1); peek() then reads 2 for free from the already-drained out_stack; pushing 4 goes straight to in_stack without disturbing out_stack; the remaining pops (2, 3) come from out_stack, and the last pop (4) triggers a second drain since out_stack had emptied.

Complexity

Space: $O(n)$ total across the two internal stacks, since every pushed element lives in exactly one of them at any time (no extra space is used beyond storing the n elements themselves).

Edge cases

• Calling pop() or peek() on an empty two-stack queue: in the reference implementation, _transfer() leaves out_stack empty when both stacks are empty, so pop()'s self.out_stack.pop() and peek()'s self.out_stack[-1] both raise an unhandled IndexError instead of failing cleanly. Guard this explicitly, for example if not self.in_stack and not self.out_stack: raise IndexError("pop from empty queue") before touching out_stack, so the caller gets a clear, intentional signal rather than an incidental one.
• A single push followed immediately by a pop: the drain moves that one element from in_stack to out_stack and it is returned, leaving both stacks empty again, which is the state the empty-queue guard above must handle correctly on the next call.

Trade-offs & pitfalls

The most common confusion is treating "amortized" as "always fast": a single pop can still cost $O(n)$ when it triggers the drain. Note the asymmetry with building a stack out of a single queue by rotating on every push (dequeue-then-requeue the previous elements so the newest sits at the front): that rotation happens on every single push, not just occasionally, so it is genuinely $O(n)$ per push with no amortization to appeal to, unlike the two-stack construction above where the expensive transfer is rare and each element only ever pays for it once.

Direct answer

"In-place" and "$O(1)$ extra space" are usually used interchangeably to mean an algorithm transforms its input using only a constant amount of auxiliary memory beyond the input and output themselves. Recursion complicates that accounting: every recursive call adds a stack frame (its arguments, local variables, and a return address), so a recursive function that touches no second array or list can still use $O(n)$ extra memory through the call stack alone, memory that is easy to forget because it never shows up as an explicit variable in the code.

Structured elaboration

What counts as "extra" space

The convention is to count space beyond the input and the required output. A function that reverses an array by swapping elements in the same array is $O(1)$ extra space by this convention, even though the array itself is $O(n)$, because that space was already accounted for as the input. Auxiliary structures the algorithm allocates on top of that, a second array, a hash map, or the call stack, are what get charged against the space bound.

How recursion hides space in the call stack

Each recursive call is not free: the runtime pushes a new stack frame holding that call's parameters and local variables, and does not pop it until the call returns. A recursive function with depth d therefore uses $O(d)$ stack space regardless of what its explicit variables look like. For a tree of height h, naive recursion is $O(h)$ stack space, which is $O(\log n)$ for a balanced tree but $O(n)$ for a completely skewed one; for a straightforward recursive Fibonacci, the recursion depth (and thus stack space) is $O(n)$ even though each individual call only holds a couple of integers.

Three ways to convert hidden stack space into genuine O(1) space

1. Threading (Morris traversal): temporarily rewrite null-looking child pointers to point back up the tree, walk using those threads instead of recursing, then restore the original structure. No stack, no recursion, just pointer rewrites.
2. Iterative looping with an accumulator: replace a linear recursion (like naive Fibonacci) with a loop carrying only the last one or two values needed, discarding everything else.
3. Recurse on the smaller side, loop on the larger (tail-call style elimination): for divide-and-conquer algorithms like quicksort, always making the recursive call on the smaller partition bounds the recursion depth by $O(\log n)$ even in the worst case, because the smaller side can be at most half the remaining size at each level.

Worked example

# 1) Morris inorder traversal: O(1) extra space, no recursion, no explicit stack
def morris_inorder(root):
    out = []
    cur = root
    while cur:
        if not cur.left:
            out.append(cur.val)
            cur = cur.right
        else:
            pred = cur.left
            while pred.right and pred.right is not cur:
                pred = pred.right
            if not pred.right:
                pred.right = cur          # thread to come back later
                cur = cur.left
            else:
                pred.right = None         # remove the thread, tree restored
                out.append(cur.val)
                cur = cur.right
    return out

# 2) Iterative Fibonacci: O(1) extra space, versus O(n) recursion-stack depth for the naive recursive version
def fib(n):
    if n < 2:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# 3) Quicksort: recurse on the smaller partition, loop on the larger, bounding stack depth to O(log n)
def partition(arr, lo, hi):
    pivot = arr[hi]
    i = lo
    for j in range(lo, hi):
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]
    return i

def quicksort(arr, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    while lo < hi:
        p = partition(arr, lo, hi)
        if p - lo < hi - p:
            quicksort(arr, lo, p - 1)
            lo = p + 1
        else:
            quicksort(arr, p + 1, hi)
            hi = p - 1

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

n = {v: Node(v) for v in range(1, 8)}
n[4].left, n[4].right = n[2], n[6]
n[2].left, n[2].right = n[1], n[3]
n[6].left, n[6].right = n[5], n[7]

print(morris_inorder(n[4]))
print([fib(i) for i in range(10)])

import random
random.seed(5)
original = [random.randint(0, 100) for _ in range(50)]
arr = original[:]
quicksort(arr)
print("quicksort matches sorted():", arr == sorted(original))

Running this prints the Morris traversal [1, 2, 3, 4, 5, 6, 7] (the tree's inorder sequence, confirming the temporary threads were fully removed and the structure is intact), the Fibonacci sequence [0, 1, 1, 2, 3, 5, 8, 13, 21, 34], and quicksort matches sorted(): True, confirming the in-place quicksort produces the same order as Python's own sorted() on the same seeded input.

Key points

• Morris traversal never recurses and never allocates an explicit stack, it reuses the tree's own null pointers as temporary bookkeeping, then undoes that bookkeeping before moving on.
• The iterative Fibonacci keeps exactly two rolling values (a, b) instead of a call stack that grows with n.
• "Recurse smaller, loop larger" is not just a performance tweak, it is what guarantees the quicksort recursion depth is $O(\log n)$ even on adversarial input, since the recursive branch always operates on a piece at most half the current size.

Complexity notes

Morris traversal: $O(n)$ time (each edge is traversed a bounded number of times to set up and tear down threads), $O(1)$ extra space. Naive recursive Fibonacci: $O(2^n)$ time and $O(n)$ stack space (depth n); the iterative version is $O(n)$ time and $O(1)$ space. Naive quicksort recursion: $O(n)$ worst-case stack depth (already-sorted input recursing on the full remaining range each time); recursing on the smaller side bounds it to $O(\log n)$ worst case.

Trade-offs & pitfalls

A recursive solution that "looks" $O(1)$ space because it declares no arrays is a common trap, always ask separately what the maximum recursion depth is and whether the language or runtime performs tail-call optimization (most mainstream production runtimes, including CPython, do not, so a "tail recursive" Python function still accumulates real stack frames). Morris traversal trades a temporary, carefully-undone mutation of the tree's own pointers for the stack savings, which is a real complexity cost in the code even though the asymptotic space bound improves, and it is unsafe on a tree that might be read concurrently while being traversed, since the tree is briefly in a modified state.

Direct answer

Advance one pointer (slow) one step at a time and another (fast) two steps at a time. If the list has no cycle, fast reaches the end first and you can report there is none. If it does have a cycle, fast eventually laps slow and the two meet somewhere inside it. Once they meet, restarting one pointer at the head and advancing both pointers one step at a time makes them meet again exactly at the cycle's start. All of this uses $O(1)$ extra space, no visited set required.

Structured elaboration

Why meeting implies a cycle, and why no meeting implies no cycle. With no cycle, fast strictly gains ground toward a null terminator every step and reaches it in at most n/2 steps; it can never occupy the same node as slow without a cycle to loop back through. Once both pointers are inside a cycle, fast closes the gap to slow by exactly one node per step, because fast gains two steps of distance while slow gains one, a net closing rate of one per step. Since the gap can never exceed the cycle's length, they are guaranteed to meet within one full lap of the cycle.

Why the meeting point locates the cycle's start. Let a be the distance from the head to the cycle's start, c be the cycle's length, and b be the distance from the cycle's start to the meeting point, with $0 \le b < c$. By the time they meet, slow has traveled a + b steps and fast has traveled exactly twice that, but fast has also gone around the cycle some whole number of extra laps $n \ge 1$:

So a and (c - b) differ by a whole number of cycle lengths, meaning a pointer walking one step at a time from the head, and a pointer walking one step at a time from the meeting point, land on the same node after exactly a steps: the cycle's start.

Related applications of the same fast/slow pattern. Removing the n-th node from the end of a list uses the same shape without any cycle involved: advance one pointer n steps first, then move both pointers together; when the front pointer reaches the end, the trailing pointer sits exactly at the node to remove. Finding a duplicate number hidden in an array reframes the array itself as an implicit linked list, where the value stored at each index tells you which index to visit next; a repeated value forces two different positions to point at the same next index, creating a cycle in that implicit list, which Floyd's tortoise-and-hare detects exactly the way it detects a cycle here.

Worked example

class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next


def detect_cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            ptr = head
            while ptr is not slow:
                ptr = ptr.next
                slow = slow.next
            return ptr
    return None


if __name__ == "__main__":
    nodes = [Node(i) for i in range(5)]  # values 0,1,2,3,4
    for i in range(4):
        nodes[i].next = nodes[i + 1]
    nodes[4].next = nodes[2]  # cycle back into node with value 2
    start = detect_cycle_start(nodes[0])
    print(start.val)

Running this prints 2. In the derivation's terms: a = 2 (two steps from the head, value 0, to the cycle's start, value 2), c = 3 (the cycle 2 to 3 to 4 back to 2 has three edges), and the two pointers first meet at the node with value 3, so b = 1 (one step from the cycle's start to that meeting point). Checking the identity: c - b = 3 - 1 = 2, which equals a, confirming the derivation against this concrete run.

Complexity

Time: $O(n)$. The pointers meet within one full lap of the cycle once both are inside it, and finding the cycle's start afterward takes at most another full lap; both phases are bounded by a constant multiple of the list's length n.
Space: $O(1)$, since only the slow and fast pointers (and later ptr) are held, with no visited set.

Edge cases

• Empty list (head is None): fast is None immediately, so the loop never runs and the function correctly returns no cycle.
• Single node with no self-link: fast.next is None on the first check, so the loop exits immediately with no cycle detected.
• Single node that cycles to itself: slow and fast both land back on that same node on the first iteration, correctly reporting it as the cycle's start.

Trade-offs & pitfalls

A common bug is comparing pointer values instead of pointer identity; when list values can repeat, slow.val == fast.val can be true without slow and fast being the same node, so the check must be slow is fast.

Direct answer

Quicksort is in-place with average time $O(n \log n)$ but a worst case of $O(n^2)$ on an unlucky pivot sequence; merge sort and heap sort both guarantee $O(n \log n)$ in every case. Merge sort needs $O(n)$ extra space and is stable; heap sort needs only $O(1)$ extra space but is not stable; quicksort's extra space is $O(\log n)$ for the recursion stack on average, but can grow to $O(n)$ in the worst case. For nearly-sorted data, pick an adaptive sort such as TimSort (the hybrid merge/insertion sort behind Python's and Java's built-in sort); when a guaranteed worst case matters more than average speed, pick heap sort or merge sort, never plain quicksort.

Structured elaboration

Nearly-sorted input

Plain quicksort and plain top-down merge sort are not adaptive: both do the same $O(n \log n)$ work regardless of how ordered the input already is. TimSort is: it scans for existing ascending or descending runs, extends and merges them, and degrades toward close to linear work as the input approaches already-sorted. For nearly-sorted data, reach for TimSort (or, if you must hand-roll something, a natural merge sort) rather than a textbook quicksort or merge sort.

Worst-case guarantees matter more than average speed

Both heap sort and merge sort guarantee $O(n \log n)$ in every case; quicksort does not, no matter how the pivot is chosen, because an adversary (or, unintentionally, already-sorted or already-reverse-sorted input under a naive pivot rule) can always construct a sequence that degrades a fixed pivot strategy to $O(n^2)$. Choose heap sort when the extra $O(n)$ memory merge sort needs is unavailable and stability is not required; choose merge sort when stability is required alongside the worst-case guarantee and the memory budget allows it.

Two side notes worth naming explicitly

• Parallelization on resource-constrained devices: merge sort's divide phase maps cleanly onto independent worker threads or cores (each half sorts independently before a merge step), which is attractive on a multi-core mobile device; the cost is the extra O(n) buffer merge sort needs, which is a real constraint on memory-limited hardware. Quicksort's partitions can also be sorted concurrently, but partition sizes are unpredictable (a skewed pivot gives one thread almost all the work), so load balancing is harder to reason about.
• Cross-language floating-point sort determinism: when the same data is sorted by comparator across different languages or platforms, an unstable sort's tie-breaking for equal keys is unspecified and can differ, and NaN comparisons under IEEE 754 floating point are neither less-than nor greater-than any value, which breaks the total-order assumption most sort implementations rely on. If reproducible ordering across systems matters (for example, deterministic test fixtures or replaying a pipeline), use a stable sort and either exclude or explicitly place NaNs, rather than relying on the default comparator.

Worked example

A concrete way to see the worst case: implement a plain quicksort that always pivots on the last element, and run it on an already-sorted array.

def quicksort_last_pivot_count(a: list[int]) -> int:
    """
    Naive quicksort that always pivots on the last element.
    Returns the number of comparisons performed (element-to-pivot checks).
    """
    comparisons = 0

    def sort(lo: int, hi: int) -> None:
        nonlocal comparisons
        if lo >= hi:
            return
        pivot = a[hi]
        store = lo
        for i in range(lo, hi):
            comparisons += 1
            if a[i] < pivot:
                a[i], a[store] = a[store], a[i]
                store += 1
        a[store], a[hi] = a[hi], a[store]
        sort(lo, store - 1)
        sort(store + 1, hi)

    sort(0, len(a) - 1)
    return comparisons


if __name__ == "__main__":
    for n in [6, 10, 20]:
        already_sorted = list(range(n))
        c = quicksort_last_pivot_count(already_sorted)
        expected = n * (n - 1) // 2
        print(f"n={n}: comparisons={c}, n(n-1)/2={expected}")

Running this prints:

n=6: comparisons=15, n(n-1)/2=15
n=10: comparisons=45, n(n-1)/2=45
n=20: comparisons=190, n(n-1)/2=190

Every partition step on already-sorted input with a last-element pivot puts everything on one side, so the recursion depth is n and the total comparisons are exactly $n(n-1)/2 = \Theta(n^2)$, confirmed by the counts matching the closed-form prediction at every size tested. A randomized or median-of-three pivot choice avoids this specific failure mode but does not eliminate the worst case in general, only make it exponentially unlikely to hit by chance.

Trade-offs & pitfalls

The most common wrong turn is treating quicksort as unconditionally the fastest choice: on already-sorted or reverse-sorted input under a naive pivot rule, it is the slowest of the three by an order of magnitude, as the worked example shows directly. A second common gap is forgetting that merge sort's memory cost is real: at large enough n, the O(n) auxiliary buffer competes with other memory pressure, which is exactly why external (disk-based) sorting is built on multi-way merge rather than quicksort, since merge sort's sequential access pattern suits disk or network I/O far better than quicksort's more random access pattern. A third trap is ignoring stability when it silently matters: if you sort by a secondary key after already sorting by a primary key, only a stable sort preserves the primary ordering among equal secondary keys; using an unstable sort there produces a result that looks correct on small examples but is wrong in general.