Algorithmic Problem-Solving and Data Structure Selection Questions

Direct answer

On a sorted array, start one pointer at the beginning and one at the end, and move them toward each other based on how the current pair's sum compares to the target: this finds the pair in one linear pass using O(1) extra space, no hash map required. Sorted order is exactly what makes the hash map unnecessary, since it tells you in which direction to move without needing to remember every value you have already seen. The same converging-pointer idea, applied to two arrays instead of one target sum, gives you their intersection: advance whichever array currently has the smaller value.

Structured elaboration

Two-sum on a sorted array: maintain the invariant that every valid pair still under consideration lies between left and right. If arr[left] + arr[right] == target, you are done. If the sum is too small, arr[left] cannot be part of any valid pair with anything to its left (everything to the left is even smaller, making the sum only smaller), so advance left. If the sum is too large, by the same logic on the other side, retreat right. Because the array is sorted, this monotonic narrowing never skips over a valid pair: if one exists, it is found.

Why sorted order removes the need for a hash map: an unsorted two-sum needs a hash map to remember "have I seen the complement of this value yet," since there is no way to know which direction to search without that memory. Sorted order replaces that memory with structure: the comparison arr[left] + arr[right] versus target alone tells you which pointer must move, with no need to have seen anything before.

Adapting to intersect two sorted arrays: instead of pointers converging toward each other, they move in the same direction, each independently, starting both at index 0. Compare the current elements of each array: if equal, that value is in the intersection, and advance both; if array a's current element is smaller, it cannot match anything later in b (which is only larger from here), so advance a; otherwise advance b. This is the same "sorted order tells you which pointer to move, so no hash map is needed" idea, just applied across two sequences instead of within one.

Worked example

Two-sum, sorted array:

def two_sum_sorted(arr: list[int], target: int) -> tuple[int, int]:
    left, right = 0, len(arr) - 1
    while left < right:
        s = arr[left] + arr[right]
        if s == target:
            return left, right
        if s < target:
            left += 1
        else:
            right -= 1
    return -1, -1

arr = [2, 7, 11, 15]
print(two_sum_sorted(arr, 18))

Running this prints:

(1, 2)

arr[1] + arr[2] = 7 + 11 = 18.

Sorted-array intersection:

def intersect_sorted(a: list[int], b: list[int]) -> list[int]:
    i, j = 0, 0
    result = []
    while i < len(a) and j < len(b):
        if a[i] == b[j]:
            result.append(a[i])
            i += 1
            j += 1
        elif a[i] < b[j]:
            i += 1
        else:
            j += 1
    return result

a = [1, 2, 2, 3, 5, 8]
b = [2, 2, 3, 6, 8, 9]
print(intersect_sorted(a, b))

Running this prints:

[2, 2, 3, 8]

Key points

• Both algorithms use the same underlying idea: sorted order lets a single comparison decide which pointer must move, replacing the memory a hash map would otherwise need to provide.
• The intersection version keeps every duplicate (two 2s appear in both inputs, so two 2s appear in the output); deduplicating the result, if needed, is a separate, trivial step.

Complexity

for the sorted two-sum (n is the array length), and

for the intersection of arrays of length n and m, since each pointer advances at most once per element and never backtracks.

Edge cases

• Empty or single-element array: two_sum_sorted correctly returns (-1, -1) since the while left < right loop never runs.
• No valid pair exists: the loop exits naturally when left meets right, returning (-1, -1).
• Negative numbers: handled correctly, since the comparison s < target / s > target does not depend on sign.
• One array is empty in the intersection case: the while loop's length check exits immediately, correctly returning an empty result.

Trade-offs & pitfalls

Reaching for a hash map here works too (build a set of one array's values in $O(n)$ time and $O(n)$ space, then scan the other), and is actually necessary if the input is not sorted and sorting it first is not acceptable (for example, if the original order must be preserved in the output); but given already-sorted input, that hash map is pure overhead, since the sort order already encodes everything the hash map would tell you. A common mistake is trying to adapt the sum-target converging-pointer pattern directly to intersection by starting the second pointer at the end instead of at the start: intersection is fundamentally a same-direction scan (both arrays are being consumed left to right looking for equal elements), not a converging one (which relies on one array's values increasing while the other's decrease, a relationship two independent sorted arrays don't have with each other).

Direct answer

Reach for a self-balancing tree over a hash table specifically when ordered iteration, range queries, or a worst-case (not just average-case) time guarantee is needed; a hash table's O(1) average lookup has no built-in notion of order and can degrade to O(n) in the worst case, while a balanced tree guarantees O(log n) for every operation and keeps keys in sorted order at all times. When only point lookups are ever needed, and order, range, and worst-case behavior never matter, the balancing overhead of a tree buys nothing and a hash table is strictly cheaper.

Structured elaboration

What a hash table fundamentally cannot give you

• Ordered iteration: walking a hash table's contents comes out in whatever order the hash function and internal layout produced, not sorted order; a balanced tree's in-order traversal is always sorted.
• Range queries: "give me every key between A and B," or "find the next key after X" (predecessor/successor), requires either scanning the entire hash table or maintaining a second sorted structure; a balanced tree answers both in O(log n + m), where m is the number of results returned.
• Worst-case guarantees: a hash table's O(1) average case relies on the hash function spreading keys evenly. A pathological input, or an attacker deliberately choosing keys (a hash-flooding attack), can degrade every operation to O(n) in the worst case. A balanced tree's O(log n) bound holds for every input, not just typical ones, because it comes from the tree's structural invariant, not from statistical spread.

AVL vs red-black: two ways to bound the height

Because AVL keeps a tighter height bound, point lookups are on average slightly faster (fewer comparisons); because red-black tolerates more imbalance before rotating, insert and delete are on average cheaper. Neither difference is large in practice, and both are asymptotically O(log n); the choice matters more in workloads with extreme read/write ratios than in typical applications.

When the balancing overhead isn't worth paying

• Point-lookup-only workloads (caches, sets, deduplication) with no ordering or range needs: use a hash table.
• On-disk storage, such as database indexes: neither AVL nor red-black trees are the right structure at all. A B-tree (a tree with a much higher branching factor than a binary tree, so each node holds many keys) is preferred for on-disk indexes because it minimizes the number of disk-block reads: each node read is one I/O, and a wide branching factor means far fewer levels than a binary tree for the same key count. An in-memory red-black or AVL tree assumes uniformly cheap pointer-chasing, which doesn't hold once each node access might be a disk seek.

Worked example

For n = 1,000,000 keys, the exact minimum-node recurrence for AVL trees (the same Fibonacci-like relation used to derive the roughly 1.44 log2 n bound) gives a provable worst-case height of 27: an AVL tree needs at least 832,039 nodes to reach height 27, so 1,000,000 nodes cannot exceed height 27. The classical red-black bound, $2 \log_2(n+1)$, evaluates to about 39.86 for the same n, so at most 39. For comparison, an ideal perfectly balanced binary tree has height floor(log2(1,000,000)) = 19, and a plain unbalanced binary search tree (BST, a tree where every node's left subtree holds smaller keys and its right subtree holds larger keys) built from sorted-order inserts degrades to height 999,999 (a straight chain).

import math

def max_avl_height_for_n(n):
    min_nodes = {-1: 0, 0: 1}
    h = 0
    while min_nodes[h] <= n:
        h += 1
        min_nodes[h] = min_nodes[h - 1] + min_nodes[h - 2] + 1
    return h - 1, min_nodes[h - 1]

n = 1_000_000
avl_h, avl_min_nodes = max_avl_height_for_n(n)
rb_bound = 2 * math.log2(n + 1)
print(f"ideal height: {math.floor(math.log2(n))}")
print(f"AVL worst-case height: {avl_h} (needs >= {avl_min_nodes:,} nodes)")
print(f"red-black worst-case height bound: {rb_bound:.2f} -> at most {math.floor(rb_bound)}")
print(f"unbalanced BST worst case: {n - 1:,}")

prints:

ideal height: 19
AVL worst-case height: 27 (needs >= 832,039 nodes)
red-black worst-case height bound: 39.86 -> at most 39
unbalanced BST worst case: 999,999

All four numbers describe worst-case comparisons for a single lookup on the same one million keys; the practical takeaway is that both AVL and red-black stay within roughly 2x of the theoretical minimum even in their worst case, while an unbalanced BST has no such guarantee at all.

Trade-offs & pitfalls

A hash table with open addressing or chaining still needs periodic resizing to keep its average O(1) guarantee, and a resize is an O(n) operation, though amortized (its cost spread evenly across the many O(1) inserts that led to it) over the sequence of inserts that triggered it, similar in spirit to how a dynamic array's occasional resize is amortized across its appends.

Concurrent access: red-black trees are generally easier to adapt to concurrent or lock-free implementations than AVL trees, because their rebalancing needs fewer structural changes per insert.

A common mistake is defaulting to a balanced tree "for safety" when a hash table would do, paying O(log n) for every operation when O(1) average was available and ordering was never actually needed. The opposite mistake is relying on a hash table's average-case guarantee in a context where an adversary controls the keys, for example a public API accepting arbitrary user-supplied strings as hash keys, where the worst case is a real risk rather than a theoretical one.

Direct answer

Put every element into a hash set, then only start "walking" a run from numbers that are the start of a run, meaning their predecessor (x - 1) is not in the set. From each such start, walk forward through x+1, x+2, ... while each is present, and track the longest walk seen. Because a hash set gives $O(1)$ average membership checks and every element is only ever walked once across the whole algorithm, this runs in average $O(n)$ time without sorting.

Structured elaboration

Approach. Sorting first would cost $O(n \log n)$, which is worse than the $O(n)$ bound the problem asks for; the hash set gets you constant-time "is this the start of a run" and "is the next number present" checks that a sorted array cannot beat once you account for the sort itself.

def longest_consecutive(nums):
    """
    Return length of longest consecutive sequence in nums.
    Average O(n) time, O(n) space.
    """
    if not nums:
        return 0
    s = set(nums)
    best = 0
    for x in s:
        if x - 1 not in s:          # only start counting at a run's beginning
            length = 1
            cur = x + 1
            while cur in s:
                length += 1
                cur += 1
            best = max(best, length)
    return best

Why the x - 1 not in s check keeps it linear. Without it, every element would try to walk its own run, redoing the same work as its predecessors: for a run of length L you'd do $1 + 2 + \dots + L = O(L^2)$ work instead of $O(L)$. The start-of-run check means the inner while loop only ever fires from a true run start, and every element is visited by exactly one such walk (the one belonging to its run), so total inner-loop work across the whole array is bounded by n, not by the number of runs times their lengths.

Worked example

nums = [100, 4, 200, 1, 3, 2]
print(longest_consecutive(nums))

Output: 4

Trace: the set is {100, 4, 200, 1, 3, 2}. Only 100 (no 99), 200 (no 199), and 1 (no 0) are run starts. From 1: 2, 3, 4 are all present, giving a run of length 4 (1,2,3,4). From 100 and 200: no successor present, so length 1 each. The longest is 4.

Trade-offs & pitfalls

Key points

• Sorting-based solutions (sort, then scan for consecutive runs) are simpler to reason about and use no extra hash-set memory, but they cost $O(n \log n)$ from the sort itself, which is asymptotically worse than the hash-set approach for large n.
• The hash-set approach only pays off because you resist the temptation to walk a run from every element; the "start of run" gate is what keeps total work linear instead of quadratic in the worst case (e.g., one giant consecutive run).
• Average-case linear time relies on the hash set having O(1) average operations; under adversarial hash collisions (a concern in security-sensitive contexts) a hash set's worst case degrades, whereas sorting's $O(n \log n)$ worst case is guaranteed regardless of input.

Complexity

• Time: average $O(n)$ (building the set is O(n); every element is visited by the inner while loop at most once across the whole run).
• Space: $O(n)$ for the hash set.

Edge cases

• Empty array: returns 0 immediately.
• Duplicates: the set naturally deduplicates, so [1, 2, 2, 3] still returns a run length of 3, not 4.
• All elements identical: every element is its own non-start except one value, giving a run length of 1.
• Negative numbers or gaps: the algorithm works unchanged since it relies only on integer successor relationships, not on sign or magnitude.

Direct answer

An adjacency list (each node keeps a list of just its neighbors) uses memory proportional to the actual number of edges, while an adjacency matrix (an n by n grid marking which pairs are connected) always uses memory proportional to $n^2$ regardless of how many edges actually exist. For a sparse graph (few edges relative to $n^2$ possible pairs), that difference is enormous, and for a million nodes with average degree 10, an adjacency list is the clear choice.

Structured elaboration

For a sparse graph, the adjacency list wins on both memory and neighbor iteration, and only loses on single-edge existence checks, which can be recovered by backing each node's neighbor list with a hash set. For a dense graph (edges close to the $n^2$ maximum), the matrix's $O(n^2)$ memory is no longer wasteful relative to the edge count, and its $O(1)$ edge check becomes the deciding advantage, especially for algorithms that repeatedly ask "are these two connected" (for example, computing transitive closure over a dense graph, where a matrix-based approach like Warshall's algorithm, which repeatedly asks whether routing through each candidate intermediate node connects a pair that was not connected before, is a natural fit).

Concrete pick for a million nodes, average degree 10: with $n = 1{,}000{,}000$,

Even at the most compact possible matrix encoding (a single bit per cell), the matrix needs about 125 GB, roughly 1,500 times more memory than the adjacency list's roughly 80 MB (assuming a compact, array-backed reference; a naive list of language-level objects would use more, but still nowhere near the matrix's footprint). The matrix is not just slower here, it is not a realistic option at all, so the adjacency list is the only workable choice.

Trade-offs & pitfalls

The most common mistake is defaulting to whichever representation is more familiar without checking density first; for the vast majority of real graphs (social graphs, web links, road networks, dependency graphs), average degree is a small constant or grows slowly with $n$, making them sparse, so adjacency lists dominate in practice. A second pitfall is assuming adjacency-list edge checks are always slow: if a node's degree is large, backing its neighbor list with a hash set restores $O(1)$ average edge checks without paying the matrix's $O(n^2)$ memory cost, which is usually the better middle ground than switching representations entirely. Converting between the two representations costs $O(n + m)$ to build a matrix from a list (visit each edge once) but $O(n^2)$ to build a list from a matrix (every cell must be scanned even if empty), which is itself a hint about which representation is cheaper to maintain as a sparse graph changes over time.

Direct answer

A plain stack already gives $O(1)$ push, pop, and top because those operations only ever touch the top element. The trick for $O(1)$ minimum retrieval is to keep a second, parallel stack that tracks what the minimum would be after each push: whenever you push a value onto the main stack, you also push the smaller of that value and the previous minimum onto the min-stack, so its top is always the correct current minimum, and popping both stacks together keeps them in sync without ever rescanning.

Approach

• Maintain two stacks of equal length at all times: stack holds the real values, min_stack holds, at each position, what the minimum was after that push.
• push(x): append x to stack. Append x to min_stack if min_stack is empty or x is less than or equal to its current top; otherwise append the current top again (repeating the still-current minimum).
• pop(): pop from both stacks together; the value from stack is returned, the value from min_stack is discarded.
• get_min(): return min_stack's top directly.

class MinStack:
    def __init__(self):
        self.stack: list[int] = []
        self.min_stack: list[int] = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)
        else:
            self.min_stack.append(self.min_stack[-1])

    def pop(self) -> int:
        if not self.stack:
            raise IndexError("pop from empty stack")
        self.min_stack.pop()
        return self.stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def get_min(self) -> int:
        return self.min_stack[-1]


if __name__ == "__main__":
    s = MinStack()
    s.push(5)
    s.push(3)
    s.push(7)
    print(s.get_min())  # 3
    s.pop()
    print(s.get_min())  # 3
    s.pop()
    print(s.get_min())  # 5
    print(s.top())       # 5

Running this prints 3, 3, 5, 5: after pushing 5, 3, 7 the minimum is 3; popping 7 (the top) leaves the minimum still 3; popping 3 next leaves only 5, so both the minimum and the top become 5.

Key points

• Using <= (not strict <) when deciding whether to push a new minimum is what makes duplicate minimum values work correctly: if two entries tie for the minimum and you only recorded the first, popping it would incorrectly raise the recorded minimum before the still-present duplicate is gone.
• An alternative "encoded delta" trick stores a single stack, keeping only a running minimum variable, and pushes a value relative to that minimum instead of the raw value, updating the running minimum on push/pop as needed. It roughly halves auxiliary storage but is more error-prone to implement correctly, especially in fixed-width-integer languages (C++, Java) where the encoded delta itself can overflow if the gap between the pushed value and the previous minimum is large.

Complexity

Time: $O(1)$ for every operation (push, pop, top, get_min). Space: $O(n)$ auxiliary for $n$ elements (two stacks, each up to size $n$; a larger constant factor than a single stack, but still linear).

Edge cases

• pop or top on an empty stack should raise or otherwise signal an error rather than reading past the end.
• Duplicate values at the current minimum: handled correctly only if the min-stack push condition uses <=, not <.
• A single-element stack: get_min() must equal top().