Arrays, Strings, and Hashing Questions

Direct answer

Slide a fixed-size window of length len(p) across s, tracking the window's contents with two fixed-size frequency arrays (as the question specifies), one for p's required counts and one for the current window, indexed directly by character rather than through hashing. Updating the window incrementally (increment the entering character's slot, decrement the exiting character's slot) rather than rebuilding and comparing a fresh count every position is what makes this O(n) instead of O(n * |p|). Space is O(alphabet size): for lowercase English letters, that is a fixed 26 integers regardless of how long s or p are.

Algorithm

1. Build need, a length-26 array of p's character counts (need[ord(ch) - ord('a')] += 1 for each character in p).
2. Initialize window as the length-26 count array of s's first len(p) characters.
3. If window == need (array-to-array comparison), index 0 is a match.
4. Slide the window one character at a time: increment the slot of the character entering on the right, decrement the slot of the character leaving on the left, and compare window == need again after each slide.

def find_anagrams(s: str, p: str) -> list:
    len_s, len_p = len(s), len(p)
    if len_p > len_s:
        return []

    def index_of(ch):
        return ord(ch) - ord("a")

    need = [0] * 26
    window = [0] * 26
    for ch in p:
        need[index_of(ch)] += 1
    for ch in s[:len_p]:
        window[index_of(ch)] += 1

    result = []
    if window == need:
        result.append(0)

    for i in range(len_p, len_s):
        incoming, outgoing = s[i], s[i - len_p]
        window[index_of(incoming)] += 1
        window[index_of(outgoing)] -= 1
        if window == need:
            result.append(i - len_p + 1)
    return result

Using a fixed-size array indexed directly by ord(ch) - ord('a'), rather than a hash map keyed by the character, is exactly what "frequency array" means here: no hashing, no key deletion bookkeeping (a count naturally sits at 0 in an untouched slot, so there is nothing to clean up the way there would be with a dict-based count map), and the window == need comparison is a fixed-length list comparison, always exactly 26 elements, regardless of the alphabet actually observed in a given window. This assumes a known, bounded alphabet (lowercase English letters, size 26 here); for Unicode or an unbounded alphabet, a hash map keyed by character is the structure that scales with distinct characters actually seen instead of the size of the declared alphabet, at the cost of per-key hashing overhead.

Applications for substring pattern detection in tokenized text

The same fixed-size-window-plus-count-comparison technique applies directly to detecting "this window of tokens is a rearrangement of a target token multiset," which comes up in tasks like flagging text spans that contain exactly the same word multiset as a suspicious phrase (word-order-scrambled plagiarism or obfuscation detection) or matching a fixed-size set of required tags in a tokenized log line regardless of their order. The technique is identical, only the "character" unit changes to "token."

Worked example

def brute_force_find_anagrams(s, p):
    len_p = len(p)
    target = sorted(p)
    result = []
    for i in range(len(s) - len_p + 1):
        if sorted(s[i:i+len_p]) == target:
            result.append(i)
    return result

tests = ["cbaebabacd", "abab", "aaaaaaaaaa"]
patterns = ["abc", "ab", "aaa"]
for s, p in zip(tests, patterns):
    fast = find_anagrams(s, p)
    brute = brute_force_find_anagrams(s, p)
    print(f"find_anagrams({s!r}, {p!r}) = {fast}  (brute-force agrees: {fast == brute})")

Output (verified by execution, and cross-checked against an O(n * k log k) brute-force reference that sorts every window directly, so the fast result's correctness is independently confirmed rather than assumed):

find_anagrams('cbaebabacd', 'abc') = [0, 6]  (brute-force agrees: True)
find_anagrams('abab', 'ab') = [0, 1, 2]  (brute-force agrees: True)
find_anagrams('aaaaaaaaaa', 'aaa') = [0, 1, 2, 3, 4, 5, 6, 7]  (brute-force agrees: True)

Tracing s='cbaebabacd', p='abc' (need = {a:1, b:1, c:1}): the window at index 0 is "cba", whose counts exactly match need, so index 0 is recorded. Sliding to index 1 gives "bae", which introduces 'e' (not in need at all) so it fails to match. The window keeps sliding until index 6, "bac" (b,a,c), which again matches need exactly, giving the second recorded index. No other window in between matches because each contains either a repeated letter with the wrong count or a letter ('e', 'd') that need doesn't have at all.

Trade-offs and pitfalls

• Comparing two full 26-length arrays on every slide is itself O(alphabet size) per comparison, not O(1), so even though the alphabet here is small and fixed, this is not free; a common refinement is to track a single integer "how many of the 26 positions currently match between the two arrays" (the same trick used in minimum-window-substring problems), updated incrementally as each slide changes at most two positions, which turns the check into O(1) instead of O(26) per step.
• The frequency-array approach assumes a known, bounded alphabet. It is the right choice here (lowercase English letters) precisely because the question specifies it; for Unicode text or an unbounded token vocabulary, a hash map keyed by the actual character or token is what scales with distinct values seen, and switching to one is a straightforward substitution of the counting structure without changing the sliding-window logic itself.
• This is a fixed-size window, unlike minimum-window-substring's variable-size window: the window length here is always exactly len(p), which is simpler (no shrink/grow decision needed) but means the technique doesn't generalize to "smallest window containing X" problems without the additional grow/shrink logic those require.
• Edge cases: p longer than s (no window can exist, return empty immediately), p empty (depends on the problem's intended contract, typically treated as matching every position or explicitly disallowed), and heavily repeated characters in s (as in the 'aaaaaaaaaaaa'/'aaa' case above), which stress-test that the sliding update (not a full rebuild) is genuinely being used, since a naive re-slice-and-recount implementation would still pass correctness tests here but silently lose its performance advantage.

Direct answer

.apply() with a Python function calls the interpreter once per row, so its cost is dominated by Python function-call and frame overhead repeated 10 million times. Series.str methods look vectorized but for the default pandas object dtype they are a C-level loop that still calls Python string methods per element internally, so they mainly remove the apply/lambda call overhead, not the per-element string-processing cost itself. numpy.char gives genuine C-level looping, but it first requires converting the column to a fixed-width NumPy unicode array, and every string gets padded to the length of the LONGEST string in the column, which can be a serious memory cost with even one long outlier in 10 million rows. For real vectorized speed at that scale the accurate move is pandas' PyArrow-backed string dtype (or stepping outside pandas entirely to Polars), not numpy.char.

Structured elaboration

.apply() (Python loop). Complexity is O(n) but with a large constant factor: each row triggers a full Python function call (frame creation, bytecode dispatch inside the lambda, boxing/unboxing of Python string objects). Nothing about this is vectorized; it is a disguised Python for loop.

Series.str vectorized methods. For the default object dtype, a pandas string column is a NumPy array of POINTERS to individual Python str objects. .str.lower(), .str.strip(), and similar calls are implemented as a loop (in Cython, faster than a Python-level for) that still invokes the underlying Python string method on each element. This removes the per-row apply/lambda call overhead and Python-level loop bookkeeping, so it is typically faster than .apply(), but it is not vectorized in the CPU/SIMD sense the way numpy arithmetic on a float array is: each element still gets an individual Python-level string operation.

numpy.char functions. These operate on a fixed-width NumPy unicode array (dtype like <U12), which is genuinely vectorized C code with no per-element Python call. The cost is that building this array from a pandas string column requires padding (or truncating) every entry to a single common width, namely the length of the longest string present. A column of mostly 10-character strings with one 500-character outlier forces every row's underlying buffer to 500 characters, multiplying memory by roughly 50x for no reason related to the average case. numpy.char also does not implement every string operation (there is no vectorized split), so a full tokenization pipeline cannot be done in numpy.char alone: the final split step still needs a Python-level loop or a different tool.

Getting genuine vectorization at 10M rows. pandas 2.x's PyArrow-backed string dtype (pd.ArrowDtype(pa.string()), or the shorthand "string[pyarrow]") stores strings in Arrow's variable-length UTF-8 buffer format and executes string operations through Arrow's compiled compute kernels: no fixed-width padding, and per-element cost is a real vectorized cost reduction rather than just less interpreter overhead. This is the currently recommended path for large string columns in pandas specifically because it avoids both the numpy.char padding tax and the object-dtype per-element Python-call tax. Where the workload no longer fits comfortably in memory or on one core, moving outside pandas to Polars (native vectorized string kernels, no object-dtype layer) or Dask (chunked, parallel, out-of-core) is the next step up.

How you would actually measure it. Time comparisons should use a repeatable, environment-relative tool (timeit/%timeit in a notebook, or time.perf_counter around repeated runs) and be reported as a RATIO between approaches on the same machine and the same data, not as an absolute number, because absolute wall-clock time is hardware- and load-dependent and will not reproduce on a different machine. Memory should be measured with tracemalloc for general Python allocations or, pandas-specifically, DataFrame.memory_usage(deep=True) (the deep=True flag matters: without it, an object-dtype column reports only the size of the pointer array, not the actual string objects it points to, which drastically understates real memory use).

Optimizing the pipeline itself for 10M rows. Read in bounded chunks (pd.read_csv(..., chunksize=...)) to cap peak memory instead of loading the whole file at once. Prefer the PyArrow-backed string dtype from the start rather than converting after the fact. Collapse multiple chained .str.replace() calls into a single combined regex or str.translate pass: each .str.replace() call allocates a brand-new full-length Series, so five chained calls pay roughly five separate full-column allocations instead of one.

Worked example

import pandas as pd
import numpy as np

data = pd.DataFrame({"raw_text": [
    "Hello World", "  Pandas STR Methods  ", "NumPy-Char Functions!",
    "Tokenize, This Sentence.", "UPPER lower MiXeD",
]})

def tokenize_py(s):
    return s.strip().lower().replace(",", "").replace(".", "").replace("!", "").split()

result_apply = data["raw_text"].apply(tokenize_py)

result_str = (
    data["raw_text"].str.strip().str.lower()
    .str.replace(",", "", regex=False).str.replace(".", "", regex=False)
    .str.replace("!", "", regex=False).str.split()
)

np_arr = data["raw_text"].to_numpy(dtype=str)
np_clean = np.char.replace(np.char.replace(np.char.replace(
    np.char.lower(np.char.strip(np_arr)), ",", ""), ".", ""), "!", "")
result_np = [s.split() for s in np_clean]  # numpy.char has no vectorized split

assert list(result_apply) == list(result_str) == result_np
print("identical tokenization:", list(result_str)[0])

# The fixed-width memory trap, concretely:
print(pd.Series(["a", "bb", "ccc"]).to_numpy(dtype=str).dtype)          # <U3
print(pd.Series(["a", "bb", "c" * 50]).to_numpy(dtype=str).dtype)       # <U50

Output:

identical tokenization: ['hello', 'world']
<U3
<U50

All three approaches agree on the pinned sample (an equivalence check, not a timing benchmark). The dtype output is the concrete evidence for the fixed-width claim: adding one 50-character string to an otherwise-tiny column forces the whole array's per-element width to 50, regardless of how short the other rows are.

Trade-offs and pitfalls

The most common misconception is treating Series.str as fully vectorized the way numpy arithmetic is; for the default object dtype it only removes call overhead, not per-element cost, and a candidate who states this without the object-dtype caveat is glossing over exactly the distinction the question is testing. The numpy.char fixed-width padding trap is easy to miss because it is invisible on clean, uniform-length synthetic data and only shows up with real-world text containing outliers, exactly the situation a 10M-row production dataset is likely to have. Never cite a fixed wall-clock number ("this ran in 40ms") as a claimed fact: that number is specific to one machine's hardware and load, and does not reproduce; report methodology (which tool, what you would compare) and, if you have actually measured it yourself, a same-machine RATIO between approaches rather than an absolute duration. Chaining several separate .str calls is a subtler trap: each one is a full pass allocating a new Series, so five chained calls cost roughly five allocations where a single combined regex or translate table would cost one; this matters more, not less, as row count grows into the tens of millions.

Direct answer

Slide a fixed-size window of length k across the array, maintaining a running SUM (add the element entering the window, subtract the one leaving), track the best sum seen, and divide by k exactly once at the end. Treat k > n as an explicit invalid-input error rather than guessing a fallback, since no window of that length exists. The time complexity is O(n) and the space complexity is O(1) extra.

Structured elaboration, narrated step by step

1. State the assumption up front. k must satisfy 1 <= k <= n; if k > n, there is no valid window, so raise explicitly rather than returning something like the whole-array average (which would silently answer a DIFFERENT question than the one asked).
2. Seed the window. Compute the sum of the first k elements directly; this is the sum for the window starting at index 0.
3. Slide. For each subsequent starting position, update the running sum in O(1): add the element newly entering the window on the right, subtract the element leaving on the left (window_sum += nums[i] - nums[i - k]). This avoids recomputing a fresh sum of k elements for every window, which is what makes the whole scan O(n) instead of O(n*k).
4. Track the best. Compare each window's sum (not yet divided) against the running best sum.
5. Divide once, at the end. Return best_sum / k after the loop finishes, rather than dividing inside the loop on every step; the comparison of sums doesn't need the division at all, since dividing by the same constant k never changes which sum is largest.
6. All-negative arrays. The algorithm needs no special case here: the "best" window sum is still correctly the LEAST negative one, exactly analogous to the Kadane's-initialization trap, since nothing in this loop clamps the result toward 0.

Worked example

def max_average_subarray(nums, k):
    n = len(nums)
    if k <= 0:
        raise ValueError("max_average_subarray: k must be positive")
    if k > n:
        raise ValueError(f"max_average_subarray: k={k} exceeds array length n={n}")
    window_sum = sum(nums[:k])
    best_sum = window_sum
    for i in range(k, n):
        window_sum += nums[i] - nums[i - k]
        if window_sum > best_sum:
            best_sum = window_sum
    return best_sum / k

def max_average_subarray_brute_force(nums, k):
    n = len(nums)
    best = sum(nums[:k]) / k
    for i in range(1, n - k + 1):
        avg = sum(nums[i:i + k]) / k
        if avg > best:
            best = avg
    return best


cases = [
    ([1.0, 12.0, -5.0, -6.0, 50.0, 3.0], 4),
    ([-1.0, -2.0, -3.0, -4.0], 2),
    ([5.0], 1),
]
for nums, k in cases:
    result = max_average_subarray(nums, k)
    brute = max_average_subarray_brute_force(nums, k)
    print(f"nums={nums}, k={k} -> max_average={result}")
    assert abs(result - brute) < 1e-9

try:
    max_average_subarray([1.0, 2.0, 3.0], 5)
except ValueError as e:
    print(f"k > n raised ValueError as expected: {e}")
print("brute-force cross-check passed for all cases")

Output (executed, python3 s70_max_avg_subarray.py, cross-checked against a brute-force O(n*k) implementation for every case):

nums=[1.0, 12.0, -5.0, -6.0, 50.0, 3.0], k=4 -> max_average=12.75
nums=[-1.0, -2.0, -3.0, -4.0], k=2 -> max_average=-1.5
nums=[5.0], k=1 -> max_average=5.0
k > n raised ValueError as expected: max_average_subarray: k=5 exceeds array length n=3
brute-force cross-check passed for all cases

The all-negative case correctly reports -1.5 (the window [-1.0, -2.0], the least-bad pair), not 0 or an unclamped positive value, and the k > n case raises with a message naming both the offending k and the actual array length rather than failing somewhere less informative.

Trade-offs & pitfalls

• All-negative arrays. As with Kadane's, don't clamp the result toward 0; the least-negative window average is the CORRECT answer, and a version seeded with best_sum = 0 would silently and wrongly prefer an empty or zero-sum comparison over the true (negative) best.
• Dividing inside the loop on every step, instead of once at the end, is unnecessary floating-point work and a common code-review nit, though not a correctness bug at this scale; it also makes the "compare sums directly" optimization harder to see.
• At scale, the same technique underlies real trailing-moving-average code, for example computing a moving average of per-second request counts for rate-limiting or monitoring: the array becomes a live counter rather than a stored list, but the sliding-sum idea is identical. A Go port of that framing would typically keep the running sum as an integer type (e.g. int64, since request counts are naturally integers, and to avoid float accumulation error over a long-running process) and convert to float64 only at the final division, exactly mirroring the "divide once, at the end" principle above; it would also express the k > n check as an explicit returned error value rather than a raised exception, matching Go's idiomatic error-handling convention instead of Python's.
• A vectorized (numpy) equivalent trades the explicit Python loop for a cumulative-sum array and slicing, which is the same O(n) asymptotic work but with a much smaller constant factor in practice, useful once the array is large enough that Python's own per-iteration interpreter overhead dominates:

import numpy as np

def max_average_subarray_numpy(nums, k):
    arr = np.asarray(nums, dtype=float)
    n = arr.shape[0]
    if k <= 0 or k > n:
        raise ValueError(f"max_average_subarray_numpy: invalid k={k} for n={n}")
    csum = np.cumsum(arr)
    window_sums = np.empty(n - k + 1)
    window_sums[0] = csum[k - 1]
    window_sums[1:] = csum[k:] - csum[:-k]
    return float(window_sums.max() / k)


cases = [
    ([1.0, 12.0, -5.0, -6.0, 50.0, 3.0], 4),
    ([-1.0, -2.0, -3.0, -4.0], 2),
    ([5.0], 1),
]
for nums, k in cases:
    loop_result = max_average_subarray(nums, k)
    numpy_result = max_average_subarray_numpy(nums, k)
    print(f"nums={nums}, k={k} -> loop={loop_result}, numpy={numpy_result}, match={abs(loop_result - numpy_result) < 1e-9}")
    assert abs(loop_result - numpy_result) < 1e-9
print("numpy variant agrees with the loop-based version to within 1e-9 for all three cases")

Output (executed, continuing in the same session as the loop-based version above):

nums=[1.0, 12.0, -5.0, -6.0, 50.0, 3.0], k=4 -> loop=12.75, numpy=12.75, match=True
nums=[-1.0, -2.0, -3.0, -4.0], k=2 -> loop=-1.5, numpy=-1.5, match=True
nums=[5.0], k=1 -> loop=5.0, numpy=5.0, match=True
numpy variant agrees with the loop-based version to within 1e-9 for all three cases

The numpy variant agrees with the loop-based version to within 1e-9 for all three cases, confirmed by the explicit comparison above rather than asserted.

Direct answer

Precompute a running-total array prefix where prefix[i] is the sum of the first i counts, built once in O(n). Any inclusive range sum [left, right] is then prefix[right + 1] - prefix[left], O(1). When a new minute of events arrives, append one new prefix entry (last + new_count) in O(1) rather than recomputing anything. A "last W minutes" query is just a range-sum query where the range is derived from the current length, so it reuses the same O(1) machinery.

Approach

1. Build: prefix = [0]; for each count in order, append prefix[-1] + count. prefix has n+1 entries so that prefix[0] = 0 represents "the sum of zero elements," letting the range-sum formula work uniformly even for a range starting at index 0.
2. Range query [left, right] inclusive: prefix[right + 1] - prefix[left]. This is O(1) regardless of range width, because the two boundary lookups already encode the running total up to each endpoint.
3. Streaming update: appending a new minute's count is prefix.append(prefix[-1] + new_count), O(1) amortized (Python list append), since it only ever adds one new entry using the existing last total; nothing earlier in prefix needs to change. This is what makes the update efficiently incremental: each new event only costs one addition, never a recomputation of the whole array.
4. Windowed query ("last W minutes"): since the array is indexed one entry per minute in arrival order, the last W minutes are just the range [n - W, n - 1] (clamped to 0 if W exceeds the history length), so this reuses the same O(1) range-sum formula directly.

Complexity

Build: O(n) time, O(n) space for the prefix array. Range query: O(1). Streaming append: O(1) amortized. Windowed query: O(1), same as any other range query, because the window boundary is derivable directly from the current array length.

Edge cases

• Windowed query wider than the history so far (e.g. asking for the last 60 minutes when only 5 minutes of data exist): clamp the left boundary to 0 rather than going negative, returning the sum of everything available.
• Zero-length range (left == right + 1, i.e. querying an empty window): returns 0 correctly, since prefix[right+1] - prefix[left] collapses to prefix[left] - prefix[left].

class MinuteEventCounter:
    def __init__(self, counts):
        self.prefix = [0]
        for c in counts:
            self.prefix.append(self.prefix[-1] + c)

    def range_sum(self, left, right):
        return self.prefix[right + 1] - self.prefix[left]

    def append(self, count):
        self.prefix.append(self.prefix[-1] + count)

    def last_window_sum(self, window_minutes):
        n = len(self.prefix) - 1
        left = max(0, n - window_minutes)
        return self.range_sum(left, n - 1)


counts = [10, 0, 5, 20, 3]
counter = MinuteEventCounter(counts)

print(counter.range_sum(0, 4))
print(counter.range_sum(2, 3))

counter.append(7)
print(counter.range_sum(0, 5))

print(counter.last_window_sum(3))
print(counter.last_window_sum(60))

Output:

38
25
45
30
45

Five minutes of counts [10, 0, 5, 20, 3] sum to 38 overall, and minutes 2-3 (5 + 20) sum to 25, both matching the range-sum formula directly. After a sixth minute (7 events) streams in, the full six-minute sum is 45. The last-3-minutes window covers minutes 3, 4, 5 (20 + 3 + 7 = 30); asking for a 60-minute window when only 6 minutes of history exist correctly clamps to the whole history's sum, 45.

Trade-offs and pitfalls

• This O(1)-per-minute update relies on the array being indexed one entry per minute, in order, with no gaps (exactly the shape given in the question). If events instead arrived with irregular or sparse timestamps (not one guaranteed entry per minute) and a windowed query meant "events from timestamp T-60min to now" rather than "the last 60 array slots," you would need to look up the index corresponding to a given timestamp first, which is a binary search over a parallel timestamps array (O(log n)), not O(1); the O(1) windowed-query property here is a direct consequence of the question's stated per-minute indexing, not something that survives arbitrary timestamp irregularity for free.
• Prefix sums do not support efficient updates to a value that has already been counted (e.g. correcting minute 2's count after the fact): that would require rebuilding every later prefix entry (O(n)) with this simple array, whereas a Fenwick tree (binary indexed tree) supports both point updates and prefix queries in O(log n) each, at the cost of noticeably more implementation complexity than this straight prefix array. For a purely append-only stream (as asked here), the simple array is the right level of machinery; reach for a Fenwick tree only once in-place corrections to historical counts become a real requirement.
• Memory grows without bound on an infinite append-only stream: since every new minute keeps a running prefix entry forever, a long-lived service would eventually want to either cap the retained history (e.g. only keep the last 24 hours of prefix entries, discarding older ones once no query can reference them) or periodically "re-base" by dropping fully-expired history and adjusting subsequent range-sum math accordingly.

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.