Arrays, Strings, and Hashing Questions

Direct answer

Reduce k modulo n first, since rotating by a full n is a no-op and any k can be folded into [0, n). Then reverse the whole array once, and reverse each of the two resulting parts (the first k elements and the remaining n - k), which lands every element in its rotated position using only O(1) extra space and three linear passes.

Structured elaboration

• Why k %= n first. A right rotation by n positions returns the array to its original order, so any k >= n is equivalent to k % n. Skipping this step means an implementation either does needless repeated work for large k, or (worse) indexes out of bounds when it assumes k < n.
• The reversal trick, step by step. A right rotation by k moves the LAST k elements to the front and the FIRST n - k elements to the back, each preserving their own relative order:
  1. Reverse the whole array. Everything is now in fully reversed order.
  2. Reverse the first k elements of THAT reversed array. Those k elements were originally the array's last k elements; reversing them twice (once by the whole-array reversal, once here) restores their original relative order, now correctly sitting at the front.
  3. Reverse the remaining n - k elements similarly, restoring the original relative order of what were the first n - k elements, now correctly sitting at the back.
• Complexity. Three linear passes over the array: O(n) time total, O(1) extra space (just the swap loop), no second array allocated.

Worked example

def rotate_right(arr, k):
    n = len(arr)
    if n == 0:
        return arr
    k %= n

    def reverse(lo, hi):
        while lo < hi:
            arr[lo], arr[hi] = arr[hi], arr[lo]
            lo += 1
            hi -= 1

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

def slice_rotate_right(arr, k):
    n = len(arr)
    if n == 0:
        return list(arr)
    k %= n
    return arr[-k:] + arr[:-k] if k else list(arr)


test_cases = [
    ([1, 2, 3, 4, 5, 6, 7], 3),
    ([1, 2, 3, 4, 5, 6, 7], 10),
    ([1, 2, 3, 4, 5, 6, 7], 7),
    ([1, 2, 3, 4, 5, 6, 7], 0),
    ([42], 5),
]
for arr, k in test_cases:
    result = rotate_right(list(arr), k)
    expected = slice_rotate_right(list(arr), k)
    print(f"arr={arr}, k={k} -> {result}")
    assert result == expected
print("cross-check against slice-based rotation passed for all 5 cases")

Output (executed, python3 s68_rotate_right.py, cross-checked against slice-based rotation for 5 cases):

arr=[1, 2, 3, 4, 5, 6, 7], k=3 -> [5, 6, 7, 1, 2, 3, 4]
arr=[1, 2, 3, 4, 5, 6, 7], k=10 -> [5, 6, 7, 1, 2, 3, 4]
arr=[1, 2, 3, 4, 5, 6, 7], k=7 -> [1, 2, 3, 4, 5, 6, 7]
arr=[1, 2, 3, 4, 5, 6, 7], k=0 -> [1, 2, 3, 4, 5, 6, 7]
arr=[42], k=5 -> [42]
cross-check against slice-based rotation passed for all 5 cases

k=10 on a 7-element array gives the identical result to k=3 (10 % 7 == 3), and k=7 (a full rotation) correctly leaves the array unchanged.

Trade-offs & pitfalls

• Forgetting the k %= n reduction is the most consequential bug: it can index a reversal call with k - 1 larger than n - 1, or simply waste O(k/n) extra full passes for a large k.
• Off-by-one in the two split-reversal calls (reverse(0, k-1) and reverse(k, n-1)) is the most common implementation bug; verifying against a small hand-traced example (as above) catches this quickly.
• Rotating LEFT by k is the mirror image but with the reversal ORDER changed: reverse the first k, reverse the remaining n - k, THEN reverse the whole array (right rotation reverses the whole array FIRST). Mixing up the order between left and right rotation is an easy transcription error.
• Alternatives: an extra output array is O(n) space but trivial to write correctly; a cycle-following ("juggling") algorithm is also O(1) space and O(n) time but is meaningfully harder to get right, since it needs to track gcd(n, k) independent cycles rather than three flat passes. The reversal trick is generally preferred in an interview specifically because it's simple to reason about and hard to get subtly wrong.

Direct answer

Profile with tracemalloc (or a sampling profiler like py-spy for a live production process you cannot restart) to find which lines are allocating the most, then reduce churn by building strings incrementally into a preallocated buffer (io.StringIO, a list plus "".join(), or a bytearray/memoryview for byte-oriented data) instead of repeated concatenation, and only reach for rewriting the hot path in a compiled language like Go once profiling shows the Python-level allocation itself, not something else, is the bottleneck. To demonstrate improvement, compare allocation counts and bytes allocated before and after, not wall-clock time, since wall-clock measurements are too environment-dependent to be a reliable before/after signal on their own.

Structured elaboration

Profiling and identifying hotspots:

• tracemalloc (standard library): take a snapshot, run the workload, take a second snapshot, and compare them grouped by traceback (Snapshot.compare_to(..., "lineno")). This ranks allocation sites by net bytes and net object count, which is exactly "identify hotspots" turned into a concrete procedure.
• py-spy: a sampling profiler that attaches to an already-running process by PID, with no code changes and low enough overhead to run against production. This matters specifically in a Site Reliability Engineering (SRE) context, where the process causing the pressure may not be restartable or instrumentable on demand.
• objgraph: useful when the concern is object retention (things not being freed) rather than pure allocation churn, by showing what is holding references to a suspect object type.

A precision point that changes how you frame the problem to a team: plain Python str objects are refcounted, not tracked by the cyclic garbage collector (garbage collection, GC) at all, since they cannot hold references to other objects. Confirmed directly: gc.is_tracked("hello") returns False. This means transient string churn in CPython does not, by itself, increase cyclic-GC pause frequency the way churn of container objects (lists, dicts, custom class instances) can; it shows up instead as allocator (pymalloc) traffic, more time spent in malloc/free-equivalent bookkeeping, and heap fragmentation. Calling this "GC pressure" is common shorthand but is worth correcting precisely when advising a team, since it points them at the right tool (tracemalloc, allocator-level metrics) instead of the wrong one (gc.get_stats(), which reports on the cyclic collector).

Reducing allocations, in the order the question names them:

• bytearray/memoryview: bytearray is mutable, so appending to it does not create a new object each time the way immutable str concatenation can; memoryview lets you take zero-copy slices of existing buffer objects instead of allocating a new copy for every substring.
• io.StringIO: acts as a growable in-memory buffer with .write(), giving the same "accumulate then finalize" benefit as building a list and joining it, useful when the code is structured as many small writes rather than a clean list comprehension.
• Preallocated buffers / pooling: if the maximum size is known or bounded, allocate the buffer once outside the hot loop and reuse it, rather than allocating fresh per iteration or per request; this is the standard fix once profiling shows the same code path allocating repeatedly at high frequency.
• "".join(list_of_parts): append parts to a list (which CPython over-allocates geometrically, so appending is amortized $O(1)$) and join once at the end, rather than repeated += concatenation.
• Moving the hot path to a language with different allocation and escape-analysis behavior: Go's escape analysis can keep many short-lived values on the stack instead of the heap, avoiding per-object allocator overhead entirely for values that never need to outlive the function call; a hand-written C extension goes further still, giving full manual control over a single reused buffer with zero object-header overhead per string. Both are justified only once profiling has shown the allocation itself, not I/O or something else entirely, is the actual bottleneck.

Metrics to collect to demonstrate improvement:

• Net bytes allocated and net object count from tracemalloc snapshot comparisons, run against the same fixed workload before and after the change (a controlled, repeatable comparison, not a wall-clock timing claim).
• gc.get_stats() collection counts per generation, mainly as a sanity check that the change has not shifted pressure onto container types the cyclic collector does track, rather than as the primary signal for string-specific churn (per the precision point above).
• Process-level memory metrics already collected by most SRE tooling: resident set size (RSS) over time and page-fault counts, which reflect real allocator and operating-system-level cost.
• Downstream 95th/99th-percentile (P95/P99) request latency in production dashboards, correlated with the change's rollout, as the ultimate business-relevant signal, understanding that latency is influenced by many factors and is a correlation check, not a controlled experiment by itself.

Worked example

A controlled comparison of three approaches to building an 80,000-character string from 2,000 fixed 40-character pieces, counting reallocations directly via consecutive-identity comparison rather than timing anything:

import gc

N_ITEMS = 2000
ITEM = "x" * 40

print(f"gc.is_tracked('hello') = {gc.is_tracked('hello')}")

def count_reallocations_plus_equals(alias=False):
    s = ""
    history = [] if alias else None
    realloc_count = 0
    bytes_copied = 0
    prev_id = None
    for _ in range(N_ITEMS):
        if alias:
            history.append(s)  # keeps refcount(s) >= 2, defeating CPython's in-place resize fast path
        s += ITEM
        if id(s) != prev_id:
            realloc_count += 1
            bytes_copied += len(s)
        prev_id = id(s)
    return realloc_count, bytes_copied

def count_reallocations_join():
    parts = [ITEM for _ in range(N_ITEMS)]
    result = "".join(parts)
    return 1, len(result)

n_no_alias, bytes_no_alias = count_reallocations_plus_equals(alias=False)
n_alias, bytes_alias = count_reallocations_plus_equals(alias=True)
n_join, bytes_join = count_reallocations_join()

quadratic_upper_bound = sum(i * len(ITEM) for i in range(1, N_ITEMS + 1))
print(f"'+=' no alias  : reallocations = {n_no_alias:6d}, bytes copied = {bytes_no_alias:9d}")
print(f"'+=' aliased   : reallocations = {n_alias:6d}, bytes copied = {bytes_alias:9d}")
print(f"''.join(list)  : reallocations = {n_join:6d}, bytes copied = {bytes_join:9d}")
print(f"O(n^2) upper bound if every '+=' fully reallocated = {quadratic_upper_bound}")
print(f"aliased bytes-copied / no-alias bytes-copied = {bytes_alias / bytes_no_alias:.1f}x")
print(f"aliased bytes-copied / quadratic upper bound  = {bytes_alias / quadratic_upper_bound:.3f}")

Output (one representative run; counting via id(s) != prev_id rather than accumulating ids in a set matters here, because CPython can reuse a freed string's memory address for a later object, which silently under-counts reallocations if you count distinct id() values seen across the whole run instead of consecutive-call transitions):

gc.is_tracked('hello') = False
'+=' no alias  : reallocations =     36, bytes copied =    212200
'+=' aliased   : reallocations =   2000, bytes copied =  80040000
''.join(list)  : reallocations =      1, bytes copied =     80000
O(n^2) upper bound if every '+=' fully reallocated = 80040000
aliased bytes-copied / no-alias bytes-copied = 377.2x
aliased bytes-copied / quadratic upper bound  = 1.000

This is a genuinely interesting result, not the textbook story most candidates repeat: when nothing else holds a reference to the accumulating string, CPython's own refcount-1 fast path resizes the string in place for most iterations, so only a few dozen reallocations (36 in this run; repeated local runs varied between 36 and 37, with bytes copied varying correspondingly between roughly 212,200 and 277,720, since the fast path's exact behavior depends on the allocator's in-memory layout at the time) were actually needed for 2,000 concatenations, and total bytes copied is nowhere near the naive $O(n^2)$ bound in any of those runs. The moment something else holds a reference to the intermediate value on each iteration (history.append(s), simulating an innocuous-looking debug log or snapshot list elsewhere in the code), that fast path is completely defeated: exactly 2,000 reallocations occur every time (one per iteration, matching $N$ exactly) and the bytes-copied total lands at a ratio of 1.000 against the textbook quadratic bound, with no run-to-run variation

exactly matching the printed value, in every run. "".join() allocates exactly one object regardless. The practical lesson for an SRE debugging this in a real service: the dangerous pattern is not += concatenation itself, it is += concatenation where something else (a logger, a cache, a list of "recent values" for a debug endpoint) is quietly holding a reference to each intermediate string.

Trade-offs & pitfalls

• "Always use join, never +=" is oversimplified advice given what this measurement shows: in CPython specifically, single-owner += is often not the quadratic disaster it is in languages without that optimization. "".join() remains the right default because it is portable (not every Python implementation, such as PyPy in some configurations, guarantees the same optimization) and immune to accidental aliasing, but do not present the complexity claim as universally true across implementations without qualifying it.
• Reporting "reduced GC pressure" without the gc.is_tracked distinction can send a team optimizing the wrong layer. If the actual problem is generational-collector pause time, the fix is about reducing tracked-container churn (dicts, lists, custom objects), not string handling at all; conflating the two wastes an investigation cycle.
• Rewriting a hot path in Go or C is the highest-effort, highest-risk option on this list (new language, new deployment surface, a cross-language call boundary to maintain) and should be the last resort, justified by profiler evidence that the allocation itself, not serialization overhead, I/O wait, or something else in the same code path, is what dominates.
• A common measurement mistake: comparing wall-clock time for a "before" and "after" version on a shared, noisy production host and presenting the difference as the improvement. Machine load, CPU frequency scaling, and other tenants make single wall-clock comparisons unreliable; use allocation counts and bytes (as measured above) or repeated, controlled benchmarking on an isolated host as the primary evidence instead.

Direct answer

Normalize both strings to a canonical Unicode form (NFC: compose combining marks into precomposed characters wherever a composed form exists), then casefold them (a Unicode-aware, more aggressive relative of .lower()), and finally compare character frequency counts using a hash map. Two strings are anagrams exactly when their normalized, casefolded character-count maps are equal. This is O(n) time and O(k) extra space, where k is the number of distinct characters actually present, not the size of the whole alphabet.

Structured elaboration

Why raw codepoint comparison fails on Unicode text. The same visible character can be represented by different codepoint sequences: an accented letter like an e with an acute accent can be one precomposed codepoint, or two codepoints (the base letter plus a separate combining acute-accent mark). Two strings that look identical to a human, and that a user would absolutely expect to be treated as anagrams of each other, can fail a naive character-by-character or Counter-based comparison if one uses the composed form and the other the decomposed form, because they are literally different sequences of codepoints.

Normalization (NFC) before comparison. Running both strings through Unicode Normalization Form C (NFC) converts any decomposed base-plus-combining-mark sequence into its precomposed equivalent wherever one exists, so that two visually-identical strings become byte-for-byte identical at the codepoint level before any counting happens. Normalization must happen before counting, not after, since counting decomposed and precomposed forms separately would treat them as different characters.

Casefolding, not just lowercasing. Python's .casefold() is used instead of .lower() because casefolding is defined specifically for caseless string matching and handles cases .lower() doesn't, most famously the German sharp s (ß), which casefolds to the two-character sequence ss (matching how ß and ss are treated as equivalent in caseless comparisons) while .lower() leaves it unchanged. This means casefolding can change a string's length, which matters for the next step.

Order of operations for the length check. The length check (len(s) != len(t) as a fast rejection before doing full character counting) must be performed on the normalized-and-casefolded strings, never on the raw input, precisely because casefolding can change length. Checking the raw lengths first, as a shortcut before normalization, is a subtle but real bug: it would incorrectly reject valid Unicode-aware anagram pairs whose raw lengths differ only because casefolding expands one of them.

Sorting-based versus counting-based comparison, and the large-alphabet trade-off. A sorting-based approach (sort both normalized/casefolded strings, compare for equality) costs O(n log n) time but only O(1) extra space if sorting can be done on a mutable copy in place (or O(n) if the language's sort isn't in-place), and it never needs a hash map at all, which matters when the character alphabet is enormous, since a sort never allocates space proportional to the alphabet size, only to the string length. A counting-based approach (build a frequency map, compare maps) is O(n) time but pays O(k) space for the map, where k is the number of distinct characters seen; for a small, fixed alphabet like lowercase ASCII, that map is trivially small and counting wins outright on speed, but for full Unicode text (over a million possible codepoints, even though any single string only uses a tiny fraction of them), a hash-map-based counter is still the right call because k is bounded by the input length itself, not by the alphabet size, since a Python dict/Counter only allocates entries for characters that actually appear.

Worked example

Full runnable code with pinned test cases, including the composed-versus-decomposed accented-character case and the German sharp-s casefold case (a genuine subtlety, not a contrived one):

import unicodedata
from collections import Counter


def normalize_for_compare(s):
    """NFC-normalize then casefold. Length check must happen AFTER this,
    never on the raw string (see the STRASSE case below)."""
    return unicodedata.normalize("NFC", s).casefold()


def is_anagram(s, t):
    """O(n) time, O(k) extra space where k is the distinct-character count,
    counting-based rather than sorting-based."""
    s_norm = normalize_for_compare(s)
    t_norm = normalize_for_compare(t)
    if len(s_norm) != len(t_norm):
        return False
    return Counter(s_norm) == Counter(t_norm)


if __name__ == "__main__":
    # Built from explicit codepoint escapes so the composed/decomposed
    # distinction is unambiguous regardless of source-file encoding.
    precomposed = "caf" + "\u00e9"          # c a f e-acute (1 codepoint, U+00E9)
    decomposed = "caf" + "e" + "\u0301"     # c a f e + combining acute (U+0301)

    print("raw codepoint lengths (decomposed vs precomposed):", len(decomposed), len(precomposed))
    print("raw equal (no normalization)?", decomposed == precomposed)
    print("NFC-normalized equal?", unicodedata.normalize("NFC", decomposed) == unicodedata.normalize("NFC", precomposed))

    reordered_precomposed = "\u00e9" + "fac"          # e-acute f a c (reordered anagram)
    strasse_lower = "stra" + "\u00df" + "e"           # stra-sharp_s-e

    tests = [
        ("listen", "silent", True),
        ("Listen", "Silent", True),
        (precomposed, decomposed + "x", False),
        (precomposed, reordered_precomposed, True),
        (decomposed, reordered_precomposed, True),
        ("STRASSE", strasse_lower, True),   # casefold('ss') == casefold('\u00df')
        ("ab", "abc", False),
    ]
    for a, b, expected in tests:
        result = is_anagram(a, b)
        print(f"is_anagram({a!r}, {b!r}) = {result} (expected {expected})")

    print("raw len(strasse_lower) =", len(strasse_lower), " raw len('STRASSE') =", len("STRASSE"))
    print("casefold(strasse_lower) =", strasse_lower.casefold())
    print("casefold('STRASSE') =", "STRASSE".casefold())

Output (actual run):

raw codepoint lengths (decomposed vs precomposed): 5 4
raw equal (no normalization)? False
NFC-normalized equal? True
is_anagram('listen', 'silent') = True (expected True)
is_anagram('Listen', 'Silent') = True (expected True)
is_anagram('café', 'caféx') = False (expected False)
is_anagram('café', 'éfac') = True (expected True)
is_anagram('café', 'éfac') = True (expected True)
is_anagram('STRASSE', 'straße') = True (expected True)
is_anagram('ab', 'abc') = False (expected False)
raw len(strasse_lower) = 6  raw len('STRASSE') = 7
casefold(strasse_lower) = strasse
casefold('STRASSE') = strasse

The STRASSE / straße case is the one to walk through out loud in an interview: the raw strings have different lengths (7 versus 6 codepoints), so a fast-reject on raw length would wrongly report "not an anagram." But ß casefolds to the two characters ss, so both strings casefold to the same 7-character string strasse, and they are correctly identified as an anagram pair. This is exactly why the length check must run on the normalized-and-casefolded strings.

Trade-offs and pitfalls

• Comparing raw strings, or even lowercasing with .lower() instead of .casefold(), silently fails on real internationalized input like the ß/ss case above; .lower() alone leaves ß unchanged and would report STRASSE and straße as not anagrams, which is wrong under Unicode caseless matching rules.
• Checking length before normalizing (a tempting micro-optimization to avoid normalizing strings that "obviously" can't match) is a genuine bug source, not a harmless shortcut, precisely because casefolding and normalization can both change apparent length.
• Sorting-based comparison is the right call when the alphabet is small and fixed (interview-classic lowercase-English anagram checks) since it avoids hash-map overhead entirely; counting-based comparison is the right call once the input might be full Unicode text, since a hash map's cost scales with how many distinct characters actually appear in this particular input, not with the size of the Unicode codepoint space.
• Grapheme-cluster-level correctness (treating an emoji-with-modifier sequence, or a base character plus multiple combining marks, as a single user-perceived "character") is a further layer beyond codepoint-level NFC normalization; this answer normalizes and compares at the codepoint level, which is sufficient for the vast majority of real anagram-style interview questions, but a fully grapheme-aware comparison would need a dedicated segmentation library, which is depth beyond what this question is testing.
• NFC (compose) rather than NFD (decompose) is used here because it produces the more compact, more widely-used-as-a-default form; either would work correctly as long as it's applied consistently to both strings before comparison, since the point is only that both strings land on the same normalized form, not which specific form is chosen.

Direct answer

Sort the array, then fix each element in turn as the smallest of a candidate triplet and use two pointers over the remaining sorted suffix to find pairs summing to its negation. Skipping repeated values at the fixed index and at both inner pointers is what avoids duplicate triplets in the output without a separate deduplication pass over a set of results.

Structured elaboration

• Sort first. Sorting costs O(n log n) and is what enables both the two-pointer sweep and the duplicate-skipping logic below.
• Outer loop. For each index i (up to n - 2), if nums[i] > 0 the loop can break entirely: in a sorted-ascending array, no triplet starting at or after a positive number can ever sum to zero. Skip i if it repeats the previous value, to avoid re-deriving the same set of triplets from an identical starting point.
• Inner two-pointer sweep. With left = i + 1, right = n - 1, and target = -nums[i]: if nums[left] + nums[right] == target, record the triplet and move both pointers inward, additionally skipping over any further repeats of nums[left] or nums[right] so the SAME triplet isn't recorded twice; if the sum is too small, advance left; if too large, retreat right.
• Complexity. O(n log n) sort plus O(n^2) for the outer loop times the inner two-pointer sweep, dominated by the O(n^2) term overall. Extra space is O(1) beyond the sort itself and the output list (or O(n) if the sort isn't in-place, depending on language).
• On "use lists and dictionaries where appropriate." The solution above uses only the sorted list and two pointers, with no dictionary needed for correctness. An equally valid O(n^2) alternative fixes i and then runs a hash-SET-based two-sum pass over the remaining unsorted elements for each i (checking whether target - nums[j] has been seen), which avoids needing the array sorted at all. Here, sorting is essentially free to do and additionally buys the early break and the duplicate-skipping logic for free, so the two-pointer version is the standard choice; the hash-set variant is worth naming as the alternative specifically for a case where the array's original order must be preserved for some OTHER constraint.

Worked example

def three_sum(nums):
    nums = sorted(nums)
    n = len(nums)
    result = []
    for i in range(n - 2):
        if nums[i] > 0:
            break
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        left, right = i + 1, n - 1
        target = -nums[i]
        while left < right:
            s = nums[left] + nums[right]
            if s == target:
                result.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1
            elif s < target:
                left += 1
            else:
                right -= 1
    return result


def three_sum_brute_force(nums):
    n = len(nums)
    found = set()
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if nums[i] + nums[j] + nums[k] == 0:
                    found.add(tuple(sorted((nums[i], nums[j], nums[k]))))
    return found


for nums in [[-1, 0, 1, 2, -1, -4], [0, 0, 0], [0, 0, 0, 0], [1, 2, -2, -1], []]:
    result = three_sum(nums)
    print(f"nums={nums} -> {result}")
    as_multisets = [tuple(sorted(t)) for t in result]
    assert len(as_multisets) == len(set(as_multisets)), "duplicate triplet detected"
    assert set(as_multisets) == three_sum_brute_force(nums)
print("brute-force cross-check (as sets of sorted triplets) and no-duplicate check passed for all cases")

Output (executed, python3 s66_three_sum.py, cross-checked against an O(n^3) brute force as sets of sorted triplets, and checked that no triplet in the output repeats another as a multiset):

nums=[-1, 0, 1, 2, -1, -4] -> [[-1, -1, 2], [-1, 0, 1]]
nums=[0, 0, 0] -> [[0, 0, 0]]
nums=[0, 0, 0, 0] -> [[0, 0, 0]]
nums=[1, 2, -2, -1] -> []
nums=[] -> []
brute-force cross-check (as sets of sorted triplets) and no-duplicate check passed for all cases

[0, 0, 0, 0] correctly collapses to a single [0, 0, 0] triplet despite four zeros being present, which is exactly the duplicate-skip logic being exercised.

Trade-offs & pitfalls

• Duplicates can sneak into the output from three separate places: the outer index i, left after a match, and right after a match. Missing any ONE of the three still produces duplicate triplets, so all three skips are needed together, not just one.
• A naive alternative, dumping every found triplet (as a sorted tuple) into a set after the fact, is correct but wastes work: it still does the redundant searching that produces the duplicates in the first place, it just filters them out afterward instead of avoiding them.
• This generalizes to k-sum by recursing one level per additional target element, but each added level multiplies in another O(n) (or O(n log n) for the sort, done once) factor, so 4Sum is already O(n^3) and the approach stops scaling well past k around 4 or 5.
• sorted(nums) here returns a NEW list, so the caller's original array is untouched; an in-place nums.sort() would mutate it, which matters if the caller still needs the original order elsewhere.

Direct answer

With n elements, the best case is that the array holds exactly {1, 2, ..., n}, which makes the answer n + 1; otherwise the missing value lies somewhere in [1, n]. That collapses the search space enough to turn the array into its own presence table: place each value v (when 1 <= v <= n) at index v - 1 using swaps, then scan for the first index whose value doesn't match index + 1. That index (plus one) is the smallest missing positive integer, and the whole thing runs in O(n) time using O(1) extra space because no second array or hash set is ever allocated.

Structured elaboration

Why the search space collapses to [1, n+1]. Any value outside [1, n] (negative, zero, or greater than n) cannot possibly be the smallest missing positive integer for an n-element array, so it can be ignored or safely overwritten. This is what makes the array itself a viable substitute for a hash set: only n "slots" are needed to track presence of the n candidate values that matter.

The index-mapping (cyclic placement) pass. For each index i, while nums[i] is a valid candidate (1 <= nums[i] <= n) and it is not already sitting in its home slot (nums[nums[i] - 1] != nums[i]), swap nums[i] with nums[nums[i] - 1]. This pushes the value toward the index it "claims." A value equal to i + 1 is already home and the while loop stops immediately; a value outside [1, n] also stops the loop, since it can never claim a valid slot.

Why this stays O(n) despite the nested loop. Each swap places at least one element into its permanent correct home (once an element lands at its target index, the loop condition for that index becomes false and it never moves again). Since there are only n positions to permanently fill, the total number of swaps across the entire outer loop is bounded by n, so the nested while does not make this quadratic; it is a classic amortized-O(n) argument, the same one that justifies calling cyclic-sort-style placement linear.

The read-out pass. After placement, scan left to right for the first i where nums[i] != i + 1. That mismatch means value i + 1 never found a home, i.e. it was missing from the input, so the answer is i + 1. If no mismatch is found, every slot holds its expected value and the answer is n + 1.

Worked example

Trace on [3, 4, -1, 1] (n = 4), printing every swap exactly as executed:

start: [3, 4, -1, 1]
  swap nums[0] with nums[2] -> [-1, 4, 3, 1]
  swap nums[1] with nums[3] -> [-1, 1, 3, 4]
  swap nums[1] with nums[0] -> [1, -1, 3, 4]
after placement pass: [1, -1, 3, 4]
first mismatch at index 1: nums[1]=-1 != 2
answer = 2

Full runnable code (Python 3, no external dependencies) with pinned test cases:

def first_missing_positive(nums):
    """Return the smallest missing positive integer.
    O(n) time, O(1) extra space (beyond the input list, mutated in place).
    """
    n = len(nums)

    # Step 1: place each value v (1 <= v <= n) at index v-1 by swapping,
    # so that on a "perfect" array nums[i] == i+1 for all i.
    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            target = nums[i] - 1
            nums[i], nums[target] = nums[target], nums[i]

    # Step 2: the first index i where nums[i] != i+1 reveals the answer.
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1


if __name__ == "__main__":
    tests = [
        ([3, 4, -1, 1], 2),
        ([1, 2, 0], 3),
        ([7, 8, 9, 11, 12], 1),
        ([1, 2, 3], 4),
        ([], 1),
        ([1], 2),
        ([2], 1),
    ]
    for arr, expected in tests:
        arr_copy = list(arr)
        result = first_missing_positive(arr_copy)
        print(f"input={arr!r:25} -> {result} (expected {expected})")

Output (actual run):

input=[3, 4, -1, 1]             -> 2 (expected 2)
input=[1, 2, 0]                 -> 3 (expected 3)
input=[7, 8, 9, 11, 12]         -> 1 (expected 1)
input=[1, 2, 3]                 -> 4 (expected 4)
input=[]                        -> 1 (expected 1)
input=[1]                       -> 2 (expected 2)
input=[2]                       -> 1 (expected 1)

Trade-offs and pitfalls

• The most common wrong turn is sorting first: it works, but costs O(n log n) time and fails the question's stated time bound. Naming it as a correct-but-non-optimal baseline before presenting the index-mapping trick shows the interviewer you understand why the O(n) approach is needed, not just that it exists.
• A hash set of seen values gets O(n) time but O(n) extra space, missing the O(1) space constraint. It is worth naming this trade-off explicitly rather than jumping straight to the in-place trick, since it demonstrates the same reasoning under a relaxed constraint.
• An easy implementation bug: omitting the "not already home" guard (nums[nums[i]-1] != nums[i]) causes an infinite loop whenever a value already equals its own target, which happens with duplicates like [1, 1], since the code would keep swapping a value with itself forever.
• The input array is mutated in place. If the array must be preserved, say so and either copy it first (paying O(n) space to keep O(n) time) or confirm in-place mutation is acceptable for the exercise.
• Duplicates and out-of-range values (negatives, zero, values greater than n) are both handled by the same guard condition, so no separate cleanup pass is required; stating this explicitly heads off the follow-up question before it's asked.