Algorithmic Problem-Solving and Data Structure Selection Questions

Direct answer

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

Structured elaboration

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

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

How cyclic sort gets the same information for free

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

The swap loop's subtlety

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

Worked example

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

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

This prints:

2
3
1
2

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

Key points

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

Complexity

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

Edge cases

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

Trade-offs & pitfalls

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

Direct answer

Reverse the whole array, then reverse the first k elements and the remaining n-k elements separately; three linear passes compose into the fully rotated result with no auxiliary array. The same reversal trick generalizes directly: reversing a string in place is the identical two-pointer, swap-from-both-ends routine, and rotating a square matrix 90 degrees in place is a transpose followed by reversing each row, both built on the same in-place-swap primitive as the array rotation.

Structured elaboration

Why three reversals produce a rotation. Reversing the entire array puts every element in fully reversed order. Reversing the first k elements of that reversed array un-reverses exactly the block that should now sit at the front, restoring its original relative order; reversing the remaining n-k elements does the same for the remainder. Normalizing with k %= n handles k values larger than the array's length or equal to zero.

Generalizing to a string. The same in-place two-pointer swap from both ends is exactly what reverses a string, provided the string is held in a mutable container (a list of characters, for example, since Python's own string type is immutable and cannot be reversed truly in place without first converting it).

Generalizing to a square matrix. Transposing swaps matrix[i][j] with matrix[j][i] for every i < j, turning rows into columns. Reversing each row afterward flips left to right. Combined, what was the first column read top to bottom becomes the first row read left to right, which is exactly a 90-degree clockwise turn.

Related in-place-preprocessing techniques (with an honest space caveat). Prefix-sum preprocessing builds an auxiliary array once, in $O(n)$ time, so that any later range-sum query answers in $O(1)$; this trades $O(n)$ extra space for fast queries, so it is not itself an O(1)-extra-space technique, even though it shares this family's "one linear pass, reuse the result" character. Product-except-self, by contrast, genuinely can be done with O(1) extra space beyond the required output array: a first pass fills the output with the running product of everything to each index's left, and a second pass multiplies in the running product of everything to that index's right, needing no separate auxiliary array at all.

Worked example

def rotate_array(nums: list[int], k: int) -> None:
    n = len(nums)
    if n <= 1:
        return
    k %= n
    if k == 0:
        return

    def reverse(i, j):
        while i < j:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1

    reverse(0, n - 1)
    reverse(0, k - 1)
    reverse(k, n - 1)


def reverse_string_inplace(chars: list[str]) -> None:
    i, j = 0, len(chars) - 1
    while i < j:
        chars[i], chars[j] = chars[j], chars[i]
        i += 1
        j -= 1


def rotate_matrix_90_cw_inplace(matrix: list[list[int]]) -> None:
    n = len(matrix)
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:
        row.reverse()


if __name__ == "__main__":
    arr = [1, 2, 3, 4, 5, 6, 7]
    rotate_array(arr, 3)
    print(arr)

    chars = list("hello")
    reverse_string_inplace(chars)
    print("".join(chars))

    m = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
    rotate_matrix_90_cw_inplace(m)
    print(m)

Running this prints [5, 6, 7, 1, 2, 3, 4], then olleh, then [[7, 4, 1], [8, 5, 2], [9, 6, 3]].

Complexity

rotate_array: time $O(n)$ for the three reversal passes, since they compose additively into a single linear scan rather than multiplying; space $O(1)$ extra, using only the two index pointers inside each reversal call.
reverse_string_inplace: time $O(n)$, one pass with two pointers closing in from both ends; space $O(1)$ extra beyond the mutable character list itself.
rotate_matrix_90_cw_inplace: time $O(n^2)$ for an n-by-n matrix, since the transpose visits each of the $n^2$ cells once; space $O(1)$ extra, since both the transpose and the row reversals swap in place with no auxiliary matrix.

Edge cases

• k = 0, or k a multiple of the array's length once normalized via k %= n: rotate_array detects this and returns immediately without performing any reversals, since the array is already in its correct rotated position.
• Empty or single-element array or string: both rotate_array (via its n <= 1 guard) and reverse_string_inplace (via while i < j never firing) return immediately with nothing to do.
• A non-square matrix passed to rotate_matrix_90_cw_inplace: this implementation assumes a square matrix, and a non-square transpose changes the matrix's dimensions, so it cannot be rotated true in place this way.

Trade-offs & pitfalls

Forgetting k %= n for a k larger than the array's length either wastes work or, in a careless implementation, indexes out of range. The transpose-then-reverse-rows trick only works for a square matrix: transposing a non-square matrix changes its dimensions, so a genuinely non-square rotation needs a separate output buffer rather than a true in-place transform. Python's string immutability means a real in-place string reversal needs a mutable container (a list of characters, or a bytearray) first; there is no way to mutate a str object's characters directly.

Direct answer

Walk the list once, and at each node redirect its next reference back to the previous node before advancing, using three tracking references: previous, current, and a temporary save of current's original next. This is $O(n)$ time and $O(1)$ space. A recursive version expresses the identical rewiring, handling everything after the current node first and then flipping the one link back, but it pays for that with $O(n)$ call-stack space that the iterative version does not need.

Structured elaboration

The iterative three-pointer dance. Before overwriting curr.next, save it in a temporary variable, or the rest of the list is lost permanently. Then point curr.next back at prev, advance prev to curr, and advance curr to the saved temporary. Repeat until curr is empty.

The recursive version. The base case is an empty list or a single remaining node, which is already "reversed" as-is. Otherwise, recursively reverse everything after the head first; that recursive call returns the new head of the whole reversed list. Then head.next.next = head flips the one link connecting the old head back into the newly-reversed remainder, and head.next = None prevents the old head from accidentally pointing at itself in a two-node cycle.

What language a solution is written in does not change any of this. The reskin into Python, JavaScript, Swift, or Kotlin, or building the linked-list node class from scratch first, is the same pointer-rewiring skill underneath; only the syntax for holding and dereferencing a reference changes, not the three-step relinking logic itself.

Worked example

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


def reverse_iterative(head):
    prev = None
    curr = head
    while curr:
        next_tmp = curr.next  # save before overwriting
        curr.next = prev
        prev = curr
        curr = next_tmp
    return prev


def reverse_recursive(head):
    if head is None or head.next is None:
        return head
    new_head = reverse_recursive(head.next)
    head.next.next = head
    head.next = None
    return new_head


def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out


def build_list(vals):
    dummy = Node(0)
    tail = dummy
    for v in vals:
        tail.next = Node(v)
        tail = tail.next
    return dummy.next


if __name__ == "__main__":
    print(to_list(reverse_iterative(build_list([1, 2, 3, 4]))))
    print(to_list(reverse_recursive(build_list([1, 2, 3, 4]))))

Running this prints [4, 3, 2, 1] twice, once from each implementation.

Complexity

Time: $O(n)$ for both the iterative and recursive versions, since each one visits every node exactly once.
Space: $O(1)$ extra for the iterative version (three pointer variables regardless of list length); $O(n)$ for the recursive version, from the call stack, since the recursion descends one frame per node before any relinking happens.

Edge cases

• Empty list (head is None): both versions return None immediately without any relinking.
• Single-node list: both versions return that same node unchanged as the new head, since there is nothing to reverse.
• Very long list: the recursive version risks an actual stack overflow, since typical call-stack depth limits are far smaller than what a linked list can otherwise hold in memory.

Trade-offs & pitfalls

The recursive version risks an actual stack overflow on a very long list in production, not just an academic concern, since typical call-stack depth limits are far smaller than what a linked list or array can otherwise hold in memory. The single most common bug in the iterative version is forgetting to save curr.next before overwriting it, which permanently disconnects the rest of the list from anything still reachable.

Direct answer

A trie (prefix tree) stores strings by sharing common prefixes as a path through a tree of characters: each node holds child pointers keyed by the next character, plus a marker for "a word ends here". insert, search, and startsWith all walk that path one character at a time, so each costs $O(L)$ where $L$ is the length of the word or prefix, independent of how many other words are stored. That's exactly what beats a hash set once the workload shifts to prefix queries: a hash set can tell you whether one exact string is a member in $O(L)$, but it has no way to answer "give me everything starting with pre" except scanning every stored string.

Approach

• Each TrieNode holds a dictionary of child nodes keyed by character, plus an is_word flag.
• insert(word): walk from the root, creating a child node for each character not already present, then mark the final node's is_word as true.
• search(word): walk the same path; if any character is missing, the word isn't stored. If the path exists, the word is present only if the final node's is_word is true (this is what distinguishes an exact match from merely being a prefix of something else).
• startsWith(prefix): identical walk, but the answer is simply whether the path exists at all; is_word is irrelevant.

class TrieNode:
    __slots__ = ("children", "is_word")

    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.is_word = False


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_word = True

    def _walk(self, prefix: str):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

    def search(self, word: str) -> bool:
        node = self._walk(word)
        return node is not None and node.is_word

    def startsWith(self, prefix: str) -> bool:
        return self._walk(prefix) is not None


if __name__ == "__main__":
    trie = Trie()
    trie.insert("apple")
    print(trie.search("apple"))     # True
    print(trie.search("app"))       # False: "app" was never inserted as a word
    print(trie.startsWith("app"))   # True: it's a valid prefix path
    trie.insert("app")
    print(trie.search("app"))       # True: now it's an inserted word too

Running this prints True, False, True, True, showing the exact distinction between a prefix existing in the tree and a full word being marked at that node.

Key points

• Sharing prefixes is the whole benefit: "app", "apple", and "application" only pay for the divergent suffixes once "app" has been walked.
• Trie versus hash table, concretely: reach for a trie when the workload needs prefix queries, autocomplete, or longest-prefix matching (for example IP routing or URL routing tables), since a hash set has no ordering by prefix at all. Reach for a hash set when you only ever need exact-match membership and words rarely share prefixes, since a trie pays a real per-character node overhead that a flat hash set avoids.
• Deletion (not shown above) needs care: unmark is_word at the target node, then optionally prune nodes back up toward the root, but only while a node has no children and isn't itself marking a shorter stored word.

Complexity

insert: $O(L)$ time, up to $O(L)$ new nodes in the worst case (no shared prefix). search: $O(L)$ time, $O(1)$ extra space. startsWith(prefix): $O(P)$ time where $P$ is the prefix length. Overall trie space is $O(\text{total characters across all stored words})$ in the worst case, less whenever words share prefixes.

Edge cases

• Empty string: insert("") marks the root itself as a word; search("") and startsWith("") should both be true afterward.
• A prefix longer than any stored word simply fails the walk partway through and returns the correct negative.
• Re-inserting the same word is idempotent (no duplicate storage, is_word just gets set again).
• Large alphabets (Unicode) increase the practical memory cost per node since the child dictionary can hold far more distinct keys; a compressed trie (radix/PATRICIA tree, collapsing single-child chains) reduces node count when words rarely branch.

Direct answer

Count every character's frequency in one pass (a hash map or Counter), then make a second pass over the string returning the first character whose count is exactly 1. This is $O(n)$ time and $O(k)$ space, where k is the number of distinct characters. If the string arrives one character at a time and you must be able to answer "what's the first non-repeating character so far" at any point, keep a queue of once-seen candidates in arrival order and evict its front whenever that character's count rises above 1.

Structured elaboration

Two-pass approach, for a string you already have in full:

from collections import Counter

def first_non_repeated(s):
    """
    Return first non-repeated character in s, or None if none exists.
    Two-pass approach: O(n) time, O(k) space (k = distinct characters).
    """
    if not s:
        return None
    counts = Counter(s)
    for ch in s:
        if counts[ch] == 1:
            return ch
    return None

Streaming variant. The two-pass approach needs the whole string up front. If characters arrive one at a time and a query can land at any point, you cannot afford to rescan everything seen so far on every query. Instead, maintain a frequency map alongside a queue (double-ended queue) of characters that are currently unique, in the order they first appeared:

from collections import deque

class StreamingFirstNonRepeated:
    """
    Streaming variant: feed one character at a time via .push(ch) and query
    .current() at any point without rescanning history. O(1) amortized time
    per pushed character (each character enters and leaves the deque at most
    once), O(k) space for k distinct characters seen so far.
    """
    def __init__(self):
        self.counts = {}
        self.q = deque()

    def push(self, ch):
        self.counts[ch] = self.counts.get(ch, 0) + 1
        if self.counts[ch] == 1:
            self.q.append(ch)
        while self.q and self.counts[self.q[0]] > 1:
            self.q.popleft()

    def current(self):
        return self.q[0] if self.q else None

The queue's front is always the earliest-arrived character that is still unique, because any character that becomes non-unique gets evicted from the front the moment its count rises above 1 (it may sit behind the front briefly until it becomes the front, but it is removed by the time it would otherwise be reported).

Worked example

s = "swiss"
print(first_non_repeated(s))

tracker = StreamingFirstNonRepeated()
running = []
for ch in s:
    running.append(ch)
    tracker.push(ch)
    print(''.join(running), '->', tracker.current())

Output:

w
s -> s
sw -> s
swi -> s
swis -> w
swiss -> w

The full-string answer is w, matching the streaming tracker's final answer. Along the way you can see the answer change: after "s", "sw", "swi" the answer is still s (unique so far); once the second s arrives ("swis") the tracker evicts s from the front and reports w; the final s in "swiss" doesn't change the answer since w is still unique.

Trade-offs & pitfalls

Key points

• The two-pass approach is the simplest correct solution when the full string is available; don't reach for the streaming version if you don't need "answer at any point in time" semantics, since it adds a queue and eviction logic for no benefit.
• The streaming approach never needs to rescan from the start, but it does need to keep counts for every distinct character seen so far, and the queue can (temporarily) hold characters that later get evicted, so peak memory is still O(k) not O(1).
• Multi-codepoint or combined Unicode characters (for example, accented characters built from a base character plus a combining mark) are treated as separate codepoints by both approaches; if the requirement is "first non-repeating user-visible character" rather than "first non-repeating codepoint," you would need a grapheme-aware library instead of iterating raw codepoints.

Complexity

• Two-pass: time $O(n)$, space $O(k)$.
• Streaming: $O(1)$ amortized time per pushed character (each character is added to and removed from the queue at most once), space $O(k)$ for the counts and queue combined.

Edge cases

• Empty string: both approaches return None.
• All characters repeated: both return None (the two-pass loop finds no count-1 character; the streaming queue empties out).
• Single character: trivially non-repeating, both return it.