Arrays, Strings, and Hashing Questions

Direct answer

Parse the line as a leading timestamp token followed by a run of key=value tokens, where a value is either a bare token or a quoted string that can itself contain spaces or an escaped quote. Scan it manually, character by character, rather than with one big anchored regular expression: a single anchored pattern matches the whole line or fails the whole line, and "handle missing fields safely" specifically means a missing field should leave that one key unset, not blow up the entire parse.

Structured elaboration

Tokenizing approach. Read the leading whitespace-delimited token as the timestamp (an ISO 8601 style stamp, 2025-12-06T12:00:00Z, though the parser does not need to validate that format, only extract it). Then repeatedly: skip whitespace, read a key up to =, and read the value either as a bare token (up to the next space) or, if the next character is a quote, as everything up to the matching unescaped quote, unescaping any \' along the way.

Safe field handling. Every expected key (timestamp, service, pid, level, msg) starts at None in the result dict. A key that never appears in the line simply stays None; a malformed pid (not all digits) is caught with a try/except around the int() conversion and also left as None, instead of raising and losing the whole line. That is the concrete meaning of "handle missing or quoted messages safely" here: partial, defensive results instead of an exception.

Performance at millions of lines per hour. The scan itself is a single O(n) pass per line, O(1) extra space beyond the output dict, no backtracking. The throughput number matters for scale: 1,000,000 / 3600 ≈ 277.8 lines per second, a modest rate for a single-threaded O(n)-per-line parse. The parsing technique's job at that rate is to not add avoidable overhead: avoid rebuilding the same intermediate list-and-rejoin structure that line.split() plus manual reassembly would need, and avoid a regex whose quantifiers could backtrack badly on adversarial input (many repeated escaped quotes inside msg). Everything past that (batching, buffering, multiple worker processes) is an ingestion-pipeline design question, a different skill from the array/string parsing technique this question is actually testing.

Worked example

def parse_log_line(line: str) -> dict:
    result = {"timestamp": None, "service": None, "pid": None, "level": None, "msg": None}
    n = len(line)
    i = 0

    # 1. timestamp is the leading whitespace-delimited token
    while i < n and line[i] == ' ':
        i += 1
    start = i
    while i < n and line[i] != ' ':
        i += 1
    if i > start:
        result["timestamp"] = line[start:i]

    # 2. remaining key=value tokens, respecting quoted values
    while i < n:
        while i < n and line[i] == ' ':
            i += 1
        if i >= n:
            break
        key_start = i
        while i < n and line[i] != '=' and line[i] != ' ':
            i += 1
        if i >= n or line[i] != '=':
            while i < n and line[i] != ' ':
                i += 1
            continue
        key = line[key_start:i]
        i += 1  # skip '='

        if i < n and line[i] in ("'", '"'):
            quote = line[i]
            i += 1
            val_start = i
            while i < n:
                if line[i] == '\\' and i + 1 < n and line[i + 1] == quote:
                    i += 2
                    continue
                if line[i] == quote:
                    break
                i += 1
            raw_val = line[val_start:i]
            value = raw_val.replace('\\' + quote, quote)
            if i < n:
                i += 1  # skip closing quote
        else:
            val_start = i
            while i < n and line[i] != ' ':
                i += 1
            value = line[val_start:i]

        if key in result:
            result[key] = value

    if result["pid"] is not None:
        try:
            result["pid"] = int(result["pid"])
        except ValueError:
            result["pid"] = None
    return result

test_lines = [
    "2025-12-06T12:00:00Z service=auth pid=1234 level=ERROR msg='Failed login for user bob: invalid password'",
    "2025-12-06T12:00:01Z service=auth level=INFO msg='pid missing on this line'",
    "2025-12-06T12:00:02Z service=auth pid=5678 level=WARN msg='He said \\'hi\\' twice'",
    "2025-12-06T12:00:04Z service=auth pid=notanumber level=INFO msg='bad pid value'",
]
for t in test_lines:
    print(repr(t))
    print(parse_log_line(t))

print("1,000,000 lines/hour =", round(1_000_000 / 3600, 1), "lines/second")

Output, run against the sample line plus edge cases:

"2025-12-06T12:00:00Z service=auth pid=1234 level=ERROR msg='Failed login for user bob: invalid password'"
{'timestamp': '2025-12-06T12:00:00Z', 'service': 'auth', 'pid': 1234, 'level': 'ERROR', 'msg': 'Failed login for user bob: invalid password'}

"2025-12-06T12:00:01Z service=auth level=INFO msg='pid missing on this line'"
{'timestamp': '2025-12-06T12:00:01Z', 'service': 'auth', 'pid': None, 'level': 'INFO', 'msg': 'pid missing on this line'}

"2025-12-06T12:00:02Z service=auth pid=5678 level=WARN msg='He said \\'hi\\' twice'"
{'timestamp': '2025-12-06T12:00:02Z', 'service': 'auth', 'pid': 5678, 'level': 'WARN', 'msg': "He said 'hi' twice"}

"2025-12-06T12:00:04Z service=auth pid=notanumber level=INFO msg='bad pid value'"
{'timestamp': '2025-12-06T12:00:04Z', 'service': 'auth', 'pid': None, 'level': 'INFO', 'msg': 'bad pid value'}

1,000,000 lines/hour = 277.8 lines/second

Every field from the question (timestamp, service, pid as int, level, msg) is produced, a missing pid and a missing quoted value both degrade to None instead of raising, and the escaped-quote case (\'hi\') is correctly unescaped to a literal quote inside the message.

Trade-offs and pitfalls

A single anchored regex (^(?P<timestamp>\S+)\s+service=...) is more compact to write, but it is all-or-nothing: reorder the fields, drop one, or add an unexpected key, and the whole line fails to match instead of degrading field by field. If you do reach for a regex per field, keep quantifiers bounded (avoid nested .* inside the quoted-value group) so a message packed with escaped quotes cannot trigger catastrophic backtracking.

Swallowing a bad pid to None is the right behavior for a pipeline that must never crash on one bad line, but silently doing nothing else is its own risk: track a counter of how many lines failed to parse a given field, or a silent upstream format change (a service starts emitting pid as a hex string, say) goes unnoticed indefinitely.

Real log files are commonly UTF-8; if you are reading raw bytes rather than already-decoded text, quote and escape detection has to run on the decoded string, not the raw byte sequence, or a multi-byte character could be split mid-character by a byte-oriented scan.

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

Two clean variants exist. Variant 1, in-place, O(1) extra space: a single write-pointer pass that swaps every element satisfying the predicate to the front; O(n) time, O(1) extra space, but does NOT preserve relative order within either group. Variant 2, order-preserving: build two lists (matched, unmatched) in a single pass and concatenate them; O(n) time, O(n) extra space, and DOES preserve relative order. In general, O(1) extra space and stability cannot both be had in O(n) time; achieving both simultaneously needs O(n log n) time instead, the same trade-off behind why C++'s std::stable_partition switches to a slower algorithm specifically when it cannot get extra memory.

Structured elaboration

Variant 1 mechanics (swap-based partition). Maintain a write pointer starting at 0. Scan read from 0 to n-1; whenever predicate(arr[read]) holds, swap arr[write] and arr[read], then increment write. After the scan, everything before write satisfies the predicate and everything from write onward does not, but a swap can move an unmatched element out of its original relative position among other unmatched elements (or vice versa for matched elements).

Variant 2 mechanics. A single pass builds two separate lists, matched and unmatched, in original encounter order, then concatenates them. Correctness is immediate: each list is built purely by appends in scan order, and appends never reorder elements relative to each other within their own list.

Can O(1) space and stability be achieved together? Yes, but not in O(n) time. A divide-and-conquer approach recursively stable-partitions each half of the array, then merges the two halves' now-partitioned matched and unmatched runs using an in-place rotation (rotation itself can be done with O(1) extra space via the three-reversals trick, in time proportional to the rotated range). This gives the recurrence T(n) = 2T(n/2) + O(n), which solves to O(n log n) time with O(1) extra space (or O(log n) if counting recursion-stack space). This mirrors exactly what C++'s standard library documents for std::stable_partition: O(n) swaps when extra memory is available for a temporary buffer, up to O(n log n) swaps if allocation fails and it must fall back to in-place. It is a genuine impossibility result at O(n) time: you cannot have in-place (O(1) space), stable, AND O(n) time simultaneously for a general predicate-based partition; you must give up exactly one of the three.

Worked example

def partition_inplace_unstable(arr, predicate):
    '''O(1) extra space, O(n) time. Relative order NOT guaranteed.'''
    write = 0
    for read in range(len(arr)):
        if predicate(arr[read]):
            arr[write], arr[read] = arr[read], arr[write]
            write += 1

def partition_stable(arr, predicate):
    '''O(n) extra space, O(n) time. Preserves relative order in each group.'''
    matched = [x for x in arr if predicate(x)]
    unmatched = [x for x in arr if not predicate(x)]
    return matched + unmatched

data = [1, 4, 2, 7, 3, 8, 5, 9, 6]  # pinned
is_even = lambda x: x % 2 == 0

unstable_copy = data.copy()
partition_inplace_unstable(unstable_copy, is_even)
print("input                    =", data)
print("unstable in-place result =", unstable_copy)

stable_result = partition_stable(data, is_even)
print("stable (extra space)     =", stable_result)

evens_in_order = [x for x in data if is_even(x)]
odds_in_order = [x for x in data if not is_even(x)]
print("stability check (evens):", stable_result[:len(evens_in_order)] == evens_in_order)
print("stability check (odds): ", stable_result[len(evens_in_order):] == odds_in_order)

evens_after_unstable = [x for x in unstable_copy if is_even(x)]
odds_after_unstable = [x for x in unstable_copy if not is_even(x)]
print("unstable evens order matches original order?", evens_after_unstable == evens_in_order)
print("unstable odds order matches original order? ", odds_after_unstable == odds_in_order)

Output:

input                    = [1, 4, 2, 7, 3, 8, 5, 9, 6]
unstable in-place result = [4, 2, 8, 6, 3, 1, 5, 9, 7]
stable (extra space)     = [4, 2, 8, 6, 1, 7, 3, 5, 9]
stability check (evens): True
stability check (odds):  True
unstable evens order matches original order? True
unstable odds order matches original order?  False

The stable variant preserves order for BOTH groups, as guaranteed. The unstable variant's evens [4, 2, 8, 6] happen to keep their original relative order for this particular input, but the odds group does not: it ends as [3, 1, 5, 9, 7] instead of the original relative order [1, 7, 3, 5, 9]. That asymmetry is instructive: instability is not a guarantee that EVERY group gets scrambled, it is the absence of a guarantee that ANY group stays in order, and this input concretely demonstrates the odds group breaking.

Trade-offs and pitfalls

• The three-way trade-off (space, stability, time) is the deep point of this question: claiming the swap-based partition is "basically the same as the stable one, just in place" misses that the relative-order guarantee is genuinely lost, not merely an implementation detail.
• A common bug is forgetting to swap (writing arr[write] = arr[read] instead) in the O(1)-space version, which overwrites and destroys data rather than reordering it; this only works if discarding the unmatched values is acceptable, otherwise a real swap is required.
• The O(n)-space stable variant needs no swapping subtlety at all; that simplicity is itself a valid engineering argument, plenty of real systems accept O(n) extra space for a partition specifically to keep the code obviously correct.
• Do not assume "in-place" always means "faster": the swap-based version is not asymptotically faster than the two-list version, both are O(n) time, it only saves memory, and if that memory saving is not needed, the added subtlety may not be worth it.

Direct answer

Add the two digit strings exactly the way long addition is done by hand: walk both strings from the rightmost digit, add the corresponding digits plus any carry from the previous position, keep the ones digit as the result and carry the tens digit forward, and continue until both strings and the carry are exhausted. This never converts the whole number into a native integer type, runs in O(max(len(a), len(b))) time and space, and generalizes directly to any base by changing how individual digits are parsed and re-emitted.

Structured elaboration

Why this can't just use native integer addition. The entire point of the exercise is that the numbers may be arbitrarily large decimal strings, potentially larger than any fixed-width integer type can represent without an arbitrary-precision ("big-int") library; the question explicitly disallows using one, so digits are processed as characters, not as a machine integer.

The right-to-left digit-pair-plus-carry loop. Two index pointers start at the last character of each string and move left. At each step, the digit from a (or 0 if that pointer has run past the start of a) is added to the digit from b (or 0, similarly) plus the carry from the previous step. The result's ones digit (total % 10) is appended to the output, and the new carry is the tens digit (total // 10). The loop continues as long as either pointer still has digits left, or a carry is still pending, which correctly handles the case where the final addition produces an extra leading digit (e.g. 9 + 9 = 18, carrying a new leading 1).

Reversal at the end. Because digits are produced from least-significant to most-significant (processing right to left), the accumulated digit list is in reverse order relative to the final answer and must be reversed once before joining into the output string.

Generalizing to base 16 or other bases. The algorithm's structure doesn't change at all between bases; only two things change: how a single character is parsed into its numeric digit value, and how a numeric digit value is turned back into a character. In decimal, int(digit) and str(digit) handle this. For an arbitrary base b (2 through 36), Python's int(digit, b) parses a single base-b digit character (handling both decimal digits and letters a through z for bases above 10), and indexing into a fixed alphabet string (\"0123456789abcdefghijklmnopqrstuvwxyz\") re-emits a digit value as its base-b character. The carry logic is identical, just with % base and // base replacing % 10 and // 10.

Worked example

Full runnable code with pinned test cases, including the question's own large-number example, verified against Python's own native big-integer addition as ground truth (used here only to cross-check the from-scratch implementation, not as a substitute for it):

def add_strings(a, b):
    """Add two non-negative decimal-string integers without big-int libs.
    O(max(len(a), len(b))) time and space, single right-to-left pass with
    a carry, exactly like manual long addition."""
    i, j = len(a) - 1, len(b) - 1
    carry = 0
    digits = []
    while i >= 0 or j >= 0 or carry:
        da = int(a[i]) if i >= 0 else 0
        db = int(b[j]) if j >= 0 else 0
        total = da + db + carry
        digits.append(str(total % 10))
        carry = total // 10
        i -= 1
        j -= 1
    return ''.join(reversed(digits))


def add_strings_base(a, b, base):
    """Same algorithm generalized to an arbitrary base (2-36), using
    int(digit, base) to parse and a base-N string alphabet to re-emit."""
    digits_alphabet = "0123456789abcdefghijklmnopqrstuvwxyz"
    i, j = len(a) - 1, len(b) - 1
    carry = 0
    out = []
    while i >= 0 or j >= 0 or carry:
        da = int(a[i], base) if i >= 0 else 0
        db = int(b[j], base) if j >= 0 else 0
        total = da + db + carry
        out.append(digits_alphabet[total % base])
        carry = total // base
        i -= 1
        j -= 1
    return ''.join(reversed(out))


if __name__ == "__main__":
    a = "9876543210123456789"
    b = "1234567890987654321"
    result = add_strings(a, b)
    expected_via_python_int = str(int(a) + int(b))
    print(f"add_strings({a!r}, {b!r})")
    print(f"  result   = {result}")
    print(f"  expected = {expected_via_python_int} (cross-checked via Python's native int addition)")
    print(f"  match: {result == expected_via_python_int}")

    more_tests = [
        ("0", "0", "0"),
        ("1", "9", "10"),
        ("99", "1", "100"),
        ("123", "0", "123"),
    ]
    for x, y, exp in more_tests:
        r = add_strings(x, y)
        print(f"add_strings({x!r}, {y!r}) = {r} (expected {exp})")

    hex_result = add_strings_base("ff", "1", 16)
    print(f"add_strings_base('ff', '1', 16) = {hex_result} (expected 100)")

Output (actual run):

add_strings('9876543210123456789', '1234567890987654321')
  result   = 11111111101111111110
  expected = 11111111101111111110 (cross-checked via Python's native int addition)
  match: True
add_strings('0', '0') = 0 (expected 0)
add_strings('1', '9') = 10 (expected 10)
add_strings('99', '1') = 100 (expected 100)
add_strings('123', '0') = 123 (expected 123)
add_strings_base('ff', '1', 16) = 100 (expected 100)

This confirms the question's own stated example: '9876543210123456789' + '1234567890987654321' -> '11111111101111111110' is correct, verified both by the character-by-character implementation and by cross-checking against Python's native arbitrary-precision integer addition on the same inputs. The base-16 example ('ff' + '1' = '100' in hex, i.e. 255 + 1 = 256) confirms the generalization: the carry chain propagates through both hex digits exactly as it would for 99 + 1 = 100 in decimal.

Trade-offs and pitfalls

• Converting both strings to native integers, adding, and converting back (str(int(a) + int(b))) is the obvious shortcut and was used above only as a cross-check, not as the answer: for genuinely arbitrary-precision inputs in a language without native big-int support (or under an explicit "no big-int library" constraint, as this question states), this shortcut isn't available at all, which is the entire point of the exercise.
• A common bug is forgetting the final carry: if the loop condition doesn't check carry as an independent continuation condition (only checking i >= 0 or j >= 0), an addition like 9 + 9 (which produces 18, needing an extra leading digit) silently drops the final carry digit.
• Building the result with repeated string concatenation (result = digit + result instead of appending to a list and reversing once at the end) works but is less efficient in languages or situations where string concatenation is O(current length) per operation, making a naive left-prepend approach O(n^2) overall instead of O(n); appending to a list and reversing once avoids this.
• This implementation assumes both inputs are non-negative digit strings with no sign character or leading-zero ambiguity beyond a literal "0"; supporting signed values would require detecting and handling a leading - or + before the digit-processing loop, which is a real but separate extension.
• The base generalization above supports bases 2 through 36 only, since it relies on Python's int(digit, base) and a 36-character alphabet; supporting arbitrary bases beyond 36 would require a different, explicitly-provided digit alphabet rather than reusing 0-9a-z.

Direct answer

The same running-sum Kadane's approach handles the all-negative edge case correctly as long as best_sum/current_sum are seeded with the first element rather than 0. Extending it to track the maximum PRODUCT subarray needs one extra piece of state: because multiplying by a negative number can flip the current running minimum into the new maximum, you must track both the max-ending-here AND the min-ending-here at every position, not just the max.

Structured elaboration

• Sum version, with indices. current_sum resets to nums[i] whenever it goes negative, current_start moves with it; whenever current_sum beats best_sum, copy current_start/i into best_start/best_end. Seeding with nums[0] (not 0) is what makes an all-negative array report its true best single (least-negative) element, instead of a wrong 0 implying an empty subarray won.
• Why product needs a second running value. For sums, dropping below zero is always bad, so resetting is safe. For products, a large NEGATIVE running product can become the best POSITIVE product the moment it's multiplied by another negative number. So at each index track both:
  • max_end = max(nums[i], max_end_prev * nums[i], min_end_prev * nums[i])
  • min_end = min(nums[i], max_end_prev * nums[i], min_end_prev * nums[i])
    and update the running best from max_end.
• Zero handling. Any product crossing a zero is zero, so a zero naturally resets both max_end and min_end toward nums[i] itself (one of the three candidates above is always nums[i] alone), acting as a partition point in the array.
• Index tracking, the part that's easy to get wrong. The start index of the winning chain at position i is not always "the same start as the previous max": a sign flip can pull in the MIN chain's start instead. Track max_start and min_start as two separate running indices, exactly parallel to max_end/min_end, and copy whichever one wins into the reported answer.

Worked example

def max_subarray_product(nums):
    if not nums:
        raise ValueError("max_subarray_product: input array must be non-empty")

    max_end, max_start = nums[0], 0
    min_end, min_start = nums[0], 0
    best, best_start, best_end = nums[0], 0, 0

    for i in range(1, len(nums)):
        x = nums[i]
        options = [
            (max_end * x, max_start),
            (min_end * x, min_start),
            (x, i),
        ]
        new_max, new_max_start = max(options, key=lambda t: t[0])
        new_min, new_min_start = min(options, key=lambda t: t[0])
        max_end, max_start = new_max, new_max_start
        min_end, min_start = new_min, new_min_start

        if max_end > best:
            best, best_start, best_end = max_end, max_start, i

    return best, best_start, best_end


def max_subarray_product_brute_force(nums):
    n = len(nums)
    best = nums[0]
    for i in range(n):
        p = 1
        for j in range(i, n):
            p *= nums[j]
            if p > best:
                best = p
    return best


product_cases = [
    [2, 3, -2, 4],
    [-2, 0, -1],
    [-2, 3, -4],
    [-1, -2, -3, 0, -1],
]
for nums in product_cases:
    p, a, b = max_subarray_product(nums)
    subarray = nums[a:b + 1]
    computed = 1
    for v in subarray:
        computed *= v
    brute = max_subarray_product_brute_force(nums)
    print(f"nums={nums} -> best_product={p}, subarray={subarray}, product(subarray)={computed}, brute_force={brute}")
    assert computed == p
    assert p == brute
print("brute-force cross-check (value) and subarray self-consistency check passed for all product cases")

Output (executed, python3 s63_kadane_product.py, cross-checked against an O(n^2) brute force for value AND against recomputing each claimed subarray's own product):

nums=[2, 3, -2, 4] -> best_product=6, subarray=[2, 3], product(subarray)=6, brute_force=6
nums=[-2, 0, -1] -> best_product=0, subarray=[-2, 0], product(subarray)=0, brute_force=0
nums=[-2, 3, -4] -> best_product=24, subarray=[-2, 3, -4], product(subarray)=24, brute_force=24
nums=[-1, -2, -3, 0, -1] -> best_product=6, subarray=[-2, -3], product(subarray)=6, brute_force=6
brute-force cross-check (value) and subarray self-consistency check passed for all product cases

The all-negative-adjacent case [-1, -2, -3, 0, -1] shows the flip directly: two negatives (-2, -3) multiply to the positive 6, which beats every other candidate even though the array is mostly negative numbers.

Trade-offs & pitfalls

• A real bug caught during verification, worth naming explicitly. A first draft of this function tracked only a single running start index (updated only when the code decided it was "restarting fresh"). It produced a technically-correct product VALUE (24, for [-2, 3, -4]) paired with a subarray ([3, -4]) that actually multiplies out to -12, not 24: the reported value and the reported subarray disagreed with each other. The fix is exactly the two-start-index tracking above; the way it was caught is by recomputing each claimed subarray's own product and asserting it equals the claimed answer, which is good general practice for any "return a value AND a supporting slice" problem.
• A zero divides the array into independent segments for the product version; the best answer can be a single zero if every other segment is negative-product.
• Products can overflow fixed-width integer types (Java int/long, C) on a long array of large-magnitude values; Python's arbitrary-precision integers hide this, but a real production port needs an overflow strategy (wider type, or switch to summing logs of absolute values and tracking sign separately).
• Taking the absolute value of the sum-version and reusing it is not a valid shortcut: the sum version's reset rule ("restart if negative") is specifically wrong for products, since it would throw away a large negative run that a later negative number could have flipped into the best answer.