Arrays, Strings, and Hashing Questions

Direct answer

Normalize both strings to the same Unicode normalization form and case-fold them, rather than just lowercasing, before counting characters. The same visual text can be represented by different underlying code point sequences, and case folding, not naive lowercasing, is the operation Unicode actually defines for caseless comparison across scripts. With that one extra normalization step, the same O(n) time, O(k) space frequency-map technique from the basic version still applies unchanged, k bounded by the number of distinct normalized characters.

Structured elaboration

Normalization forms. NFC (Normalization Form Canonical Composition, preferring a single precomposed character wherever one exists) and NFD (Normalization Form Canonical Decomposition, preferring a base character followed by separate combining marks) are two different, both entirely valid, code point sequences for the exact same visual text. "café" typed as a precomposed é is 4 code points; the same visual text with é written as "e" plus a combining acute accent is 5 code points. A character-by-character frequency count of the two, with no normalization step, sees different counts for literally identical text.

Casefold, not lower(). Python's str.lower() does not implement full Unicode case folding. The clearest example is German eszett: "straße".lower() leaves ß alone (still 6 characters), while "straße".casefold() expands it to "ss" (7 characters), which is the standard case-insensitive equivalence Unicode defines (ß case-folds to ss). casefold(), not lower(), is the correct building block for caseless comparison across languages.

Stated assumptions. This technique operates at the code point level after normalizing and case-folding, not at the full grapheme-cluster level (a base letter with several stacked combining marks, common in Vietnamese or Devanagari text, is a deeper case addressed only as a boundary note below, not solved here). str.isalnum() in Python is Unicode-aware across scripts, not an ASCII-only check, so it correctly drops whitespace and punctuation in non-Latin text too. Whichever normalization form you pick, NFC or NFD, must be applied consistently to both input strings, the specific form chosen does not matter as long as it is the same on both sides of the comparison.

Worked example

import unicodedata
from collections import Counter

def _normalize_for_anagram(x: str, form: str = "NFC"):
    x = unicodedata.normalize(form, x)
    x = x.casefold()
    return [c for c in x if c.isalnum()]

def is_anagram_unicode(s: str, t: str) -> bool:
    ns, nt = _normalize_for_anagram(s), _normalize_for_anagram(t)
    if len(ns) != len(nt):
        return False
    return Counter(ns) == Counter(nt)

cafe_nfc = "caf" + chr(0x00E9)
cafe_nfd = "caf" + chr(0x0065) + chr(0x0301)
print("NFC form code points:", [hex(ord(c)) for c in cafe_nfc])
print("NFD form code points:", [hex(ord(c)) for c in cafe_nfd])
print()

def is_anagram_naive(s, t):
    def normalize(x):
        return [c.lower() for c in x if c.isalnum()]
    ns, nt = normalize(s), normalize(t)
    return len(ns) == len(nt) and Counter(ns) == Counter(nt)

print(f"is_anagram_naive(NFC {cafe_nfc!r}, NFD {cafe_nfd!r})   = {is_anagram_naive(cafe_nfc, cafe_nfd)}  (WRONG: same text, flagged as non-anagram)")
print(f"is_anagram_unicode(NFC {cafe_nfc!r}, NFD {cafe_nfd!r})  = {is_anagram_unicode(cafe_nfc, cafe_nfd)}  (correct: same text -> True)")
print()

strasse = "stra" + chr(0x00DF) + "e"
print(f"{strasse!r}.lower()    = {strasse.lower()!r}  (len {len(strasse.lower())})")
print(f"{strasse!r}.casefold() = {strasse.casefold()!r}  (len {len(strasse.casefold())})")
print(f"is_anagram_naive({strasse!r}, 'strasse')   = {is_anagram_naive(strasse, 'strasse')}  (WRONG: length mismatch under .lower())")
print(f"is_anagram_unicode({strasse!r}, 'strasse')  = {is_anagram_unicode(strasse, 'strasse')}  (correct: casefold equates ss/eszett)")
print()

import random
base = "ΟΔΥΣΣΕΥΣ"
shuffled = list(base.casefold())
random.Random(42).shuffle(shuffled)
shuffled_str = "".join(shuffled)
print(f"shuffled multilingual case: {base!r} vs {shuffled_str!r}")
print(f"is_anagram_unicode -> {is_anagram_unicode(base, shuffled_str)} (expected True: same multiset of letters, just reordered and re-cased)")
other = "ΑΘΗΝΑ"
print(f"is_anagram_unicode({base!r}, {other!r}) -> {is_anagram_unicode(base, other)} (expected False)")

Output:

NFC form code points: ['0x63', '0x61', '0x66', '0xe9']
NFD form code points: ['0x63', '0x61', '0x66', '0x65', '0x301']

is_anagram_naive(NFC 'café', NFD 'café')   = False  (WRONG: same text, flagged as non-anagram)
is_anagram_unicode(NFC 'café', NFD 'café')  = True  (correct: same text -> True)

'straße'.lower()    = 'straße'  (len 6)
'straße'.casefold() = 'strasse'  (len 7)
is_anagram_naive('straße', 'strasse')   = False  (WRONG: length mismatch under .lower())
is_anagram_unicode('straße', 'strasse')  = True  (correct: casefold equates ss/eszett)

shuffled multilingual case: 'ΟΔΥΣΣΕΥΣ' vs 'σσυσυεοδ'
is_anagram_unicode -> True (expected True: same multiset of letters, just reordered and re-cased)
is_anagram_unicode('ΟΔΥΣΣΕΥΣ', 'ΑΘΗΝΑ') -> False (expected False)

The NFC-versus-NFD case is the sharpest demonstration: the same literal text "café", represented two different (both entirely valid) ways, is wrongly flagged as not an anagram of itself by a naive .lower()-plus-Counter check, and correctly flagged as one once both sides are normalized to the same form first. The eszett case shows the same pattern for casing: .lower() leaves the two strings at different lengths (a real bug, not a subtlety), while .casefold() correctly equates them. A genuine multilingual anagram (the Greek letters of "ΟΔΥΣΣΕΥΣ", deterministically shuffled with random.Random(42)) confirms the technique still does its actual job, correctly returning True for a real anagram and False against unrelated Greek text ("ΑΘΗΝΑ").

Trade-offs and pitfalls

Code-point-level comparison after normalization is the practical, standard-interview-depth answer, but it is not full grapheme-cluster equality: text that stacks multiple combining marks on one base character can, in principle, be grouped differently by two representations that both eventually normalize to the same NFC form by a different path. In practice NFC handles the overwhelming majority of real-world multilingual text correctly; fully grapheme-cluster-safe comparison is a further, rarely-needed step beyond what this answer implements.

Order matters: normalize first, then case-fold, not the reverse, and not .lower() after normalizing instead of .casefold(). Applying case-folding to whichever normalization form you've already settled on gives a consistent answer regardless of how the input arrived; mixing the order or substituting .lower() reintroduces exactly the bugs demonstrated above.

This machinery, normalize plus casefold, is the multilingual, standards-based extension of the same technique as plain .lower(). Reach for it specifically when the input is genuinely multilingual or user-generated text, not as the default on every anagram check, the plain version is simpler and sufficient for ASCII-only input.

Direct answer

Group strings that are anagrams of each other by mapping each string to a canonical key that is identical for all of its anagrams and different otherwise, then bucket strings by that key in a hash map. The two standard keys are the sorted-character string (simple, O(L log L) per string) and a fixed-length character-frequency vector (O(L) per string, faster for long strings, but only straightforward for a small, known, fixed alphabet).

Structured elaboration

Approach 1: sorted string as key

Sort each string's characters and join them back into a string; two strings are anagrams exactly when this sorted form is identical. Sorting a string of length L costs O(L log L), so grouping n strings this way costs O(n * L log L) in total, where L is the average or maximum string length.

Approach 2: frequency vector as key

Count the occurrences of each character into a fixed-size array (26 entries for lowercase English letters), then use that array, converted to an immutable tuple so it can be a hash-map key, as the grouping key. Building the count for one string costs O(L), so this approach costs O(n * (L + alphabet_size)) in total, asymptotically better than the sorted-key approach once L is large relative to log L, since counting avoids the sort entirely. The trade-off is that this fixed-size-array trick assumes a small, KNOWN alphabet; it does not generalize as cleanly the moment the alphabet is unbounded.

Unicode input

Both approaches need care once the input can contain arbitrary Unicode text rather than plain lowercase English letters. The frequency-vector approach's fixed 26-slot array breaks down immediately, since Unicode text can contain far more than 26 distinct characters; the practical fix is a hash map from character to count instead of a fixed array, which still works but loses the small constant-factor advantage of a fixed array. More subtly, even the sorted-key approach can give a WRONG answer on Unicode input if two visually and semantically identical strings are represented by different underlying code point sequences: an accented character can be represented either as a single precomposed code point, or as the base letter followed by a separate combining accent mark. These compare as different strings and produce different sorted keys even though they represent the same text. The fix is to first normalize every string using Unicode Normalization Form C (NFC), which canonicalizes precomposed and decomposed forms to the same representation, before computing either kind of key.

Performance for long strings and memory trade-offs

For long strings, the frequency-vector approach avoids the L log L sorting cost, which matters when strings are long, for example grouping DNA-like sequences or long tokenized identifiers rather than short English words. Memory-wise, the sorted-key approach's key is proportional to the string's own length, while the frequency-vector key has a FIXED size (26 entries, or however many distinct characters the chosen alphabet has) regardless of the string's length, which can be smaller for long strings but is pure overhead for very short ones.

Worked example

from collections import defaultdict
import unicodedata

def group_anagrams_sorted_key(strs):
    groups = defaultdict(list)
    for s in strs:
        key = ''.join(sorted(s))
        groups[key].append(s)
    return list(groups.values())

def group_anagrams_freq_key(strs, alphabet_size=26):
    groups = defaultdict(list)
    for s in strs:
        counts = [0] * alphabet_size
        for ch in s:
            counts[ord(ch) - ord('a')] += 1
        groups[tuple(counts)].append(s)
    return list(groups.values())

strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(group_anagrams_sorted_key(strs))
print(group_anagrams_freq_key(strs))

def normalize_for_unicode_anagram_key(s):
    return ''.join(sorted(unicodedata.normalize('NFC', s)))

precomposed = "café"          # single code point for e-acute
decomposed = "café"          # 'e' + combining acute accent
print(precomposed == decomposed)
print(''.join(sorted(precomposed)) == ''.join(sorted(decomposed)))
print(normalize_for_unicode_anagram_key(precomposed) == normalize_for_unicode_anagram_key(decomposed))

Output:

[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
False
False
True

Both approaches group the same six words into the same three anagram groups. The Unicode section demonstrates the normalization issue directly: two strings that print identically and represent the same visible text, cafe with an accented e built from a single precomposed code point versus the same word built from a base letter plus a separate combining accent mark, compare as unequal Python strings, and their naive sorted-character keys also disagree, but normalizing both to NFC before computing the key makes them match, exactly the correctness gap this section describes.

Trade-offs and pitfalls

A common mistake is assuming string equality in Python already handles Unicode normalization: it does not, two strings built from a precomposed versus a decomposed representation of the same visible text can compare as unequal, which silently splits what should be one anagram group into two. A second is hardcoding a 26-entry frequency array without checking the actual input alphabet, which either crashes on characters outside a-z or silently produces wrong groupings once real-world text with punctuation, digits, or non-English characters shows up. For genuinely massive input, the scale this problem is asked at in a batch-processing context, well beyond what fits comfortably in memory as one hash map, the practical extension is external-memory or streaming grouping: sort the (key, original-string) pairs using an external merge sort so anagrams become adjacent on disk without needing every group held in memory at once, or shard by a prefix of the key across multiple workers so each worker only needs to hold its own shard's groups in memory. That is a genuine and reasonable extension of this same technique at scale, but it is a distinct system-design problem from choosing a grouping key, and is mentioned here only as the natural next question, not as something this answer needs to design in full. The same two key strategies carry over unchanged in Java (HashMap<String, List<String>> or HashMap<List<Integer>, List<String>>) and JavaScript (a Map keyed on the same sorted-string or frequency-array-as-string idea).

Direct answer

Track two running arrays indexed by "how many transactions used so far": buy[j] (best running profit while holding a share, having started the j-th buy) and sell[j] (best running profit while not holding, having completed the j-th sell), and update both for every price in a single left-to-right pass. This is O(n * k) time and O(k) space. There is also a special case: once k is at least n // 2, there can never be more than n // 2 genuinely profitable non-overlapping transactions regardless of how large k is, so the problem collapses to unlimited transactions, solvable greedily in O(n) time by summing every positive day-to-day price increase.

Algorithm

For each day's price, and for each transaction count j from 1 to k:

• buy[j] = max(buy[j], sell[j-1] - price): either keep the best "holding" position already found for the j-th buy, or start a new j-th buy today, financed by whatever profit was banked after the (j-1)-th sell.
• sell[j] = max(sell[j], buy[j] + price): either keep the best "sold" position already found for the j-th sell, or sell today's holding for today's price.

Because buy[j] on the right-hand side is this day's just-updated value, sell[j] on the same day can reflect a buy-and-sell on the same day (a net-zero move, which never hurts an optimal solution since it's equivalent to not trading), while still processing the array in one pass with two length-(k+1) arrays rather than a full 2D table.

def max_profit_k_transactions(prices, k):
    n = len(prices)
    if n == 0 or k == 0:
        return 0

    if k >= n // 2:
        return sum(max(0, prices[i] - prices[i - 1]) for i in range(1, n))

    buy = [float("-inf")] * (k + 1)
    sell = [0] * (k + 1)
    for price in prices:
        for j in range(1, k + 1):
            buy[j] = max(buy[j], sell[j - 1] - price)
            sell[j] = max(sell[j], buy[j] + price)
    return sell[k]

Why k >= n // 2 collapses to unlimited transactions

Every transaction consumes at least 2 distinct days (one buy day, one sell day), and a set of non-overlapping transactions can't reuse a day. So no more than n // 2 transactions can ever be simultaneously "active" in an optimal non-overlapping schedule; once the allowed k reaches that ceiling, the constraint is no longer binding; you may as well capture every single profitable up-move independently, since doing so never uses more than n // 2 actual buy/sell pairs (adjacent up-runs merge into one transaction each) and no constrained schedule can beat the unconstrained greedy optimum.

Worked example

from functools import lru_cache

def max_profit_memoized(prices, k):
    n = len(prices)

    @lru_cache(maxsize=None)
    def rec(day, txns_used, holding):
        if day == n or txns_used == k:
            return 0
        best = rec(day + 1, txns_used, holding)
        if holding:
            best = max(best, prices[day] + rec(day + 1, txns_used + 1, False))
        else:
            best = max(best, -prices[day] + rec(day + 1, txns_used, True))
        return best

    result = rec(0, 0, False)
    rec.cache_clear()
    return result

cases = [
    ([2, 4, 1], 2),
    ([3, 2, 6, 5, 0, 3], 2),
    ([1, 2, 4, 2, 5, 7, 2, 4, 9, 0], 3),
]
for prices, k in cases:
    fast = max_profit_k_transactions(prices, k)
    memoized = max_profit_memoized(prices, k)
    print(f"max_profit_k_transactions({prices}, k={k}) = {fast}  (memoized cross-check: {memoized}, agree: {fast == memoized})")

Output (verified by execution, and cross-checked against an independently-implemented memoized recursion over (day, transactions_used, holding) for every case, a genuinely different formulation, not the same array-DP checked against itself):

max_profit_k_transactions([2, 4, 1], k=2) = 2  (memoized cross-check: 2, agree: True)
max_profit_k_transactions([3, 2, 6, 5, 0, 3], k=2) = 7  (memoized cross-check: 7, agree: True)
max_profit_k_transactions([1, 2, 4, 2, 5, 7, 2, 4, 9, 0], k=3) = 15  (memoized cross-check: 15, agree: True)

For [3, 2, 6, 5, 0, 3] with k=2: the optimal schedule is buy at 2 (index 1), sell at 6 (index 2), profit 4; buy at 0 (index 4), sell at 3 (index 5), profit 3; total 7, using exactly 2 of the allowed 2 transactions, matching the DP's answer. For [1, 2, 4, 2, 5, 7, 2, 4, 9, 0] with k=3: buy 1 sell 4 (profit 3), buy 2 sell 7 (profit 5), buy 2 sell 9 (profit 7), total 15, again using all 3 allowed transactions and matching the largest 3 disjoint up-runs in the sequence.

Trade-offs and pitfalls

• k small vs k large is a genuine complexity cliff, not a smooth trade-off: for small k (say, single or low double digits), O(n*k) is fast and the array-DP above is the right tool. For large k (specifically once k >= n // 2), the same DP still gives the correct answer but does unnecessary work; recognizing and special-casing the collapse to the O(n) greedy is the difference between an interviewer seeing a complete answer and a merely correct-but-naive one.
• Off-by-one in the collapse threshold is a common mistake: it's n // 2, not n / 2 rounded up or n - 1; a schedule needs 2 distinct days per transaction, so n days support at most n // 2 non-overlapping transactions (floor division).
• The buy[j] = sell[j-1] - price recurrence is the crux most people get wrong on their own the first time: it's tempting to write buy[j] - price (buying doesn't "cost" anything against your own already-open position; it should reset from the state before this transaction started, i.e., sell[j-1], the profit banked from the previous, already-closed transaction).
• This is a good example of the topic's own boundary: the natural solution technique here is DP-style state tracking over transaction count, but the practical implementation is two flat arrays updated in a single array pass, not a full 2D recursive table, the same reasoning that keeps Kadane's algorithm and expand-around-center palindrome checks classified as array-manipulation technique rather than routed to a dedicated dynamic-programming topic.

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

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.