Arrays, Strings, and Hashing Questions

Direct answer

Walk the string once: skip leading whitespace, consume an optional sign, then consume digits until a non-digit character, converting as you go and clamping to the 32-bit signed integer range the moment the running value would exceed it. Overflow is detected before it happens, by comparing against a threshold, rather than by letting the value overflow and checking after the fact.

Structured elaboration

The parsing steps in order

1. Skip any leading space characters.
2. Read an optional + or -; anything else in that position (or nothing at all) means the sign defaults to positive.
3. Read consecutive digit characters, stopping at the first non-digit (including the end of the string). Everything after this point, including any trailing whitespace or trailing garbage characters, is ignored: there is no separate "trim the trailing spaces" step, because stopping the digit scan at the first non-digit already has the same effect as trimming, whatever comes after the last digit was never going to be parsed anyway.
4. If no digits were consumed at all, whether because the string was empty, all whitespace, or a sign with nothing after it, the result is invalid input and the function returns 0.
5. Apply the sign to the accumulated digits, then clamp to the 32-bit signed range: [-2147483648, 2147483647].

Detecting overflow without a big-integer library

The naive approach, accumulate the number as a normal machine integer and check afterward whether it exceeds the 32-bit range, does not work in a genuinely fixed-width language, because the multiplication and addition that build up the number can themselves overflow before you ever get to check. The safe pattern is to check BEFORE combining: given the current accumulated value num, the next digit d, and INT_MAX = 2147483647, the update num * 10 + d will exceed INT_MAX exactly when:

Since this comparison only involves num (kept within a checked range by this same rule applied to the previous digit) and small fixed constants, it never itself overflows, so you can safely bail out to the clamped INT_MAX (or INT_MIN for the negative sign) the moment the check trips, without ever needing arbitrary-precision arithmetic. In Python this exact discipline is not strictly required for correctness, since Python integers do not overflow, but it is exactly what a Java implementation of the same function needs: Java's int genuinely wraps around on overflow rather than raising an error, and Java's own Integer.parseInt throws a NumberFormatException on overflow rather than clamping, so a hand-rolled atoi in Java has to implement this check explicitly to match the clamp-on-overflow contract this problem asks for.

Treating invalid input

"Invalid" here specifically means: no digits were ever consumed. That covers an empty string, a string of only whitespace, a lone sign character with nothing after it, and a string that starts with a non-digit, non-sign, non-whitespace character. All of these return 0, matching the classic atoi contract; there is no exception path in this version of the problem.

Worked example

INT_MAX = 2**31 - 1
INT_MIN = -2**31

def string_to_int(s: str) -> int:
    i, n = 0, len(s)
    while i < n and s[i] == ' ':
        i += 1
    sign = 1
    if i < n and s[i] in '+-':
        if s[i] == '-':
            sign = -1
        i += 1
    digits_start = i
    num = 0
    while i < n and s[i].isdigit():
        digit = ord(s[i]) - ord('0')
        if num > (INT_MAX - digit) // 10:
            return INT_MAX if sign == 1 else INT_MIN
        num = num * 10 + digit
        i += 1
    if i == digits_start:
        return 0
    return sign * num

for t in ["42", "   -42", "4193 with words", "words and 987", "-91283472332", "91283472332"]:
    print(repr(t), "->", string_to_int(t))

Output:

'42' -> 42
'   -42' -> -42
'4193 with words' -> 4193
'words and 987' -> 0
'-91283472332' -> -2147483648
'91283472332' -> 2147483647

The last two lines show the overflow clamp firing correctly in both directions: 91283472332 is far larger than INT_MAX, and the function returns exactly 2147483647, not a wrapped or garbage value.

Trade-offs and pitfalls

The most common bug is checking for overflow AFTER the multiply-and-add, which is unsafe once you are in a language with real fixed-width integers, since the overflow has already corrupted the value by the time you inspect it. A second common mistake is forgetting that a sign character with no digits after it (just "-", or a sign followed only by more whitespace) must return 0, not treat the sign alone as meaningful. A third is stopping only at whitespace instead of at any non-digit, which mishandles inputs like "12a34" (should return 12, not attempt to parse further digits after the letter). Finally, remember this problem's clamp-and-return-0 behavior is a deliberate simplification for interview purposes: production-grade parsers, and most standard library functions, instead raise an exception on malformed or out-of-range input, so this should not be presented as how you would design a real parsing API, only as the exact contract this problem specifies.

Direct answer

Try IPv4 first: split on ., require exactly 4 parts, and each part must be all digits, at most 255, with no leading zero unless the part is exactly "0". If that fails, try IPv6: split on :, handle the :: zero-compression shorthand (which can appear at most once), require the expanded form to have exactly 8 groups, and each group must be 1 to 4 hexadecimal digits. Both formats have real edge-case density, which is exactly why this question is a good filter for carefulness rather than algorithmic cleverness.

Approach: IPv4

1. Split on .; reject unless there are exactly 4 parts.
2. Each part must be all-digit (test against /^[0-9]+$/), which also rejects a sign character or empty part.
3. Reject a leading zero unless the part is exactly "0" (i.e. "0" is valid, "00" and "01" are not).
4. Reject if the numeric value exceeds 255.

Approach: IPv6

1. :: can appear at most once; more than one is invalid (the shorthand would be ambiguous about how many zero groups it represents).
2. If :: is present, split the string into a "head" and "tail" around it, split each side on : (an empty side yields zero groups, not one empty-string group), and the total number of explicit groups on both sides together must be strictly less than 8 (the whole point of :: is to stand in for at least one omitted group).
3. If :: is absent, splitting on : must yield exactly 8 groups.
4. Every resulting group must be 1 to 4 hexadecimal digits.

Complexity

Both: O(L) where L is the length of the input string (each character is inspected a constant number of times across the split and per-group checks).

Edge cases

• IPv4 with a leading zero ("1.1.1.01"): rejected under the standard interview convention, discussed further below.
• IPv6 with the :: shorthand at the very start or end ("::1", "1::"), or standing alone for all-zero ("::"): all valid, and the head/tail split correctly produces zero groups on the empty side.
• A string that looks numeric but isn't a valid address in either format (e.g. too many or too few groups): correctly rejected by both checks, so the overall answer is "neither."

function isValidIPv4(s) {
  const parts = s.split(".");
  if (parts.length !== 4) return false;
  for (const p of parts) {
    if (!/^[0-9]+$/.test(p)) return false;
    if (p.length > 1 && p[0] === "0") return false;
    if (parseInt(p, 10) > 255) return false;
  }
  return true;
}

function isValidIPv6(s) {
  if ((s.match(/::/g) || []).length > 1) return false;
  let parts;
  if (s.includes("::")) {
    const [head, tail] = s.split("::");
    const headParts = head ? head.split(":") : [];
    const tailParts = tail ? tail.split(":") : [];
    if (headParts.length + tailParts.length >= 8) return false;
    parts = headParts.concat(tailParts);
  } else {
    parts = s.split(":");
    if (parts.length !== 8) return false;
  }
  for (const p of parts) {
    if (p.length < 1 || p.length > 4) return false;
    if (!/^[0-9a-fA-F]+$/.test(p)) return false;
  }
  return true;
}

const cases = ["172.16.254.1", "256.1.1.1", "1.1.1.1.1", "192.168.0.1",
  "2001:0db8:85a3:0000:0000:8a2e:0370:7334", "2001:db8::8a2e:370:7334", "::1", "::"];
for (const c of cases) {
  console.log(`${c} -> (${isValidIPv4(c)}, ${isValidIPv6(c)})`);
}

Output (executed, node s59_ip_validate.js):

172.16.254.1 -> (true, false)
256.1.1.1 -> (false, false)
1.1.1.1.1 -> (false, false)
192.168.0.1 -> (true, false)
2001:0db8:85a3:0000:0000:8a2e:0370:7334 -> (false, true)
2001:db8::8a2e:370:7334 -> (false, true)
::1 -> (false, true)
:: -> (false, true)

Each IPv4-shaped input is correctly recognized only as IPv4 ((true, false)), each IPv6-shaped input only as IPv6 ((false, true)), and the malformed 256.1.1.1 / 1.1.1.1.1 cases are correctly rejected as neither.

Trade-offs and pitfalls, grounded against a real parser

I checked this implementation's verdicts against Node's built-in net.isIP() (a mature, spec-driven parser shipped with the runtime this answer targets), as ground truth, over a wider test set that included two intentionally awkward cases. It surfaced one genuine, useful disagreement rather than confirming everything blindly:

const net = require("net");
console.log("1.1.1.01 -> mine:", isValidIPv4("1.1.1.01"), "net.isIP:", net.isIP("1.1.1.01"));
console.log("02001:0db8:85a3:0000:0000:8a2e:0370:7334 -> mine:", isValidIPv6("02001:0db8:85a3:0000:0000:8a2e:0370:7334"), "net.isIP:", net.isIP("02001:0db8:85a3:0000:0000:8a2e:0370:7334"));
console.log("::ffff:1.2.3.4 -> mine:", isValidIPv6("::ffff:1.2.3.4"), "net.isIP:", net.isIP("::ffff:1.2.3.4"));

Output (executed, node s59_parser_check.js):

1.1.1.01 -> mine: false net.isIP: 0
02001:0db8:85a3:0000:0000:8a2e:0370:7334 -> mine: false net.isIP: 0
::ffff:1.2.3.4 -> mine: false net.isIP: 6

• Leading zero and the oversized hex group: no disagreement here, and that itself is worth confirming rather than assuming. net.isIP("1.1.1.01") returns 0 (invalid), agreeing with this implementation's rejection; the same is true for the 5-hex-digit IPv6 group. Leading-zero rejection is a deliberate, security-motivated convention: leading zeros in IPv4 octets are genuinely ambiguous across tools (some historically parsed them as octal, so "010" meant 8, not 10), and that exact ambiguity was serious enough that Python's own standard-library ipaddress module was patched (CVE-2021-29921, fixed in Python 3.8.12 / 3.9.5 / 3.10.0a7) to reject any leading-zero octet outright rather than guess, precisely because parser disagreement on this point had been used to bypass IP-based access controls elsewhere. Node's net.isIP happens to already enforce the strict reading here, so this specific check doesn't surface a gap, but it would be a mistake to conclude every runtime's built-in parser is this strict; confirm it for whichever one you actually ship against.
• A real disagreement: "::ffff:1.2.3.4" (an IPv4-mapped IPv6 address, RFC 4291 section 2.5.5.2) is accepted by net.isIP as valid IPv6 (6), but this implementation rejects it (false). The reason is structural, not a bug in the sense of violating the question's own spec: the question defines IPv6 validity as "eight groups of 1-4 hex digits, allowing shorthand :: once," and "1.2.3.4" is neither a hex group nor handled by the ::-splitting logic, so it correctly falls out of scope for THIS definition. A production-grade validator that needs to accept the full real-world IPv6 address space would need an explicit extra branch recognizing a trailing dotted-quad segment. This is a good example of why "matches a mature real parser" and "matches the question's stated spec" are two different bars, and a candidate should be explicit about which one their implementation is targeting.
• A common bug in the IPv6 head/tail split: using head.split(":") unconditionally, without the head ? ... : [] guard, on an empty head (e.g. for "::1") produces [""] (one empty-string "group") instead of [] (zero groups), which then incorrectly fails the later 1-to-4-hex-digit check on that phantom empty group. This applies identically in JavaScript and in a straightforward Python port of the same logic.

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.

Direct answer

Maintain a deque of INDICES whose corresponding values are strictly decreasing from front to back; the front is always the current window's maximum. As the window slides, pop expired indices off the front and pop any trailing indices whose values the new element beats before pushing it, which keeps the whole scan at O(n) total even though a naive "recompute the max for every window" approach is O(n*k).

Structured elaboration

• Invariant. The deque holds indices i_1 < i_2 < ... < i_m (all within the current window) with nums[i_1] > nums[i_2] > ... > nums[i_m]. The front, i_1, is always the max of the current window.
• Expiry. Before considering a new index i, pop from the front any index <= i - k: it has fallen out of the window.
• Domination. Before pushing the new index i, pop from the back any index whose value is <= nums[i]: once a strictly larger value has appeared to its right, that older, smaller value can NEVER again be the max of any window that still contains the new element, so it is permanently useless and safe to discard.
• Why this is O(n) despite computing a max for every window. Each index is pushed onto the deque exactly once (when its own iteration is reached) and popped at most once (either from the front on expiry, or from the back on domination, never both). Total deque operations are bounded by 2n, so the amortized cost per element is O(1) even though the algorithm reports n - k + 1 window maxima.
• Extending to a very large stream you cannot fully store. The same deque works unmodified as a generator: instead of indexing into a stored array, store (position, value) pairs directly in the deque. Memory is O(k) regardless of how long the stream runs, because the deque never holds more than k pairs and nothing earlier is retained anywhere else once it has been used.

Worked example

from collections import deque

def max_sliding_window(nums, k, counters=None):
    dq = deque()
    result = []
    for i, x in enumerate(nums):
        while dq and dq[0] <= i - k:
            dq.popleft()
            if counters is not None:
                counters["pop"] += 1
        while dq and nums[dq[-1]] <= x:
            dq.pop()
            if counters is not None:
                counters["pop"] += 1
        dq.append(i)
        if counters is not None:
            counters["push"] += 1
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

def max_sliding_window_streaming(stream, k):
    dq = deque()
    for i, x in enumerate(stream):
        while dq and dq[0][0] <= i - k:
            dq.popleft()
        while dq and dq[-1][1] <= x:
            dq.pop()
        dq.append((i, x))
        if i >= k - 1:
            yield dq[0][1]

def brute_force_window_max(nums, k):
    return [max(nums[i:i + k]) for i in range(len(nums) - k + 1)]


nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
counters = {"push": 0, "pop": 0}
out = max_sliding_window(nums, k, counters)
print(f"nums={nums}, k={k}")
print(f"max_sliding_window -> {out}")
brute = brute_force_window_max(nums, k)
print(f"brute-force cross-check: {out} == {brute} -> {out == brute}")
assert out == brute

for edge_nums, edge_k in [([7], 1), ([4, 4, 4, 4], 2), ([9, 1, 2], 3)]:
    got = max_sliding_window(edge_nums, edge_k)
    expected = brute_force_window_max(edge_nums, edge_k)
    assert got == expected
print("edge cases (k=1, all-equal, k=len(nums)) passed")

n = len(nums)
print(f"n={n}: push_count={counters['push']}, pop_count={counters['pop']} "
      f"(pop_count <= push_count confirms amortized O(1) per element -> O(n) total)")

streamed = list(max_sliding_window_streaming(iter(nums), k))
print(f"max_sliding_window_streaming -> {streamed}")
assert streamed == out == brute
print("streaming variant matches the batch result and the brute force")

Output (executed, python3 s64_sliding_window_max.py, cross-checked against max(nums[i:i+k]) per window, plus k=1/all-equal/k==len(nums) edge cases):

nums=[1, 3, -1, -3, 5, 3, 6, 7], k=3
max_sliding_window -> [3, 3, 5, 5, 6, 7]
brute-force cross-check: [3, 3, 5, 5, 6, 7] == [3, 3, 5, 5, 6, 7] -> True
edge cases (k=1, all-equal, k=len(nums)) passed
n=8: push_count=8, pop_count=7 (pop_count <= push_count confirms amortized O(1) per element -> O(n) total)
max_sliding_window_streaming -> [3, 3, 5, 5, 6, 7]
streaming variant matches the batch result and the brute force

An instrumented run confirms the O(n) claim concretely rather than just asserting it: for n=8, the deque saw 8 pushes and 7 pops total, i.e. bounded work per element, not n*k work.

Trade-offs & pitfalls

• Comparing VALUES to decide expiry (instead of checking the stored INDEX against i - k) is a common bug: once you've popped by value you've lost the position information needed to know when something falls out of the window, especially with duplicate values in the array.
• Storing values instead of indices in the deque makes expiry-checking impossible for exactly that reason; the deque must hold indices (or (position, value) pairs in the streaming case).
• The sliding-window technique bounds the ALGORITHM's own working memory to O(k); if a downstream consumer needs the FULL history of window maxima rather than processing each one as it arrives, that consumer still needs its own O(n/k)-ish storage somewhere, which the windowing itself does not solve.
• A naive re-scan of the last k elements for every new window is O(n*k) and passes small test cases fine, which is why this problem specifically probes whether a candidate reaches for the monotonic-deque structure rather than stopping at the first working solution.

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.