Arrays, Strings, and Hashing Questions

Direct answer

Make a single pass over the list and accumulate counts in a hash map (Python's collections.Counter, which is a dict subclass purpose-built for this): for each string, increment its entry by one. This is O(n) time, where n is the total number of strings processed, and O(u) extra space, where u is the number of unique strings, which for typical real-world data (repeated categorical values, tokens, log lines) is far smaller than n itself, keeping the approach both time- and memory-efficient at the "millions of items" scale the question asks about.

Structured elaboration

Why a hash map is the right tool here. Counting occurrences requires answering "have I seen this exact value before, and how many times" for each item, which is precisely the operation a hash map is built to do in O(1) average time per lookup/update. Building the count dict is therefore a single O(n) pass: for each string, look up its current count (defaulting to 0 if new) and increment it. Counter does exactly this internally and additionally provides convenience methods (most_common(), direct construction from an iterable) on top of a plain dict.

Time and space, stated precisely. Time is O(n) because every one of the n input strings is visited exactly once, and each hash map update is O(1) amortized. Space is O(u), the number of distinct strings, not O(n): a list with heavy repetition (say, a categorical column with only a handful of distinct values repeated millions of times) uses memory proportional to that handful of distinct values, not to the list's full length. This distinction between n (total items) and u (unique items) is the detail that actually matters for the "millions of items" framing in the question, since it is u, not n, that determines the dict's memory footprint.

Applying the same technique at a narrower grain: counting vowels in a string. The identical hash-based counting technique applies just as well one level down, to counting occurrences of specific characters within a single string rather than counting occurrences of whole strings within a list. A case-insensitive vowel count is the same idea: fold case first (so 'A' and 'a' count as the same vowel), then check each character against a fixed small set of vowels, incrementing a running total. Because the set of vowels is fixed and tiny (5 characters), this doesn't even need a full frequency dict. A simple counter check against a frozenset suffices, which is O(n) time (n = length of the single string) and O(1) extra space, since the vowel set's size never grows with input size.

Worked example

Full runnable code with pinned test cases, including the question's own example and the vowel-counting variant:

from collections import Counter


def string_frequencies(strings):
    """O(n) time (n = total strings), O(u) extra space (u = unique strings)."""
    return dict(Counter(strings))


def count_vowels(s, vowels=frozenset("aeiou")):
    """Same hash-based technique applied to characters of one string instead
    of elements of a list: case-insensitive vowel count, O(n) time, O(1)
    extra space (the vowel set has fixed size 5, independent of len(s))."""
    return sum(1 for ch in s.casefold() if ch in vowels)


if __name__ == "__main__":
    data = ['a', 'b', 'a', 'c', 'b', 'a']
    result = string_frequencies(data)
    print(f"string_frequencies({data!r}) = {result!r}")

    vowel_tests = [
        ("Hello World", 3),
        ("AEIOUaeiou", 10),
        ("xyz", 0),
        ("", 0),
        ("Interview", 4),
    ]
    for s, expected in vowel_tests:
        r = count_vowels(s)
        print(f"count_vowels({s!r}) = {r} (expected {expected})")

Output (actual run):

string_frequencies(['a', 'b', 'a', 'c', 'b', 'a']) = {'a': 3, 'b': 2, 'c': 1}
count_vowels('Hello World') = 3 (expected 3)
count_vowels('AEIOUaeiou') = 10 (expected 10)
count_vowels('xyz') = 0 (expected 0)
count_vowels('') = 0 (expected 0)
count_vowels('Interview') = 4 (expected 4)

The first line matches the question's own example exactly: ['a','b','a','c','b','a'] -> {'a': 3, 'b': 2, 'c': 1}. The count_vowels('Interview') case is worth naming explicitly: the capital I counts alongside the lowercase e, i, e, since .casefold() runs before the membership check, giving 4 total (I, e, i, e), matching a case-insensitive count rather than an ASCII-literal one.

Trade-offs and pitfalls

• Sorting the list first and counting runs of equal adjacent elements is a valid alternative, but costs O(n log n) time versus the hash map's O(n), and it also destroys the original ordering unless a copy is sorted separately; for "moderate lists (millions of items)" as the question specifies, the linear hash-map approach is the better default.
• Counter(strings) alone already returns a fully-functional mapping; wrapping it in dict(...) here is purely to return a plain, predictable type to a caller who may not want Counter-specific behavior (like its most_common() method or its handling of missing keys returning 0 instead of raising KeyError); either is a reasonable answer, and it's worth naming the trade-off rather than silently picking one.
• For truly massive inputs that don't fit in memory as a single Python list (as opposed to "millions of items," which a modern machine handles comfortably in RAM), the same technique still applies conceptually: replace strings with a generator/iterator and update a single running Counter one item (or one fixed-size chunk) at a time via .update(), instead of ever materializing the whole input as a list. Peak memory then holds only the current item or chunk plus the running counts, not the full input; the counting operation itself does not change, only how the input is fed into it.
• A frequency count over Unicode strings needs the same normalization awareness as any other string-identity comparison: two strings that look identical but differ in Unicode representation (composed versus decomposed accented characters) will be counted as different keys unless normalized first, which matters if the input list can contain non-ASCII text.
• For the vowel-counting variant specifically, .casefold() is the correct choice over .lower() for the same reason it matters in general caseless comparison: locale-independent, more aggressive folding handles edge cases like the German sharp s correctly, though for a fixed 5-character ASCII vowel set this distinction rarely changes the result in practice; naming .casefold() anyway signals the same caseless-comparison discipline that matters whenever a comparison needs to be genuinely Unicode-safe.

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

Use a read/write two-pointer: walk the array once with a read index, and every time you see a value that isn't val, copy it into the next open slot tracked by a write index. The write index at the end is the new length. Whether order must be preserved decides which of two variants you use: the read/write copy above preserves the original relative order in O(n) writes; if order doesn't matter, you can instead swap a matching element with the current last element and shrink the array, which does fewer writes when val is rare.

Approach

1. Order-preserving (read/write two-pointer): write starts at 0. For each read index in order, if nums[read] != val, copy it to nums[write] and advance write. Every kept element lands in its original relative order, one slot earlier than or at its original position.
2. Order-not-preserved (swap-with-last): keep a shrinking logical length n. When nums[i] == val, overwrite it with nums[n-1] (the current last element) and shrink n by one, without advancing i (the swapped-in element still needs to be checked). When nums[i] != val, advance i. This does one write per removal instead of potentially shifting every later element, which is cheaper when matches are rare and scattered.
3. Both mutate nums in place and return the new length; elements at or past the returned length are not meaningfully defined afterward.

Complexity

Both variants: O(n) time (single pass), O(1) extra space. The order-preserving version always does one write per surviving element; the swap variant does one write per removed element, which is fewer when val is rare.

Edge cases

• val not present at all: every element is kept, new length equals original length, zero writes beyond the initial pass.
• All elements equal val: new length is 0.
• Empty input: returns 0 immediately.

def remove_element(nums, val):
    write = 0
    for read in range(len(nums)):
        if nums[read] != val:
            nums[write] = nums[read]
            write += 1
    del nums[write:]
    return write


def remove_element_unordered(nums, val):
    i = 0
    n = len(nums)
    while i < n:
        if nums[i] == val:
            n -= 1
            nums[i] = nums[n]
        else:
            i += 1
    del nums[n:]
    return n


payload = [4, 2, 5, 2, 7, 2, 9]
k = remove_element(payload, 2)
print(k, payload)

payload2 = [4, 2, 5, 2, 7, 2, 9]
k2 = remove_element_unordered(payload2, 2)
print(k2, payload2)

Output:

4 [4, 5, 7, 9]
4 [4, 9, 5, 7]

Both agree on the count (4 surviving elements), but the surviving values land in different positions: [4, 5, 7, 9] keeps the original left-to-right order, while [4, 9, 5, 7] does not (9 moved from the end into an earlier slot during a swap), which is exactly the trade-off the question is asking about.

Trade-offs and pitfalls

• A common bug: using list.remove(val) or deleting elements from the middle of the array inside a loop, which is O(n) per removal (everything after the deletion point shifts down), making the whole operation O(n^2) in the worst case, and it also skips the next element if you don't adjust the loop index after a deletion. The two-pointer approaches here avoid both problems.
• The same read/write two-pointer technique applies directly to low-level, fixed-size buffers, not just Python lists. In C, given a null-terminated char *s, removing all space characters in place is the identical idea: a write index and a read index both walk the buffer, the write index only advances when the current character should be kept, and a null terminator is placed at the final write position. There's no list-resize step (del nums[write:]) because a C string doesn't carry a separate length field the way a Python list does; the null terminator is the length.
• Backend-cleanup framing from the question: "compacting payload arrays before storage" is exactly the order-preserving case if the array represents an ordered sequence (e.g. a time-ordered log) where reordering would corrupt meaning, or the order-not-preserved case if it's an unordered set of records where minimizing writes matters more than position.

Direct answer

If every element is guaranteed non-negative, a sliding window works: grow the window's sum, and shrink from the left whenever the sum overshoots the target, because adding a non-negative element can only increase or hold the sum, so shrinking is guaranteed to monotonically decrease it. Once negative numbers are allowed, that monotonicity breaks, so the general solution instead tracks prefix sums in a hash map: if prefix[i] - prefix[j] == target, the subarray from j+1 to i sums to target, so scanning once while checking whether running_sum - target has been seen before as an earlier prefix sum finds the answer in O(n) time and O(n) space.

Positive-only case: sliding window

def subarray_indices_positive_only(nums, target):
    left = 0
    running = 0
    for right, val in enumerate(nums):
        running += val
        while running > target and left <= right:
            running -= nums[left]
            left += 1
        if running == target:
            return (left, right)
    return None

This relies entirely on non-negativity: shrinking the window (removing nums[left]) can only decrease running, so the while running > target loop is guaranteed to terminate at a sum that is <= target, and if it lands exactly on target, that's a valid answer. With negative numbers present, removing an element from the left could just as easily increase the running sum as decrease it, so there is no longer a reliable direction to shrink in.

General case (including negatives): prefix sum plus hash map

def subarray_indices_prefix_hashmap(nums, target):
    prefix_to_index = {0: -1}   # empty prefix (before index 0) sums to 0
    running = 0
    for i, val in enumerate(nums):
        running += val
        needed = running - target
        if needed in prefix_to_index:
            return (prefix_to_index[needed] + 1, i)
        if running not in prefix_to_index:
            prefix_to_index[running] = i
    return None

The {0: -1} seed entry is what lets a subarray starting at index 0 be found correctly: it represents "the prefix sum before any elements have been added is 0," so if running itself ever equals target, needed = running - target = 0 is already in the map, pointing to index -1, giving a correct start index of 0. The if running not in prefix_to_index guard only stores the first occurrence of each prefix sum, which is what guarantees the returned subarray is as long as possible from that starting point rather than an arbitrarily chosen one (though any correct pair satisfies "sums to target"; the problem only asks for existence, not the shortest or longest one).

Worked example

def brute_force_subarray_indices(nums, target):
    n = len(nums)
    for i in range(n):
        s = 0
        for j in range(i, n):
            s += nums[j]
            if s == target:
                return (i, j)
    return None

r1 = subarray_indices_positive_only([1, 2, 3, 4, 5], 9)
r2 = subarray_indices_prefix_hashmap([1, -1, 5, -2, 3], 3)
print(r1, " (brute-force cross-check:", brute_force_subarray_indices([1, 2, 3, 4, 5], 9), ")")
print(r2, " (brute-force cross-check:", brute_force_subarray_indices([1, -1, 5, -2, 3], 3), ")")

Output (verified by execution, both cross-checked against an O(n^2) brute-force reference that tries every contiguous subarray directly):

(1, 3)  (brute-force cross-check: (1, 3) )
(0, 3)  (brute-force cross-check: (0, 3) )

For [1, 2, 3, 4, 5], target 9: the window grows through [1], [1,2], [1,2,3] to [1,2,3,4] (sum 10), which overshoots; one shrink step drops the leading 1, bringing the sum to exactly 9 with the window now [2,3,4] (indices 1-3), which matches immediately, returning (1, 3). For [1, -1, 5, -2, 3], target 3: the running prefix sums as the scan proceeds are 1, 0, 5, 3 (indices 0-3), with needed = running - target at each step -2, -3, 2, 0. At i=3, needed = 0, which IS in the map, but crucially it maps to index -1 (the seed entry), not index 1 (where prefix sum 0 also occurs, at i=1, from 1 + -1 = 0): the if running not in prefix_to_index guard means that once index -1 claims prefix-sum 0, the later occurrence at index 1 is never allowed to overwrite it. So the match resolves to (-1 + 1, 3) = (0, 3), i.e., the subarray [1, -1, 5, -2], which does sum to 1 + -1 + 5 + -2 = 3.

Trade-offs and pitfalls

• The sliding window is NOT a valid fallback once any negative number can appear, even a single one. A frequent mistake is applying the two-pointer shrink logic to "mostly positive" data and only breaking on adversarial inputs; the moment even one negative value is possible, the general prefix-sum-plus-hashmap approach is required for correctness, not just performance.
• The {0: -1} seed entry is the single most commonly dropped detail. Without it, any subarray that must start at index 0 is silently missed, because there is no recorded "prefix sum before the array starts" to subtract against.
• Storing only the first occurrence of each prefix sum (via the if running not in prefix_to_index guard) is a deliberate choice, not an accident: if the problem instead asked for the shortest subarray summing to target, this is exactly right; if it asked for the count of subarrays summing to target (a related but different problem), the correct approach is to track counts, not indices, and accumulate every match rather than returning early on the first one.
• Return-value ambiguity: this implementation returns any one valid subarray's indices (existence), which matches what the question asks; a caller wanting all valid subarrays, or the shortest, or the count, needs a variant of this same prefix-sum idea, not a fundamentally different algorithm.

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.