Algorithmic Problem-Solving and Data Structure Selection Questions

Direct answer

Count frequencies first, then either maintain a min-heap of size k as you scan the counted items (evicting the smallest whenever the heap grows past k), or bucket the items by frequency and read off the top k directly. The heap approach costs $O(n \log k)$ time; the bucket approach costs $O(n)$ time but needs frequency values that are bounded by the input size. When k is very small relative to the number of distinct items, the heap wins because $\log k$ is tiny; when k is not small (approaching the number of distinct items), bucket sort's flat $O(n)$ bound stops paying a per-item $\log k$ penalty at all.

Structured elaboration

Heap of size k

Count every item's frequency (a single pass, $O(n)$). Then walk the distinct items, pushing each (frequency, value) pair onto a min-heap; once the heap holds k pairs, only push a new one if its frequency beats the current minimum, evicting that minimum first. The heap never holds more than k pairs at once, so each push or evict is $O(\log k)$, and there are at most one distinct-items-count many of them.

Bucket sort by frequency

Frequencies in a collection of n items are themselves bounded by n (an item can appear at most n times), so you can allocate n+1 buckets indexed directly by frequency and drop each distinct item into buckets[its frequency]. Reading buckets from the highest index down and collecting values until you have k of them is $O(n)$ total: no comparisons, no heap, just direct indexing.

When to prefer which

• k very small relative to distinct-item count: the heap's $O(n \log k)$ is close to $O(n)$ since $\log k$ is small, and it avoids allocating an array sized to the full item count the way the bucket approach does.
• k not small (comparable to the number of distinct items): the bucket approach's flat $O(n)$ bound no longer pays any per-item logarithmic penalty, while the heap's $\log k$ factor grows along with k; bucket sort becomes the clearly faster choice.
• Frequencies not naturally bounded by n (for example, if you were instead ranking by an unbounded external weight rather than a count derived from the input itself), bucket sort's indexing assumption breaks down and the heap approach generalizes more directly.

Worked example

import heapq
from collections import Counter


def top_k_frequent_heap(items: list[str], k: int) -> list[str]:
    """
    Min-heap of size k keyed by frequency. O(n log k) time, O(n) space
    for the frequency table plus O(k) for the heap.
    """
    if k <= 0:
        return []
    counts = Counter(items)
    heap: list[tuple[int, str]] = []
    for value, freq in counts.items():
        if len(heap) < k:
            heapq.heappush(heap, (freq, value))
        elif freq > heap[0][0]:
            heapq.heapreplace(heap, (freq, value))
    heap.sort(reverse=True)
    return [value for _, value in heap]


def top_k_frequent_bucket(items: list[str], k: int) -> list[str]:
    """
    Bucket sort by frequency. O(n) time, O(n) space.
    Bucket index = frequency (bounded by len(items)), so no comparison sort
    is needed once counts are known.
    """
    if k <= 0:
        return []
    counts = Counter(items)
    buckets: list[list[str]] = [[] for _ in range(len(items) + 1)]
    for value, freq in counts.items():
        buckets[freq].append(value)
    result: list[str] = []
    for freq in range(len(buckets) - 1, 0, -1):
        for value in buckets[freq]:
            result.append(value)
            if len(result) == k:
                return result
    return result


if __name__ == "__main__":
    data = ["a", "b", "a", "c", "b", "a", "d"]
    print("heap:", top_k_frequent_heap(data, 2))
    print("bucket:", top_k_frequent_bucket(data, 2))

Running this prints:

heap: ['a', 'b']
bucket: ['a', 'b']

For ["a","b","a","c","b","a","d"], the frequencies are a:3, b:2, c:1, d:1. Both the size-2 min-heap and the bucket-sort approach correctly identify a and b as the two most frequent items, agreeing with each other as they must, since both are computing the same top-k set from the same frequency counts.

Complexity

• Heap of size k: time $O(n \log k)$ (counting is $O(n)$, each of up to n distinct-item heap operations is $O(\log k)$); space $O(n)$ for the frequency table plus $O(k)$ for the heap.
• Bucket sort: time $O(n)$ (counting plus a single pass over buckets); space $O(n)$ for the frequency table plus the bucket array.

Edge cases

• k equal to the number of distinct items should return all of them.
• Ties in frequency mean the "top k" set is well-defined but the specific order among tied items is not, unless a tie-break rule (for example, lower value first) is specified.
• k=0 should return an empty result rather than erroring or returning one item.
• An empty input collection should return an empty result for any k.

Trade-offs & pitfalls

A common wrong turn is defaulting to a full sort of all distinct items by frequency ($O(n \log n)$ on the number of distinct items) instead of recognizing that only the top k are needed, which is exactly what both the heap-of-size-k and bucket-sort approaches avoid paying for. A second common gap is not noticing that bucket sort's efficiency depends on frequencies being bounded by a value proportional to n; presenting it as a universal replacement for the heap approach without that caveat overstates its applicability. For the streaming follow-up this question absorbs, only the heap approach adapts directly: a size-k heap can be updated incrementally as frequencies change, while bucket sort assumes all counts are known before you build the buckets and does not update as cheaply if counts keep shifting.

Direct answer

Assign each arriving task to whichever machine currently has the smallest total load (the "least-loaded machine" greedy rule, also called list scheduling). This online rule is never worse than twice the optimal offline makespan, and a short exchange-style argument tightens that to a factor of $\left(2 - \frac{1}{m}\right)$, where m is the number of identical machines. This is the classical Graham's bound (1966). If tasks additionally carry hard deadlines, a single machine's feasibility is best handled separately by Earliest Deadline First (EDF); no online multi-machine rule offers a comparable constant-factor guarantee once deadlines are layered on top of load balancing.

Structured elaboration

Setup: m identical machines, tasks arrive one at a time with processing time $p_i$, no knowledge of future arrivals, goal is to minimize the makespan (the finish time of the last task to complete).

Greedy rule: on each arrival, place the task on the machine with the current minimum cumulative load.

The exchange/potential argument for the bound. Let job j be the one that finishes last in the greedy schedule, running on machine i, starting at time t. Because greedy always routes work to whichever machine has the least load at that instant, every OTHER machine's load at time t must already be at least t (otherwise greedy would have picked one of them instead). Summing that lower bound across all m machines: the total work already placed before job j arrived, $P - p_j$ (where P is the sum of all processing times), is at least $m \cdot t$. That gives:

using two separate lower bounds on any optimal schedule's makespan: the average load $P/m \le OPT$, and the single largest job $p_j \le OPT$ (any schedule must place job j somewhere, taking at least $p_j$ time there). The "exchange" insight is that at the exact moment job j was placed, no machine could have been idler than machine i, so every machine had already absorbed unavoidable work, not that two individual schedule decisions are swapped directly.

Deadline extension: on a single machine, preemptive EDF is optimal for feasibility (it schedules any instance that has a feasible schedule at all). Once you combine online arrival, multiple machines, AND hard deadlines, no algorithm achieves a constant competitive ratio in the worst case; production systems fall back to a fast per-machine EDF feasibility check (admission control) layered on top of the same least-loaded routing, rather than chasing a provably-optimal global schedule.

import itertools

def greedy_list_scheduling(processing_times, m):
    """Assign each task, in arrival order, to whichever of the m machines
    currently has the smallest total load."""
    loads = [0] * m
    for p in processing_times:
        i = min(range(m), key=lambda k: loads[k])
        loads[i] += p
    return max(loads), loads

def optimal_makespan_bruteforce(processing_times, m):
    """Brute-force optimal offline makespan (small n only)."""
    n = len(processing_times)
    best = float("inf")
    for assignment in itertools.product(range(m), repeat=n):
        loads = [0] * m
        for idx, machine in enumerate(assignment):
            loads[machine] += processing_times[idx]
        best = min(best, max(loads))
    return best

m = 3
processing_times = [1, 1, 1, 1, 1, 1, 3]  # m*(m-1) unit tasks, then one size-m task
greedy_makespan, loads = greedy_list_scheduling(processing_times, m)
opt = optimal_makespan_bruteforce(processing_times, m)
print(f"greedy loads: {loads}, makespan: {greedy_makespan}")
print(f"optimal makespan: {opt}")
print(f"ratio: {greedy_makespan / opt:.4f}, bound (2 - 1/m): {2 - 1/m:.4f}")

Output:

greedy loads: [5, 2, 2], makespan: 5
optimal makespan: 3
ratio: 1.6667, bound (2 - 1/m): 1.6667

Worked example

With m = 3 machines, six unit-size tasks arrive first, then one size-3 task. Greedy spreads the six units evenly (2 per machine), then the size-3 task lands on whichever machine is currently tied for least-loaded, giving loads [5, 2, 2] and a makespan of 5. The optimal offline schedule instead puts the size-3 task alone on one machine (load 3) and splits the six unit tasks 3-and-3 across the other two (loads 3, 3), for an optimal makespan of 3. The ratio, 5/3 = 1.667, exactly matches $2 - \frac{1}{3}$: this is the standard tight instance showing the bound isn't just a proof artifact, an adversary really can force it.

Trade-offs & pitfalls

• The bound assumes identical machines with no migration; allowing tasks to migrate after the fact often does much better in practice, at the cost of moved-task overhead and more bookkeeping.
• The proof needs BOTH lower bounds ($P/m$ and $p_j$); relying on $P/m$ alone fails the moment one job is very large, since a single huge job forces a bigger optimal makespan than "average load" alone would suggest.
• Tie-breaking among equally-loaded machines does not affect the worst-case ratio, but a naive deterministic tie-break (always lowest index) can create structural correlation with adversarial arrival patterns; some implementations break ties randomly to avoid that.
• If tasks carry deadlines, "least-loaded" optimizes makespan, not deadline feasibility; the least-loaded machine at arrival time is not necessarily the one where this specific task's deadline is still reachable, so admission control needs its own per-machine feasibility check rather than trusting the load-balancing rule alone.
• The (2 - 1/m) bound does NOT generalize to machines with different speeds (unrelated or uniform machines): "current load" stops being the right proxy for "expected finish time" once machines process work at different rates, and a different assignment rule is needed.

Direct answer

A single depth-first search (DFS), augmented with a discovery-time array disc (when each vertex was first visited) and a low-link array low (the earliest discovery time reachable from that vertex's subtree using at most one edge that isn't a tree edge), finds articulation points and bridges in an undirected graph in $O(V + E)$. A structurally similar DFS, but with an explicit stack of "in-progress" vertices and using directed edges, finds strongly connected components (SCCs, maximal clusters where every node can reach every other node in the cluster) in a directed graph, also in $O(V + E)$. Both share the low-link idea and both do exactly one DFS, but they are not literally the same pass on the same graph: articulation points and bridges are an undirected-graph question, and strongly connected components is a directed-graph question, so which one applies depends on whether you're treating your edges as two-way or one-way.

Structured elaboration

Undirected graphs: articulation points and bridges

disc[v] is v's DFS visit order. low[v] is defined as:

$\text{low}[u] = \min\big(\text{disc}[u],\ \min_{w:(u,w)\text{ back-edge}} \text{disc}[w],\ \min_{v:(u,v)\text{ tree-edge}} \text{low}[v]\big)$

that is, the earliest thing u's own subtree can reach, either directly (a back edge straight to an ancestor) or through one of its DFS-tree children.

• Articulation point rule. The DFS root is an articulation point if and only if it has two or more DFS-tree children (removing it splits those children's subtrees apart). A non-root vertex u is an articulation point if it has a tree-edge child v with $\text{low}[v] \ge \text{disc}[u]$: that child's whole subtree cannot reach anything above u without passing through u itself.
• Bridge rule, same low-link values, a stricter comparison: a tree edge (u, v) is a bridge if $\text{low}[v] > \text{disc}[u]$ (strict): v's subtree cannot reach u or anything above u at all without that one edge, not even u itself.

Directed graphs: strongly connected components

Maintain an explicit stack of vertices currently on the current DFS path, plus an on_stack flag per vertex. The low-link rule changes in one important way: when considering an edge to an already-visited vertex w, you only fold in disc[w] if w is currently on the stack, not merely visited, since a visited-but-popped vertex belongs to an already-finished, unrelated component. When $\text{low}[u] = \text{disc}[u]$ after all of u's edges are explored, u is the root of a complete SCC: pop the stack down through and including u, and everyone popped is that component.

The "module dependency graph" framing maps onto this directly: if nodes are modules and edges are "depends on" relationships, an SCC with more than one node is a circular dependency cluster (module A eventually depends back on itself through some chain); a singleton SCC with no self-loop is a module with no circular dependency at all.

def articulation_points(n, edges):
    g = [[] for _ in range(n)]
    for u, v in edges:
        g[u].append(v); g[v].append(u)
    disc, low, is_ap, timer = [-1]*n, [0]*n, [False]*n, [0]

    def dfs(u, parent):
        disc[u] = low[u] = timer[0]; timer[0] += 1
        children = 0
        for v in g[u]:
            if v == parent:
                continue
            if disc[v] == -1:
                children += 1
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if parent != -1 and low[v] >= disc[u]:
                    is_ap[u] = True
            else:
                low[u] = min(low[u], disc[v])
        if parent == -1 and children > 1:
            is_ap[u] = True

    for i in range(n):
        if disc[i] == -1:
            dfs(i, -1)
    return sorted(i for i in range(n) if is_ap[i])


def tarjan_scc(n, edges):
    g = [[] for _ in range(n)]
    for u, v in edges:
        g[u].append(v)
    disc, low, on_stack, stack, timer, sccs = [-1]*n, [0]*n, [False]*n, [], [0], []

    def dfs(u):
        disc[u] = low[u] = timer[0]; timer[0] += 1
        stack.append(u); on_stack[u] = True
        for v in g[u]:
            if disc[v] == -1:
                dfs(v)
                low[u] = min(low[u], low[v])
            elif on_stack[v]:
                low[u] = min(low[u], disc[v])
        if low[u] == disc[u]:
            comp = []
            while True:
                w = stack.pop(); on_stack[w] = False; comp.append(w)
                if w == u:
                    break
            sccs.append(sorted(comp))

    for i in range(n):
        if disc[i] == -1:
            dfs(i)
    return sccs


bowtie_edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 2)]
print(articulation_points(5, bowtie_edges))

directed_edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 5), (5, 3)]
print(tarjan_scc(6, directed_edges))

Worked example

For an undirected "bowtie" (two triangles sharing one vertex): edges (0,1),(1,2),(2,0),(2,3),(3,4),(4,2), articulation_points(5, edges) returns [2], the shared vertex, since removing it disconnects the two triangles from each other.

For a directed graph modeling module dependencies with two independent cyclic clusters bridged by one one-way dependency: edges (0,1),(1,2),(2,0),(2,3),(3,4),(4,5),(5,3), tarjan_scc(6, edges) returns [[3, 4, 5], [0, 1, 2]]: two separate circular-dependency clusters (modules 0-1-2 and modules 3-4-5), connected only by the one-way edge from module 2 into module 3, so they are two SCCs, not one.

Complexity

Both articulation_points and tarjan_scc do a single DFS: the disc[i] == -1 guard means
each vertex is visited, and gets its dfs call, exactly once, so the outer loop plus all dfs
calls together do $O(V)$ work setting up and finishing each vertex. Inside dfs, the for v in g[u] loop examines each entry of each vertex's adjacency list exactly once; summed over
every vertex, that is $O(E)$ total (an undirected edge appears in two adjacency lists, still
$O(E)$ with a constant factor of 2). So total time is $O(V + E)$. Space is $O(V)$ for
disc/low/is_ap (or on_stack), plus $O(V)$ for the explicit stack (Tarjan's SCC) or the
recursion call stack (both algorithms), plus $O(V + E)$ for the adjacency-list representation
itself.

Edge cases

• Disconnected graph: the outer for i in range(n): if disc[i] == -1: dfs(i, -1) restarts
  DFS from every unvisited vertex, so each component gets its own DFS tree and its own
  root-special-case check.
• Self-loop ((u, u)) in articulation_points: g[u] gets u appended to it (from both
  sides of the edge); when dfs scans that entry, disc[u] is already set (to u's own
  discovery time) before the loop starts, so it falls into the else branch
  (low[u] = min(low[u], disc[u])), a harmless no-op since disc[u] can never be smaller than
  the low[u] it was initialized to.
• Single-vertex graph (n=1, no edges): dfs(0, -1) has no neighbors, children=0, so the
  root special case (children > 1) is false; articulation_points returns [] and
  tarjan_scc returns the single component [[0]].
• Empty graph (n=0): both outer loops run zero times, so both functions return [].
• Parallel edges between the same undirected pair: also flagged in Trade-offs below as
  breaking the naive "skip the parent by vertex id" rule, since it wrongly treats one of the
  parallel edges as a back edge to an ancestor.

Trade-offs & pitfalls

• The root special case is the most common articulation-point bug: the DFS root needs two or more tree-edge children, not just "has a child," to count as an articulation point.
• Bridge vs. articulation-point comparisons are easy to swap: bridges use the strict low[v] > disc[u], articulation points use the non-strict low[v] >= disc[u]. Mixing the two up silently misclassifies edges as bridges (or vertices as articulation points) that aren't.
• Parallel edges break the naive "skip the parent" rule for undirected graphs: if there are two edges between the same pair of vertices, skipping any edge back to parent by vertex id alone will wrongly treat one of the parallel edges as a back edge to an ancestor; tracking edge identity (not just the parent vertex) fixes this.
• For SCCs, checking disc[w] for any visited w instead of only vertices currently on_stack is a bug that silently merges vertices from different, already-finished DFS branches into the same low-link value, producing wrong components.
• Kosaraju's algorithm is the classic alternative for SCCs: two full DFS passes, one over the graph and one over its transpose, which is easier to reason about but costs an explicit graph transpose and a second full traversal, versus Tarjan's single pass with a stack.

Direct answer

Sort meetings by start time, and track the end times of currently occupied rooms in a min-heap (a binary heap ordered so the smallest element is always at the root, giving $O(\log n)$ push and pop). For each meeting, if the room that frees earliest already ended at or before this meeting's start, reuse it; otherwise open a new room. The peak number of rooms in use at any moment is the answer, which is a fundamentally different question from merge-overlapping-intervals: that problem asks for the union of overlapping ranges, while this one asks for the maximum number of ranges alive at the same instant, which can be larger than the number of merged groups whenever more than two meetings overlap at once.

Structured elaboration

Why this differs from merging overlapping intervals

Merging intervals collapses any chain of pairwise-overlapping intervals into one output range: three meetings that overlap in a chain (A overlaps B, B overlaps C, but A and C do not) merge into a single interval. Room counting instead asks how many of them are simultaneously alive, which is a different quantity: those same three meetings only ever need 2 rooms if A and C never overlap directly, even though they all merge into one interval. Room counting is a peak concurrency question, not a union of ranges question.

Why sorting starts and ends (or a heap of active ends) gets you there

Model each meeting as a $+1$ event at its start and a $-1$ event at its end. Sorting starts and ends and sweeping through events in time order lets you track the running concurrent count directly: the answer is the maximum value that running count ever reaches. A min-heap of active end times is an equivalent formulation of the same sweep: instead of a raw counter, the heap always tells you the earliest time a room becomes free, so you know immediately whether the next meeting can reuse an existing room or needs a new one.

Algorithm (steps)

1. Sort meetings by start time.
2. Maintain a min-heap of the end times of meetings currently occupying a room.
3. For each meeting in start order: if the heap is non-empty and its minimum end time is $\le$ this meeting's start, pop that end time (that room frees up) and push this meeting's end time in its place; otherwise push this meeting's end time as a new room.
4. The final heap size is the minimum number of rooms needed.

Worked example

import heapq


def min_meeting_rooms(intervals: list[list[int]]) -> int:
    """
    Minimum concurrent rooms needed. O(n log n) time, O(n) space (heap of end times).
    """
    if not intervals:
        return 0
    ordered = sorted(intervals, key=lambda pair: pair[0])
    heap: list[int] = []  # end times of meetings currently occupying a room
    for start, end in ordered:
        if heap and heap[0] <= start:
            heapq.heapreplace(heap, end)  # reuse the room that frees earliest
        else:
            heapq.heappush(heap, end)     # need a new room
    return len(heap)


if __name__ == "__main__":
    sample = [[0, 30], [5, 10], [15, 20]]
    print(min_meeting_rooms(sample))
    no_overlap = [[7, 10], [2, 4]]
    print(min_meeting_rooms(no_overlap))

Running this prints:

2
1

For [[0,30],[5,10],[15,20]]: room 1 opens for [0,30]; at start=5, the heap's minimum end is 30 which is not $\le$ 5, so a new room opens for [5,10]; at start=15, the minimum end is now 10 (from the just-finished [5,10]), which is $\le$ 15, so that room is reused for [15,20]; final heap size 2. For [[7,10],[2,4]] (sorted to [[2,4],[7,10]]): room 1 opens for [2,4]; at start=7, the minimum end 4 is $\le$ 7, so the same room is reused; final heap size 1.

Complexity

Time: $O(n \log n)$, dominated by the initial sort (heap operations are $O(\log n)$ each, over $n$ meetings). Space: $O(n)$ for the heap in the worst case, when every meeting overlaps every other.

Edge cases

• Empty input needs 0 rooms.
• A meeting that starts exactly when another ends is treated as not overlapping here (the room is reused): whether a meeting ending at t and one starting at t count as conflicting is a modeling choice to state up front.
• All meetings mutually overlapping (for example, everyone scheduled from 9am to 5pm) requires n rooms, the maximum possible.
• Duplicate identical meetings still each require their own room if they are genuinely simultaneous distinct bookings.

Trade-offs & pitfalls

The most common wrong turn is applying the merge-overlapping-intervals algorithm here and reporting the number of merged groups: that undercounts whenever three or more meetings overlap in a chain without all pairwise overlapping, since merging only tracks the union shape, not simultaneous occupancy. A second common gap is not being explicit about the boundary rule (does a meeting ending at t conflict with one starting at t), since interviewers frequently vary this to see if the candidate notices the assumption. For the streaming follow-up (meetings arriving one at a time rather than as a batch), the min-heap of active end times generalizes directly: insert the new end time, and if a room is reused, decrement the heap; there is no need to re-sort, since the heap already maintains order incrementally.

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