Arrays, Strings, and Hashing Questions

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

lst[start:stop:step] returns a NEW list built by copying references at indices start, start+step, start+2*step, ... up to but not including stop. Negative indices count from the end (-1 is the last element), and a negative step walks backward. Unlike numpy, Python list slicing always copies, it never returns a view, so a slice of length k from a list of length n costs O(k) time and O(k) extra memory, not O(n).

Structured elaboration

Syntax mechanics. start defaults to 0 (or len(lst) for a negative step), stop defaults to len(lst) (or "through the beginning" for a negative step), step defaults to 1. Negative indices are resolved to positive ones first (-1 -> len(lst) - 1), then the normal start/stop/step machinery applies.

Negative step behavior. A negative step reverses the walk direction. lst[::-1] is the idiomatic full-list reverse; lst[5:1:-2] starts at index 5 and walks backward by 2 until it would reach or pass index 1.

View vs copy. List slicing is always a full copy, a genuinely new list object with its own storage, which is why mutating the slice's result never affects the original list (demonstrated below). This differs from numpy, where basic slicing (not fancy or boolean indexing) returns a VIEW sharing the same underlying buffer, and mutating the view does mutate the source, which is a separate consideration when choosing between the two.

Time and memory complexity. Creating lst[a:b] where b - a = k does exactly k reference copies: O(k) time and O(k) new memory, regardless of how large the source list n is. A common misconception is that slicing costs O(n) because "it touches the whole list": it does not, it only touches the k elements it copies.

Site Reliability Engineering (SRE)-specific danger and alternatives. Repeatedly slicing a large in-memory structure (for example, paginating through a multi-gigabyte log buffer with buf[i:i+chunk] in a loop) duplicates data on every slice, which can double memory pressure or trigger avoidable garbage-collection churn under load, exactly when an SRE (the on-call engineer responsible for a system's reliability) least wants unpredictable memory behavior during an incident. Alternatives that avoid the copy: itertools.islice for a lazy, non-copying iterator over a sequence; a plain generator or yield-based chunker; memoryview for byte-like buffers (bytes, bytearray, array.array), which does support zero-copy sliced views; or, for genuinely huge data, memory-mapping the source (mmap) instead of holding it as a Python list at all.

Worked example

data = [10, 20, 30, 40, 50, 60, 70]  # length n = 7, pinned

print("first three     data[:3]      =", data[:3])
print("last two        data[-2:]     =", data[-2:])
print("every other     data[::2]     =", data[::2])
print("reversed        data[::-1]    =", data[::-1])
print("middle (drop ends) data[1:-1] =", data[1:-1])
print("negative step   data[5:1:-2]  =", data[5:1:-2])

sub = data[1:4]
sub[0] = 999
print("after mutating sub, data      =", data, " (unchanged: slicing copied)")

import sys
n = 100_000
big = list(range(n))
small_slice = big[:10]
print("sys.getsizeof(big)        =", sys.getsizeof(big), "bytes")
print("sys.getsizeof(small_slice)=", sys.getsizeof(small_slice), "bytes")

Output:

first three     data[:3]      = [10, 20, 30]
last two        data[-2:]     = [60, 70]
every other     data[::2]     = [10, 30, 50, 70]
reversed        data[::-1]    = [70, 60, 50, 40, 30, 20, 10]
middle (drop ends) data[1:-1] = [20, 30, 40, 50, 60]
negative step   data[5:1:-2]  = [60, 40]
after mutating sub, data      = [10, 20, 30, 40, 50, 60, 70]  (unchanged: slicing copied)
sys.getsizeof(big)        = 800056 bytes
sys.getsizeof(small_slice)= 136 bytes

The size comparison makes the O(k) claim concrete: a slice of 10 elements from a 100,000-element list costs 136 bytes, not anywhere near the 800,056-byte cost of the full list, confirming the slice's footprint scales with k, not n.

Trade-offs and pitfalls

• Assuming slicing is "free" or O(1): it is O(k), which is cheap for small k but adds up when repeated over large chunks in a hot loop.
• Assuming list slicing returns a view like numpy does: it never does. If zero-copy behavior on a byte buffer is needed, reach for memoryview, not a list.
• Off-by-one errors with a negative step (lst[stop:start:-1]-style mistakes) are the single most common source of "why is my reversed slice missing an element."
• Rebuilding a large structure via repeated slicing inside an incident-response script is exactly the kind of thing that can turn a memory-pressure incident into a self-inflicted one.

Direct answer

Treat each value in the array as a pointer: from index i, "follow" nums[i] to land on index nums[i]. Because there are n+1 values all in the range [1, n], at least two different indices must point to the same value (pigeonhole), which means this functional graph has a cycle, and the duplicate value is exactly the entry point of that cycle. Floyd's tortoise-and-hare cycle detection finds that entry point in O(n) time and O(1) extra space, without modifying the array at all, which is exactly what the question asks for.

Approach (Floyd's cycle detection)

1. Start both slow and fast at nums[0], i.e. one step into the implicit linked structure (index 0 always has an outgoing "pointer," but nothing points back to it, so it can't be part of the cycle itself, only the tail leading into it).
2. Advance slow one step (slow = nums[slow]) and fast two steps (fast = nums[nums[fast]]) each iteration until they meet; a meeting point is guaranteed to exist since the structure has a cycle (standard tortoise-and-hare argument).
3. Reset a second pointer to index 0, then advance it and slow one step at a time together; the index where they meet is the cycle's entry point, which is the duplicate value.

Complexity

Time: O(n) (each phase does at most O(n) steps). Space: O(1) extra; nums itself is never modified.

Edge cases

• Exactly one duplicate value, appearing exactly twice: this is the assumed input shape and the algorithm handles it directly.
• The duplicate value equal to n itself (the largest allowed value): handled the same way, since indexing is 0-based but values start at 1, so nums[i] is always a valid index regardless of which value 1..n is duplicated.

def find_duplicate_floyd(nums):
    slow = nums[0]
    fast = nums[nums[0]]
    while slow != fast:
        slow = nums[slow]
        fast = nums[nums[fast]]
    slow2 = 0
    while slow2 != slow:
        slow2 = nums[slow2]
        slow = nums[slow]
    return slow


data = [1, 3, 4, 2, 2]
original = list(data)
print(find_duplicate_floyd(data), data == original)

Output:

2 True

The duplicate is correctly identified as 2, and data == original confirms the array was never mutated during the search.

Alternative technique: index-marking

A second valid approach exploits the same "values are indices" fact differently: walk the array once, and for each value, negate the entry at the index that value points to (abs(value) - 1). If you ever land on an index whose entry is already negative, that index (converted back to 1-based) is the duplicate, because it means two different positions "pointed" to it. This is also O(n) time and O(1) additional space, but unlike Floyd's approach, it works by temporarily mutating nums in place (each visited value's target slot gets negated), so if the caller needs nums to remain externally unmodified while the function runs (not just restored by the time it returns), Floyd's version is the safer default.

def find_duplicate_marking(nums):
    duplicate = None
    for x in nums:
        idx = abs(x) - 1
        if nums[idx] < 0:
            duplicate = idx + 1
            break
        nums[idx] = -nums[idx]
    for i in range(len(nums)):
        nums[i] = abs(nums[i])
    return duplicate


data2 = [1, 3, 4, 2, 2]
print(find_duplicate_marking(data2), data2)

Output:

2 [1, 3, 4, 2, 2]

Both techniques agree on the duplicate (2), and the marking approach restores the array to its original values by the time it returns, even though it mutated it during the scan.

Trade-offs and pitfalls

• "Does not modify the array" has two readings, and the question's phrasing ("without modifying the array") most naturally means Floyd's guarantee: never mutated, at any point, including during execution. The marking approach only satisfies a weaker version ("unmodified once the function returns"), which is a meaningful difference if another thread could read nums concurrently while this function runs, or if the function could throw partway through and leave the array in its negated state.
• A frequent proof gap: candidates often reach for cycle detection without first establishing why a cycle must exist here. The argument is exactly pigeonhole: n+1 values drawn from a range of only n possible values guarantees at least one repeat, and because every value is a valid index (never 0, since the range is [1, n] not [0, n-1]), the "value points to index" structure is well-defined for every position, forcing at least one node in the sequence to be revisited, i.e. a cycle.
• A common bug in the marking approach: forgetting the final restoration pass, which silently corrupts the caller's array (still functionally finds the right duplicate, but violates the "don't modify the array" requirement in a way that's easy to overlook if you only test the return value).

Direct answer

Use a running prefix sum together with a hash map that counts how many times each prefix-sum value has been seen. At each index, the number of subarrays ending there with sum k equals the number of earlier prefix sums equal to (current prefix sum minus k). This gives an O(n) time, O(n) space solution that works correctly with negative numbers, where a sliding window cannot be used.

Structured elaboration

Why prefix sums plus a hash map

Define prefix[i] as the sum of the first i elements. The sum of the subarray from index i+1 through j is prefix[j] - prefix[i]. That subarray sums to k exactly when prefix[i] = prefix[j] - k. So as you scan left to right building up the running prefix sum, you only need to ask "how many earlier prefix sums equal (current prefix sum - k)?", and a hash map from prefix-sum value to how many times it has occurred answers that in O(1) average time.

Seed the hash map with {0: 1} before the scan starts. That entry represents the "empty prefix" (the state before index 0), and it is what lets a subarray starting at index 0 be counted, since its prefix-sum-so-far is compared against 0.

Why negatives are fine here but break sliding window

A sliding window relies on the sum growing monotonically as you extend the window, so you can decide when to shrink it. With negative numbers allowed, extending the window can decrease the sum, so there is no monotonic rule for when to move the left edge. The hash map approach does not depend on monotonicity at all: it only tracks exact prefix-sum values, so negatives cause no correctness issue.

Memory usage

The hash map can hold up to n+1 distinct prefix-sum values (one per index plus the seed), so worst-case space is O(n). In practice, if the input has many repeated prefix sums (for example, sequences that oscillate around zero), the map stays much smaller.

Handling very large sums safely

In Python, integers are arbitrary-precision, so a sum can grow to any size without silently overflowing or wrapping the way a fixed-width 32-bit or 64-bit integer would in Java, C++, or Rust. That removes the classic overflow bug for this problem in Python specifically. The one caveat worth naming out loud: arithmetic and hashing on very large integers are not truly O(1), their cost grows with the number of digits d, roughly O(d) per addition or hash. For the sums produced by realistic array inputs this is negligible, but if you ported this exact code to a fixed-width language, you would need either a checked-addition guard (raise or saturate on overflow) or a big-integer type, since the prefix sum can exceed 64-bit range for large arrays of large values.

Worked example

from collections import defaultdict

def subarray_sum_equals_k(nums, k):
    '''Count contiguous subarrays whose sum equals k. O(n) time, O(n) space.'''
    count = 0
    prefix_sum = 0
    seen = defaultdict(int)
    seen[0] = 1  # empty prefix, handles subarrays starting at index 0
    for x in nums:
        prefix_sum += x
        count += seen[prefix_sum - k]
        seen[prefix_sum] += 1
    return count

nums = [1, 2, 3, -3, 1, 1, 1]
k = 3
print(subarray_sum_equals_k(nums, k))

Output:

6

Enumerating every contiguous subarray of nums by brute force and checking which ones sum to 3 confirms the six matches directly: [1,2], [1,2,3,-3], [2,3,-3,1], [3], [3,-3,1,1,1], and [1,1,1]. Both the hash-map solution and an independent brute-force enumeration were run against each other on this input and agree on the count of 6.

Trade-offs and pitfalls

Forgetting the {0: 1} seed is the single most common mistake: it silently undercounts every subarray that starts at index 0. Reaching for a sliding window out of habit is the second: it looks like the natural upgrade from brute force, but it is only correct when all values are non-negative, and this problem explicitly allows negatives. Recomputing each subarray's sum from scratch inside a nested loop is the brute-force O(n^2) trap this technique exists to avoid. Finally, remember the count returned can itself be larger than the array length (a single index can close out subarrays with several different earlier starting points), so do not assume the answer is bounded by n. The same prefix-sum-plus-hashmap idea ports directly to any language with a hash map, a Java version would use a HashMap<Long, Integer> in place of the dict, with identical logic.

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.