Arrays, Strings, and Hashing Questions

Direct answer

Sort the array, then fix each element in turn as the "anchor" and use a two-pointer scan over the remaining sorted suffix to find pairs that complete the triplet to zero, skipping over duplicate values at every level to avoid duplicate triplets. This runs in O(n^2) time (O(n log n) sort plus an O(n) two-pointer scan for each of n anchors) and O(1) extra space beyond the output and the sort itself. The same anchor-then-two-pointer idea generalizes to k-sum by recursing: fix one more element per level until only two remain, then solve that base case with two pointers.

Algorithm: 3Sum

1. Sort nums.
2. For each index i (the anchor), skip it if it's a duplicate of the previous anchor (nums[i] == nums[i-1]), which prevents emitting the same triplet-starting-value twice.
3. If nums[i] > 0, stop entirely: since the array is sorted, every remaining element is also non-negative, so no triplet starting here or later can sum to zero (unless all are zero, already handled by the anchor being the smallest of the three).
4. Two-pointer scan left = i+1, right = n-1 over the sorted suffix: if the three-element sum is 0, record it and advance both pointers past any duplicate values; if the sum is negative, advance left (need a larger value); if positive, retreat right (need a smaller value).

def three_sum(nums):
    nums = sorted(nums)
    n = len(nums)
    result = []
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        if nums[i] > 0:
            break
        left, right = i + 1, n - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                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 total < 0:
                left += 1
            else:
                right -= 1
    return result

Generalizing to k-sum

The pattern is: fix one element, reduce the target by its value, and recurse on k-1 with the remaining sorted suffix, until k == 2, at which point solve with the same two-pointer scan used above (which is really just 3Sum with the anchor already fixed by the outer recursion). Each recursive level still needs the duplicate-skip at its own position to avoid duplicate combinations, and a similar early-exit prune (if the smallest possible sum of the remaining k elements already exceeds the target, or the largest possible sum is already below it, stop).

def k_sum(nums, target, k):
    nums = sorted(nums)

    def helper(start, k, target):
        n = len(nums)
        if k == 2:
            res = []
            left, right = start, n - 1
            while left < right:
                total = nums[left] + nums[right]
                if total == target:
                    res.append([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 total < target:
                    left += 1
                else:
                    right -= 1
            return res

        res = []
        for i in range(start, n - k + 1):
            if i > start and nums[i] == nums[i - 1]:
                continue
            for sub in helper(i + 1, k - 1, target - nums[i]):
                res.append([nums[i]] + sub)
        return res

    return helper(0, k, target)

This runs in O(n^(k-1)) time: each of the k-2 outer recursive levels contributes a factor of O(n), and the base case two-pointer scan is O(n), for a total of O(n^(k-1)). 3Sum is exactly this generalization with k=3.

Worked example

import itertools

def brute_force_k_sum(nums, target, k):
    nums_sorted = sorted(nums)
    seen = set()
    result = []
    for combo_idx in itertools.combinations(range(len(nums_sorted)), k):
        combo_vals = tuple(nums_sorted[i] for i in combo_idx)
        if sum(combo_vals) == target and combo_vals not in seen:
            seen.add(combo_vals)
            result.append(list(combo_vals))
    return sorted(result)

print(three_sum([-1, 0, 1, 2, -1, -4]))
k_sum_result = k_sum([1, 0, -1, 0, -2, 2], target=0, k=4)
print(k_sum_result)

brute = brute_force_k_sum([1, 0, -1, 0, -2, 2], target=0, k=4)
print("brute-force cross-check:", brute)
print("agree:", sorted(k_sum_result) == brute)

Output (verified by execution, and k_sum's results were independently cross-checked against a brute-force itertools.combinations scan over every k-subset of indices, so agreement is real validation, not the same logic checked twice):

[[-1, -1, 2], [-1, 0, 1]]
[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
brute-force cross-check: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
agree: True

Tracing why [-1, -1, 2] and [-1, 0, 1] are the only two triplets on the sorted input [-4, -1, -1, 0, 1, 2]: anchor -4 (index 0) needs a pair summing to 4 from [-1,-1,0,1,2], and the two-pointer scan finds none (max reachable pair sum here is -1+2=1, which the pointers converge past without hitting 4). Anchor -1 (index 1) needs a pair summing to 1 from [-1,0,1,2]: the scan finds -1 and 2 first (giving [-1,-1,2]), then continues and finds 0 and 1 (giving [-1,0,1]). The next anchor is also -1 (index 2), but it's skipped as a duplicate of index 1's value, which is exactly what prevents [-1,-1,2] (or a duplicate [-1,0,1]) from being emitted twice.

Trade-offs and pitfalls

• The two duplicate-skip lines are the single most error-prone part of this problem. Skipping the anchor's duplicates prevents duplicate triplet-starts; skipping left/right duplicates after recording a match prevents duplicate triplet-ends. Missing either one produces a correct set of values but with duplicate entries in the output.
• The nums[i] > 0: break early exit is an optimization, not a correctness requirement for 3Sum specifically (target 0): once sorted, a non-negative anchor means the two-pointer scan can never reach a negative-enough sum to cancel it out to zero. For a general k-sum with a nonzero target, this prune needs to be a real bounds check (is the target reachable at all given the remaining sorted suffix's min/max possible sums), not just a sign check.
• k-sum's O(n^(k-1)) complexity grows fast: 4Sum is already O(n^3), and this approach stops being practical well before k gets large; for genuinely large k, a hash-map-based approach (precompute all pair sums for k/2 elements when k is even) trades space for a lower time exponent, at the cost of needing to dedupe combinations across the two halves.
• Common wrong turn: using a hash set of frozenset or sorted tuples to dedupe triplets after generating all of them (including duplicates) via brute force. This works but is O(n^3) or worse and defeats the purpose of the sorted two-pointer approach, which prevents duplicates from being generated in the first place rather than filtering them out afterward.

Direct answer

Expand a window from the right, adding each new element to a running sum. The moment the running sum reaches or exceeds the target, record the window's length as a candidate answer and shrink from the left for as long as the sum still qualifies, since every valid window found this way is a candidate for the minimum. Track the smallest length seen across the whole single pass.

Structured elaboration

Approach

def min_subarray_len(s, nums):
    n = len(nums)
    left = 0
    window_sum = 0
    best = n + 1
    for right in range(n):
        window_sum += nums[right]
        while window_sum >= s:
            best = min(best, right - left + 1)
            window_sum -= nums[left]
            left += 1
    return 0 if best == n + 1 else best

Why this requires positive numbers (the question's explicit ask)

The sliding-window technique relies on the running sum changing MONOTONICALLY as each pointer moves: adding an element (moving right) can only ever increase the sum, and removing an element (moving left) can only ever decrease it, if and only if every element is positive. That monotonicity is exactly what justifies greedily shrinking the window without ever needing to re-check a wider window later: once the sum drops below the target after removing the leftmost element, removing MORE elements from the left is guaranteed to keep it below target too, since removing a positive number is always a strict decrease. If the array could contain zero or negative values, adding an element to the right would no longer guarantee the sum increases, so a window that currently fails the threshold might still succeed if extended further, and the greedy shrink-from-the-left step is no longer safe. The standard fallback for arrays with negative numbers is prefix sums combined with a monotonic deque, or, for exact-sum variants, prefix sums indexed in a hash map.

Variant: count subarrays with product strictly less than k

A related ask uses the identical two-pointer skeleton, but tracks a running PRODUCT instead of a sum, and counts how many valid windows END at each right pointer rather than tracking a minimum length:

def num_subarrays_product_less_than_k(nums, k):
    if k <= 1:
        return 0
    left = 0
    product = 1
    count = 0
    for right, x in enumerate(nums):
        product *= x
        while product >= k:
            product //= nums[left]
            left += 1
        count += right - left + 1
    return count


def brute_force_count(nums, k):
    """O(n^2) reference: enumerate every subarray's product directly, with
    no window-shrinking logic to trust. Used only to cross-check the
    two-pointer version above, not as the real answer."""
    n = len(nums)
    count = 0
    for i in range(n):
        product = 1
        for j in range(i, n):
            product *= nums[j]
            if product < k:
                count += 1
    return count

The key insight that makes the counting step correct: for a fixed right pointer, every subarray from index left..right, left+1..right, ..., all the way to right..right, is also valid, since removing elements from the front of a window whose product is already below the threshold (with all-positive elements) can only make the product smaller or equal. So the count of newly valid subarrays ending exactly at right is right - left + 1, added once per right-pointer step. This again relies on positive integers for the same monotonicity reason as above.

Worked example

Executed with python3 s81.py (both the two-pointer function and the brute-force reference defined above):

min_subarray_len(s=7, nums=[2, 3, 1, 2, 4, 3]) = 2
min_subarray_len(s=100, nums=[1, 2, 3]) = 0

The window [4, 3] sums to 7 in exactly 2 elements, the shortest possible; with a target of 100 and a maximum possible total sum of 6, no window can ever reach it, so the function correctly returns 0.

num_subarrays_product_less_than_k(nums=[10, 5, 2, 6], k=100) = 8
brute_force_count(nums=[10, 5, 2, 6], k=100) = 8

The brute-force reference (shown above) agrees exactly: 8 qualifying subarrays out of 10 possible non-empty subarrays for a 4-element array.

Trade-offs and pitfalls

• The two-pointer approach is O(n) time and O(1) extra space; that is the entire value proposition over a brute-force O(n^2) (or worse) scan, and interviewers expect BOTH the working code AND the positivity argument for why the greedy shrink is valid, not just code that happens to pass test cases.
• A common bug in the counting variant is omitting the if k <= 1: return 0 guard: with k <= 1, no product of positive integers can ever be strictly less than k, and the main loop's while product >= k shrink condition would otherwise push left past right and read a stale or out-of-range element.
• It is easy to conflate "smallest window that reaches a target" (this problem, returning a length) with "count every window satisfying a condition" (the other variant, returning a count); keep straight which of the two output shapes a given question is actually asking for, since the bookkeeping each one needs is different even though the window-management code looks nearly identical.

Direct answer

Normalize both strings to a canonical Unicode form (NFC: compose combining marks into precomposed characters wherever a composed form exists), then casefold them (a Unicode-aware, more aggressive relative of .lower()), and finally compare character frequency counts using a hash map. Two strings are anagrams exactly when their normalized, casefolded character-count maps are equal. This is O(n) time and O(k) extra space, where k is the number of distinct characters actually present, not the size of the whole alphabet.

Structured elaboration

Why raw codepoint comparison fails on Unicode text. The same visible character can be represented by different codepoint sequences: an accented letter like an e with an acute accent can be one precomposed codepoint, or two codepoints (the base letter plus a separate combining acute-accent mark). Two strings that look identical to a human, and that a user would absolutely expect to be treated as anagrams of each other, can fail a naive character-by-character or Counter-based comparison if one uses the composed form and the other the decomposed form, because they are literally different sequences of codepoints.

Normalization (NFC) before comparison. Running both strings through Unicode Normalization Form C (NFC) converts any decomposed base-plus-combining-mark sequence into its precomposed equivalent wherever one exists, so that two visually-identical strings become byte-for-byte identical at the codepoint level before any counting happens. Normalization must happen before counting, not after, since counting decomposed and precomposed forms separately would treat them as different characters.

Casefolding, not just lowercasing. Python's .casefold() is used instead of .lower() because casefolding is defined specifically for caseless string matching and handles cases .lower() doesn't, most famously the German sharp s (ß), which casefolds to the two-character sequence ss (matching how ß and ss are treated as equivalent in caseless comparisons) while .lower() leaves it unchanged. This means casefolding can change a string's length, which matters for the next step.

Order of operations for the length check. The length check (len(s) != len(t) as a fast rejection before doing full character counting) must be performed on the normalized-and-casefolded strings, never on the raw input, precisely because casefolding can change length. Checking the raw lengths first, as a shortcut before normalization, is a subtle but real bug: it would incorrectly reject valid Unicode-aware anagram pairs whose raw lengths differ only because casefolding expands one of them.

Sorting-based versus counting-based comparison, and the large-alphabet trade-off. A sorting-based approach (sort both normalized/casefolded strings, compare for equality) costs O(n log n) time but only O(1) extra space if sorting can be done on a mutable copy in place (or O(n) if the language's sort isn't in-place), and it never needs a hash map at all, which matters when the character alphabet is enormous, since a sort never allocates space proportional to the alphabet size, only to the string length. A counting-based approach (build a frequency map, compare maps) is O(n) time but pays O(k) space for the map, where k is the number of distinct characters seen; for a small, fixed alphabet like lowercase ASCII, that map is trivially small and counting wins outright on speed, but for full Unicode text (over a million possible codepoints, even though any single string only uses a tiny fraction of them), a hash-map-based counter is still the right call because k is bounded by the input length itself, not by the alphabet size, since a Python dict/Counter only allocates entries for characters that actually appear.

Worked example

Full runnable code with pinned test cases, including the composed-versus-decomposed accented-character case and the German sharp-s casefold case (a genuine subtlety, not a contrived one):

import unicodedata
from collections import Counter


def normalize_for_compare(s):
    """NFC-normalize then casefold. Length check must happen AFTER this,
    never on the raw string (see the STRASSE case below)."""
    return unicodedata.normalize("NFC", s).casefold()


def is_anagram(s, t):
    """O(n) time, O(k) extra space where k is the distinct-character count,
    counting-based rather than sorting-based."""
    s_norm = normalize_for_compare(s)
    t_norm = normalize_for_compare(t)
    if len(s_norm) != len(t_norm):
        return False
    return Counter(s_norm) == Counter(t_norm)


if __name__ == "__main__":
    # Built from explicit codepoint escapes so the composed/decomposed
    # distinction is unambiguous regardless of source-file encoding.
    precomposed = "caf" + "\u00e9"          # c a f e-acute (1 codepoint, U+00E9)
    decomposed = "caf" + "e" + "\u0301"     # c a f e + combining acute (U+0301)

    print("raw codepoint lengths (decomposed vs precomposed):", len(decomposed), len(precomposed))
    print("raw equal (no normalization)?", decomposed == precomposed)
    print("NFC-normalized equal?", unicodedata.normalize("NFC", decomposed) == unicodedata.normalize("NFC", precomposed))

    reordered_precomposed = "\u00e9" + "fac"          # e-acute f a c (reordered anagram)
    strasse_lower = "stra" + "\u00df" + "e"           # stra-sharp_s-e

    tests = [
        ("listen", "silent", True),
        ("Listen", "Silent", True),
        (precomposed, decomposed + "x", False),
        (precomposed, reordered_precomposed, True),
        (decomposed, reordered_precomposed, True),
        ("STRASSE", strasse_lower, True),   # casefold('ss') == casefold('\u00df')
        ("ab", "abc", False),
    ]
    for a, b, expected in tests:
        result = is_anagram(a, b)
        print(f"is_anagram({a!r}, {b!r}) = {result} (expected {expected})")

    print("raw len(strasse_lower) =", len(strasse_lower), " raw len('STRASSE') =", len("STRASSE"))
    print("casefold(strasse_lower) =", strasse_lower.casefold())
    print("casefold('STRASSE') =", "STRASSE".casefold())

Output (actual run):

raw codepoint lengths (decomposed vs precomposed): 5 4
raw equal (no normalization)? False
NFC-normalized equal? True
is_anagram('listen', 'silent') = True (expected True)
is_anagram('Listen', 'Silent') = True (expected True)
is_anagram('café', 'caféx') = False (expected False)
is_anagram('café', 'éfac') = True (expected True)
is_anagram('café', 'éfac') = True (expected True)
is_anagram('STRASSE', 'straße') = True (expected True)
is_anagram('ab', 'abc') = False (expected False)
raw len(strasse_lower) = 6  raw len('STRASSE') = 7
casefold(strasse_lower) = strasse
casefold('STRASSE') = strasse

The STRASSE / straße case is the one to walk through out loud in an interview: the raw strings have different lengths (7 versus 6 codepoints), so a fast-reject on raw length would wrongly report "not an anagram." But ß casefolds to the two characters ss, so both strings casefold to the same 7-character string strasse, and they are correctly identified as an anagram pair. This is exactly why the length check must run on the normalized-and-casefolded strings.

Trade-offs and pitfalls

• Comparing raw strings, or even lowercasing with .lower() instead of .casefold(), silently fails on real internationalized input like the ß/ss case above; .lower() alone leaves ß unchanged and would report STRASSE and straße as not anagrams, which is wrong under Unicode caseless matching rules.
• Checking length before normalizing (a tempting micro-optimization to avoid normalizing strings that "obviously" can't match) is a genuine bug source, not a harmless shortcut, precisely because casefolding and normalization can both change apparent length.
• Sorting-based comparison is the right call when the alphabet is small and fixed (interview-classic lowercase-English anagram checks) since it avoids hash-map overhead entirely; counting-based comparison is the right call once the input might be full Unicode text, since a hash map's cost scales with how many distinct characters actually appear in this particular input, not with the size of the Unicode codepoint space.
• Grapheme-cluster-level correctness (treating an emoji-with-modifier sequence, or a base character plus multiple combining marks, as a single user-perceived "character") is a further layer beyond codepoint-level NFC normalization; this answer normalizes and compares at the codepoint level, which is sufficient for the vast majority of real anagram-style interview questions, but a fully grapheme-aware comparison would need a dedicated segmentation library, which is depth beyond what this question is testing.
• NFC (compose) rather than NFD (decompose) is used here because it produces the more compact, more widely-used-as-a-default form; either would work correctly as long as it's applied consistently to both strings before comparison, since the point is only that both strings land on the same normalized form, not which specific form is chosen.

Direct answer

Reduce k modulo n first, since rotating by a full n is a no-op and any k can be folded into [0, n). Then reverse the whole array once, and reverse each of the two resulting parts (the first k elements and the remaining n - k), which lands every element in its rotated position using only O(1) extra space and three linear passes.

Structured elaboration

• Why k %= n first. A right rotation by n positions returns the array to its original order, so any k >= n is equivalent to k % n. Skipping this step means an implementation either does needless repeated work for large k, or (worse) indexes out of bounds when it assumes k < n.
• The reversal trick, step by step. A right rotation by k moves the LAST k elements to the front and the FIRST n - k elements to the back, each preserving their own relative order:
  1. Reverse the whole array. Everything is now in fully reversed order.
  2. Reverse the first k elements of THAT reversed array. Those k elements were originally the array's last k elements; reversing them twice (once by the whole-array reversal, once here) restores their original relative order, now correctly sitting at the front.
  3. Reverse the remaining n - k elements similarly, restoring the original relative order of what were the first n - k elements, now correctly sitting at the back.
• Complexity. Three linear passes over the array: O(n) time total, O(1) extra space (just the swap loop), no second array allocated.

Worked example

def rotate_right(arr, k):
    n = len(arr)
    if n == 0:
        return arr
    k %= n

    def reverse(lo, hi):
        while lo < hi:
            arr[lo], arr[hi] = arr[hi], arr[lo]
            lo += 1
            hi -= 1

    reverse(0, n - 1)
    reverse(0, k - 1)
    reverse(k, n - 1)
    return arr

def slice_rotate_right(arr, k):
    n = len(arr)
    if n == 0:
        return list(arr)
    k %= n
    return arr[-k:] + arr[:-k] if k else list(arr)


test_cases = [
    ([1, 2, 3, 4, 5, 6, 7], 3),
    ([1, 2, 3, 4, 5, 6, 7], 10),
    ([1, 2, 3, 4, 5, 6, 7], 7),
    ([1, 2, 3, 4, 5, 6, 7], 0),
    ([42], 5),
]
for arr, k in test_cases:
    result = rotate_right(list(arr), k)
    expected = slice_rotate_right(list(arr), k)
    print(f"arr={arr}, k={k} -> {result}")
    assert result == expected
print("cross-check against slice-based rotation passed for all 5 cases")

Output (executed, python3 s68_rotate_right.py, cross-checked against slice-based rotation for 5 cases):

arr=[1, 2, 3, 4, 5, 6, 7], k=3 -> [5, 6, 7, 1, 2, 3, 4]
arr=[1, 2, 3, 4, 5, 6, 7], k=10 -> [5, 6, 7, 1, 2, 3, 4]
arr=[1, 2, 3, 4, 5, 6, 7], k=7 -> [1, 2, 3, 4, 5, 6, 7]
arr=[1, 2, 3, 4, 5, 6, 7], k=0 -> [1, 2, 3, 4, 5, 6, 7]
arr=[42], k=5 -> [42]
cross-check against slice-based rotation passed for all 5 cases

k=10 on a 7-element array gives the identical result to k=3 (10 % 7 == 3), and k=7 (a full rotation) correctly leaves the array unchanged.

Trade-offs & pitfalls

• Forgetting the k %= n reduction is the most consequential bug: it can index a reversal call with k - 1 larger than n - 1, or simply waste O(k/n) extra full passes for a large k.
• Off-by-one in the two split-reversal calls (reverse(0, k-1) and reverse(k, n-1)) is the most common implementation bug; verifying against a small hand-traced example (as above) catches this quickly.
• Rotating LEFT by k is the mirror image but with the reversal ORDER changed: reverse the first k, reverse the remaining n - k, THEN reverse the whole array (right rotation reverses the whole array FIRST). Mixing up the order between left and right rotation is an easy transcription error.
• Alternatives: an extra output array is O(n) space but trivial to write correctly; a cycle-following ("juggling") algorithm is also O(1) space and O(n) time but is meaningfully harder to get right, since it needs to track gcd(n, k) independent cycles rather than three flat passes. The reversal trick is generally preferred in an interview specifically because it's simple to reason about and hard to get subtly wrong.

Direct answer

Read the input in fixed-size chunks (not the whole stream at once), strip any whitespace or newlines from each chunk, and only decode the largest prefix of accumulated characters that is a multiple of 4 (one base64 "quantum"). Carry the leftover 0-3 characters forward to be combined with the next chunk. This bounds memory use to the chunk size regardless of how large the input stream is, and correctly reproduces the standard library's own base64.b64decode output on the full data.

Structured elaboration

Why a naive whole-input decode does not work here: base64.b64decode (and equivalents in other languages) requires the entire encoded string in memory first. The question explicitly asks for constant extra memory proportional to block size, so the decode has to happen incrementally as bytes arrive.

The three things that make streaming base64 harder than streaming raw bytes:

1. Base64 decodes in fixed-size groups of 4 encoded characters to 3 raw bytes. You cannot decode a partial group, so any chunk boundary that splits a group of 4 has to be handled by holding the incomplete tail back and prepending it to the next chunk.
2. Whitespace and newlines are not part of the base64 alphabet but commonly appear in real-world encoded data (classic MIME-style line wrapping at 76 characters, for example). These must be filtered out per chunk, not just once at the start, since they can appear anywhere.
3. Padding (=) only ever appears at the very end of the full encoded string, so it naturally falls out of the last "leftover" group processed, no special-casing is needed beyond decoding whatever is left when the stream ends.

Algorithm:

• Maintain a small leftover byte buffer (0 to 3 bytes) carried between reads.
• On each read of block_size bytes: strip whitespace, prepend leftover, decode the largest prefix that is a multiple of 4, write the decoded bytes to the output stream, and save the remainder as the new leftover.
• After the input is exhausted, decode any final leftover (a well-formed base64 stream always leaves a multiple-of-4 remainder including padding at the true end).

Worked example

import base64

def streaming_b64_decode(in_stream, out_stream, block_size=4096):
    assert block_size % 4 == 0, "block_size must be a multiple of 4"
    leftover = b""
    while True:
        raw = in_stream.read(block_size)
        if not raw:
            break
        if isinstance(raw, str):
            raw = raw.encode("ascii")
        cleaned = bytes(c for c in raw if c not in b" \t\r\n")
        chunk = leftover + cleaned
        usable_len = (len(chunk) // 4) * 4
        usable, leftover = chunk[:usable_len], chunk[usable_len:]
        if usable:
            out_stream.write(base64.b64decode(usable))
    if leftover:
        out_stream.write(base64.b64decode(leftover))

# Pinned verification: random payloads of varying sizes, MIME-style 76-char line
# wrapping injected to exercise whitespace handling, decoded with an artificially
# small block_size=8 to force many chunk boundaries, compared byte-for-byte
# against base64.b64decode() run on the whole un-streamed input.
import io, random
random.seed(1234)

def make_test_payload(n_bytes):
    return bytes(random.randrange(0, 256) for _ in range(n_bytes))

for n in [0, 1, 2, 3, 4, 100, 1000, 12345]:
    payload = make_test_payload(n)
    encoded = base64.b64encode(payload)
    wrapped = b"\n".join(encoded[i:i+76] for i in range(0, len(encoded), 76))
    in_buf, out_buf = io.BytesIO(wrapped), io.BytesIO()
    streaming_b64_decode(in_buf, out_buf, block_size=8)
    decoded = out_buf.getvalue()
    reference = base64.b64decode(encoded)
    print(f"n_bytes={n:6d} encoded_len={len(wrapped):6d} matches_reference={decoded == reference == payload}")

Output:

n_bytes=     0 encoded_len=     0 matches_reference=True
n_bytes=     1 encoded_len=     4 matches_reference=True
n_bytes=     2 encoded_len=     4 matches_reference=True
n_bytes=     3 encoded_len=     4 matches_reference=True
n_bytes=     4 encoded_len=     8 matches_reference=True
n_bytes=   100 encoded_len=   137 matches_reference=True
n_bytes=  1000 encoded_len=  1353 matches_reference=True
n_bytes= 12345 encoded_len= 16676 matches_reference=True

Every case, including the empty input and inputs whose length is not a multiple of 3 (which is exactly what produces = padding), matched the standard library's non-streaming decoder exactly.

Trade-offs & pitfalls

• block_size must be a multiple of 4. If it is not, the "largest usable multiple of 4" logic still works correctly (it is computed dynamically from the accumulated chunk, not assumed from block_size directly), but choosing a multiple of 4 up front avoids an unnecessary one-off adjustment and keeps the memory bound exactly predictable.
• The leftover buffer is the entire reason this works, and it is easy to get wrong by resetting it every read instead of carrying it forward. That specific bug silently corrupts output only when a chunk boundary happens to fall mid-group, which makes it easy to miss with small test inputs that fit in a single chunk.
• Memory is bounded by chunk size, not stream size, which is the whole point for very large files, but this means you cannot validate the base64 alphabet or overall structure ahead of time the way an in-memory decode implicitly does; invalid characters are only caught when base64.b64decode raises on the chunk containing them, so error messages will reference a chunk-relative position, not a position in the original stream, unless you track a running byte offset yourself.
• This does not parallelize trivially. Because state (the leftover bytes) carries across chunks, you cannot decode arbitrary byte ranges independently the way you could with a format that has self-describing block boundaries; splitting work across threads requires aligning split points to 4-character boundaries first.