Algorithmic Problem-Solving and Data Structure Selection Questions

Direct answer

A sorting algorithm is stable if it preserves the relative order of elements
that compare equal on the sort key. If two records tie on the key you sorted
by, a stable algorithm guarantees the one that came first in the input still
comes first in the output. This matters for multi-key sorts: if you sort by a
secondary key after already sorting by a primary one, stability is what lets
the primary ordering survive as a tiebreaker inside each secondary-key group.
Merge sort and Python's Timsort (the algorithm behind sorted() and list.sort())
are stable; classic in-place selection sort and a typical quicksort are not.

Structured elaboration

Why stability matters for multi-key sorts. The standard trick for sorting
by (primary key, secondary key) without writing a composite comparator is:
sort once by the primary key, then sort the result by the secondary key. This
only produces the correct combined order if the second sort is stable: a
stable sort only reorders elements that actually differ on the secondary key,
so within any group of equal secondary-key values, the primary-key order from
step one is left untouched. An unstable sort makes no such promise: it may
reorder equal-secondary-key elements arbitrarily while grouping them, silently
destroying the primary ordering you already paid to establish.

A stable sort: merge sort, and Timsort (the hybrid merge/insertion sort
used by Python and Java's Collections.sort for objects). Both work by
merging or shifting elements without ever swapping two elements past an equal
one, so ties keep their input order.

An unstable sort: classic in-place selection sort (repeatedly swap the
current position with the position of the next-smallest remaining element).
The swap step moves elements across long distances in the array, including
past other elements with the same key, which is exactly what breaks ties.
Typical in-place quicksort implementations are unstable for the same reason
(the partition step swaps non-adjacent elements).

If you only have an unstable sort available, you can force stability by
attaching the original index to each record and sorting by (key, original_index)
instead of key alone. Ties on key are then broken by index, which exactly
reproduces stable behavior, at the cost of allocating one extra field per record.

Worked example

Take four employee records, already sorted by name (the primary key):

Now sort by department (the secondary key). A stable sort must produce:

Eng: Chen, Ito       (name order preserved)
Sales: Alvarez, Diallo  (name order preserved)

Running this in Python, where sorted() is stable, versus a hand-rolled
unstable selection sort, on the exact same input:

records = [
    {"name": "Alvarez", "dept": "Sales"},
    {"name": "Chen", "dept": "Eng"},
    {"name": "Diallo", "dept": "Sales"},
    {"name": "Ito", "dept": "Eng"},
]

stable_result = sorted(records, key=lambda r: r["dept"])

def unstable_selection_sort_by_dept(items):
    items = list(items)
    n = len(items)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if items[j]["dept"] < items[min_idx]["dept"]:
                min_idx = j
        items[i], items[min_idx] = items[min_idx], items[i]
    return items

unstable_result = unstable_selection_sort_by_dept(records)

print([(r["dept"], r["name"]) for r in stable_result])
print([(r["dept"], r["name"]) for r in unstable_result])

Output (verified by running this exact code):

[('Eng', 'Chen'), ('Eng', 'Ito'), ('Sales', 'Alvarez'), ('Sales', 'Diallo')]
[('Eng', 'Chen'), ('Eng', 'Ito'), ('Sales', 'Diallo'), ('Sales', 'Alvarez')]

The Eng group comes out identical either way, but the Sales group is
reversed under the unstable sort: Diallo now precedes Alvarez, even though
Alvarez came first alphabetically. That reversal is the bug: any downstream
code relying on "same department, alphabetical order" is now silently wrong,
and the failure is data-dependent, so it will not show up on every input.

Trade-offs & pitfalls

• Stability is a property of the algorithm's specification, not just a given
  implementation detail: "quicksort" is not stable by definition, but a
  particular library's sort might document stability as a guarantee (check
  the docs rather than assuming from the algorithm's name).
• The index-as-tiebreaker trick works with any comparison sort, stable or not,
  but costs O(n) extra memory for the index field and slightly more comparison
  overhead per element; it is the right choice when the language's built-in
  sort is unstable by contract (e.g. a raw quicksort library call) and you
  cannot swap in a stable one.
• A common wrong turn is assuming "the final order looks right on my test
  data" is proof of stability; instability is a tie-breaking behavior that
  only shows up when there are actual ties, so it hides in datasets with few
  duplicate keys and surfaces later at a different data distribution.
• Do not confuse stability with sort correctness on the primary sort key
  itself: an unstable sort still produces a fully correct order on the key it
  was told to sort by, it only fails to preserve unrelated prior ordering
  among equal elements.

Direct answer

Instead of comparing all k list heads against each other on every step, an O(k) comparison repeated n times for O(nk) total, keep a min-heap holding just the current head of each non-empty list; popping the heap's minimum costs O(log k), and pushing that node's successor back in also costs O(log k), giving O(n log k) total instead of O(nk). The heap always exposes the smallest of the k current candidates without re-scanning the other k - 1 heads on every step.

Structured elaboration

Approach

• Seed the heap with the first node of every non-empty list.
• Repeatedly pop the smallest node from the heap, append it to the output list, and if that node has a next node, push the next node into the heap. This keeps exactly one candidate per still-active list in the heap at all times, so the heap never holds more than k elements.
• Python's heap comparisons fall back to comparing whatever is stored in the tuple; since list nodes aren't directly comparable, pushing (value, a unique tie-breaking counter, node) tuples means ties on value never try to compare two node objects against each other.

import heapq
import itertools


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


def merge_k_lists(lists):
    """Merge k sorted linked lists into one sorted linked list.
    Time O(n log k), space O(k) for the heap, where n is the total node count."""
    heap = []
    counter = itertools.count()  # tie-breaker so the heap never compares ListNode objects

    for node in lists:
        if node is not None:
            heapq.heappush(heap, (node.val, next(counter), node))

    dummy = ListNode(0)
    tail = dummy

    while heap:
        _, _, node = heapq.heappop(heap)
        tail.next = node
        tail = node
        if node.next is not None:
            heapq.heappush(heap, (node.next.val, next(counter), node.next))

    return dummy.next

Key points

• The heap size is bounded by k throughout, regardless of how many total elements n there are, which is what keeps each push and pop at O(log k) rather than O(log n).
• The unique counter tie-breaker is what prevents a runtime error when two nodes have equal values and Python's heap needs a second thing to compare.
• The same approach works whether the k inputs are linked lists, arrays, or lazy iterators or generators, for example k=2 streams merged without ever materializing either one fully in memory: whatever the input, "peek the current smallest available element" and "advance to the next element" are all that's needed, and a linked list's next pointer, an array's index, and an iterator's next() call are three different ways to provide exactly that.

Worked example

lists = [1,4,5], [1,3,4], [2,6] (as linked lists). merge_k_lists prints [1, 1, 2, 3, 4, 4, 5, 6]. Tracing the first few pops: the heap starts with (1, 0, node), (1, 1, node), (2, 2, node), three candidates, with the tie on value 1 broken by the insertion-order counter. Popping the lower-counter 1 first pushes list 0's next value, 4. Popping the other 1 pushes list 1's next value, 3. Popping 2 pushes list 2's next value, 6. The heap now holds {3, 4, 4, 6}, and the merge continues popping in that sorted order.

Trade-offs & pitfalls

Complexity

Time: $O(n \log k)$, where $n$ is the total number of nodes across all lists and $k$ is the number of lists; each of the $n$ nodes is pushed and popped exactly once, and each heap operation costs $O(\log k)$ since the heap never holds more than $k$ elements.
Space: $O(k)$ extra for the heap; the output reuses the existing nodes rather than allocating new ones, so there's no additional $O(n)$ allocation beyond the input itself.

Edge cases

• One or more input lists are empty: they simply never contribute to the initial heap seeding.
• All lists empty: the heap starts empty, the loop never runs, output is empty.
• A single list: behaves like a pass-through, since the heap only ever holds one element at a time.
• Duplicate values across lists: handled correctly by the tie-breaking counter, which only affects heap ordering among equal values, not the final sorted output.

A divide-and-conquer approach (merge pairs of lists, then merge pairs of results, recursively) achieves the same O(n log k) time without needing a heap or the tie-breaking trick, and is often simpler to reason about; the heap approach is usually preferred when lists arrive incrementally or as live streams, since it only ever needs one head from each source at a time rather than requiring full lists up front. In languages with a directly comparable node type (C++ with a custom comparator struct, Java with a Comparator), the tie-breaking counter trick used here for Python is unnecessary.

Direct answer

Group strings that are anagrams of each other by mapping each string to a canonical key that is identical for all its anagrams and different otherwise, then bucket by that key in a hash map. A sorted-characters key ("eat" -> "aet") is simple but costs $O(k \log k)$ per string of length k; a fixed-alphabet character-frequency key (a 26-length count tuple for lowercase letters) costs only $O(k)$ per string, so it scales better as strings get longer.

Structured elaboration

Approach 1: sorted-string key, $O(n \cdot k \log k)$ total for n strings of average length k.

from collections import defaultdict

def group_anagrams_sorted(strs):
    """Group anagrams using sorted-characters string as key. O(N*K log K) time."""
    buckets = defaultdict(list)
    for s in strs:
        key = ''.join(sorted(s))
        buckets[key].append(s)
    return list(buckets.values())

Approach 2: character-frequency key, $O(n \cdot k)$ total, avoiding the sort entirely by counting occurrences directly into a fixed-size tuple.

def group_anagrams_count(strs):
    """Group anagrams using a 26-length character-count tuple as key (lowercase a-z). O(N*K) time."""
    buckets = {}
    for s in strs:
        counts = [0] * 26
        for ch in s:
            counts[ord(ch) - 97] += 1
        key = tuple(counts)
        buckets.setdefault(key, []).append(s)
    return list(buckets.values())

The same technique applies at smaller and larger granularities than "group a whole list":

• Pairwise check ("are these two strings anagrams of each other"): compare the frequency keys of just the two strings directly, with no bucketing map needed at all, using collections.Counter as the frequency map.
• Anagram-substring start indices ("find all anagram-substring start indices" of a pattern p inside a longer string s): instead of computing one static key per whole string, slide a fixed-width window of length len(p) across s and maintain a running frequency counter for the window, comparing it against the target frequency counter for p at every position. This is the identical character-frequency-key idea, just recomputed incrementally as the window shifts by one character (add the entering character, remove the leaving character) instead of being built once per string.

from collections import Counter

def are_anagrams(a, b):
    """Pairwise anagram check using the same frequency-key technique."""
    return Counter(a) == Counter(b)

def find_anagram_starts(s, p):
    """
    Return start indices in s where a length-len(p) substring is an anagram
    of p, via a sliding window over frequency counters. O(len(s)) time.
    """
    n, k = len(s), len(p)
    if k > n:
        return []
    target = Counter(p)
    window = Counter(s[:k])
    result = []
    if window == target:
        result.append(0)
    for i in range(k, n):
        window[s[i]] += 1
        left = s[i - k]
        window[left] -= 1
        if window[left] == 0:
            del window[left]
        if window == target:
            result.append(i - k + 1)
    return result

Worked example

words = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(group_anagrams_sorted(words))
print(group_anagrams_count(words))
print(are_anagrams("listen", "silent"))
print(are_anagrams("listen", "silence"))
print(find_anagram_starts("cbaebabacd", "abc"))

Output:

[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
True
False
[0, 6]

Both grouping approaches produce the same three buckets. The pairwise check confirms "listen"/"silent" share a frequency key but "listen"/"silence" do not (different lengths, so different key). The sliding-window scan over "cbaebabacd" finds two anagram-of-"abc" windows, starting at index 0 ("cba") and index 6 ("bac").

Trade-offs & pitfalls

Key points

• Sorting is simple and works for any character set (Unicode included) without modification, but its $O(k \log k)$ per-string cost dominates once k grows large.
• The count-key avoids sorting entirely, dropping the per-string cost to $O(k)$, but as written it assumes a small fixed alphabet (lowercase a-z); for full Unicode you would key on a dictionary or Counter-derived frozen structure instead of a fixed 26-length tuple, which adds some hashing overhead per distinct character but keeps the linear-in-k scaling.
• Both approaches store $O(n \cdot k)$ total data across all buckets and keys.

Complexity

• Sorted-key grouping: time $O(n \cdot k \log k)$, space $O(n \cdot k)$.
• Count-key grouping: time $O(n \cdot k)$, space $O(n \cdot k)$.
• Sliding-window substring search: time $O(n)$ where n is the length of the longer string (constant-size alphabet keeps each window comparison O(1) amortized), space $O(1)$ for the counters (bounded by alphabet size).

Edge cases

• Empty strings: sorted("") is "" and an all-zero count tuple, both hash consistently, so empty strings correctly bucket with other empty strings.
• Case sensitivity and Unicode: decide up front whether "Eat" and "eat" should be treated as anagrams; normalize case before keying if not, and switch the count-key from a fixed 26-slot array to a Counter/dict for non-ASCII input.
• Pattern longer than the source string in the substring-search variant: return an empty result immediately rather than sliding a window that cannot fit.

Direct answer

Maintain a disjoint-set (union-find) structure over the items: each connect(u, v) event does two finds plus one union, and each are these connected query does two finds and compares the results, both in amortized time so close to constant that it is treated as $O(\alpha(n))$ in practice ($\alpha$ is the inverse Ackermann function, which is at most 4 for any realistic input). A fresh breadth-first or depth-first search (BFS/DFS, traversals that explore a graph outward from a start node) after every new edge would instead cost $O(V + E)$ per query, so answering $q$ queries over a growing graph costs $O(q \cdot (V + E))$ total, which scales far worse as both the edge stream and the query count grow.

Structured elaboration

Union-find keeps each connected group as a tree with a representative root, updated incrementally as edges arrive:

• find(x): walk up parent pointers to the root, flattening the path as you go (path compression).
• connect(u, v): find both roots; if they differ, attach the smaller tree under the larger one's root (union by rank) and merge.
• connected(u, v): true exactly when find(u) == find(v).

This is fundamentally an incremental structure: each new edge only touches the two trees it connects, never the whole graph, so the cost of processing an edge does not grow as the graph grows. Re-running BFS/DFS from scratch after every edge, by contrast, always pays for a full traversal of everything reachable so far, regardless of how small the actual change was.

The same primitive answers three framings that look different on the surface: cycle detection while building an undirected graph (adding edge (u, v) closes a cycle exactly when find(u) == find(v) already, before the union), the running count of connected components (start at $n$ and decrement by one on every union that actually merges two different roots), and an incrementally updated dependency or account-merge graph (the scenario here): all three are the same "maintain connectivity as edges stream in" problem.

Worked example

class DSU:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.components = n

    def find(self, x: int) -> int:
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # path halving
            x = self.parent[x]
        return x

    def connected(self, a: int, b: int) -> bool:
        return self.find(a) == self.find(b)

    def union(self, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False   # (a, b) already connected: this edge closes a cycle
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        self.components -= 1
        return True


dsu = DSU(6)  # nodes 0..5
stream = [(0, 1), (2, 3), (0, 2), (4, 5), (1, 3)]  # last edge closes a cycle

for u, v in stream:
    created_new_link = dsu.union(u, v)
    print(f"connect({u},{v}) -> new_edge={created_new_link}, "
          f"connected_now={dsu.connected(u, v)}, "
          f"components_remaining={dsu.components}")

print("query(0,3):", dsu.connected(0, 3))
print("query(0,4):", dsu.connected(0, 4))
print("total_components:", dsu.components)

Running this prints:

connect(0,1) -> new_edge=True, connected_now=True, components_remaining=5
connect(2,3) -> new_edge=True, connected_now=True, components_remaining=4
connect(0,2) -> new_edge=True, connected_now=True, components_remaining=3
connect(4,5) -> new_edge=True, connected_now=True, components_remaining=2
connect(1,3) -> new_edge=False, connected_now=True, components_remaining=2
query(0,3): True
query(0,4): False
total_components: 2

The (1, 3) edge returns new_edge=False because 1 and 3 were already in the same group (via 0-1 and 0-2-3), so that edge closes a cycle rather than merging anything, and the component count correctly stays at 2.

Key points

• union returning false is exactly the cycle-detection signal: the edge connects two nodes already in the same group.
• components needs no separate pass to compute: it is decremented once per union that actually merges two distinct groups.

Complexity

versus

for the BFS/DFS-from-scratch alternative. Space is $O(n)$ for the parent and rank arrays.

Edge cases

• A self-loop edge (u, u): find(u) == find(u) trivially, so union correctly reports no new edge without special-casing it.
• Edges referencing a node outside the initial size: the structure needs to be sized (or dynamically grown) for the maximum node ID up front, since union-find here uses array indices, not a hash map.
• Duplicate edges arriving again later: handled the same way as a cycle-closing edge, no extra logic needed.

Trade-offs & pitfalls

Union-find only answers connectivity and component membership; unlike a BFS/DFS traversal, it cannot reconstruct the actual path between two connected nodes, so if the caller needs the path (not just "are they linked"), you still need a traversal on top. It also has no efficient support for removing an edge once merged (there is no "un-union"): if the stream needs to delete edges as well as add them, standard union-find is the wrong tool, and you would look at fully offline processing (process deletions in reverse as unions, if the full edge stream is known ahead of time) or dedicated dynamic-connectivity structures rather than trying to force a delete through this structure.

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().