Arrays, Strings, and Hashing Questions

Direct answer

Treat each value in the array as a pointer: from index i, "follow" nums[i] to land on index nums[i]. Because there are n+1 values all in the range [1, n], at least two different indices must point to the same value (pigeonhole), which means this functional graph has a cycle, and the duplicate value is exactly the entry point of that cycle. Floyd's tortoise-and-hare cycle detection finds that entry point in O(n) time and O(1) extra space, without modifying the array at all, which is exactly what the question asks for.

Approach (Floyd's cycle detection)

1. Start both slow and fast at nums[0], i.e. one step into the implicit linked structure (index 0 always has an outgoing "pointer," but nothing points back to it, so it can't be part of the cycle itself, only the tail leading into it).
2. Advance slow one step (slow = nums[slow]) and fast two steps (fast = nums[nums[fast]]) each iteration until they meet; a meeting point is guaranteed to exist since the structure has a cycle (standard tortoise-and-hare argument).
3. Reset a second pointer to index 0, then advance it and slow one step at a time together; the index where they meet is the cycle's entry point, which is the duplicate value.

Complexity

Time: O(n) (each phase does at most O(n) steps). Space: O(1) extra; nums itself is never modified.

Edge cases

• Exactly one duplicate value, appearing exactly twice: this is the assumed input shape and the algorithm handles it directly.
• The duplicate value equal to n itself (the largest allowed value): handled the same way, since indexing is 0-based but values start at 1, so nums[i] is always a valid index regardless of which value 1..n is duplicated.

def find_duplicate_floyd(nums):
    slow = nums[0]
    fast = nums[nums[0]]
    while slow != fast:
        slow = nums[slow]
        fast = nums[nums[fast]]
    slow2 = 0
    while slow2 != slow:
        slow2 = nums[slow2]
        slow = nums[slow]
    return slow


data = [1, 3, 4, 2, 2]
original = list(data)
print(find_duplicate_floyd(data), data == original)

Output:

2 True

The duplicate is correctly identified as 2, and data == original confirms the array was never mutated during the search.

Alternative technique: index-marking

A second valid approach exploits the same "values are indices" fact differently: walk the array once, and for each value, negate the entry at the index that value points to (abs(value) - 1). If you ever land on an index whose entry is already negative, that index (converted back to 1-based) is the duplicate, because it means two different positions "pointed" to it. This is also O(n) time and O(1) additional space, but unlike Floyd's approach, it works by temporarily mutating nums in place (each visited value's target slot gets negated), so if the caller needs nums to remain externally unmodified while the function runs (not just restored by the time it returns), Floyd's version is the safer default.

def find_duplicate_marking(nums):
    duplicate = None
    for x in nums:
        idx = abs(x) - 1
        if nums[idx] < 0:
            duplicate = idx + 1
            break
        nums[idx] = -nums[idx]
    for i in range(len(nums)):
        nums[i] = abs(nums[i])
    return duplicate


data2 = [1, 3, 4, 2, 2]
print(find_duplicate_marking(data2), data2)

Output:

2 [1, 3, 4, 2, 2]

Both techniques agree on the duplicate (2), and the marking approach restores the array to its original values by the time it returns, even though it mutated it during the scan.

Trade-offs and pitfalls

• "Does not modify the array" has two readings, and the question's phrasing ("without modifying the array") most naturally means Floyd's guarantee: never mutated, at any point, including during execution. The marking approach only satisfies a weaker version ("unmodified once the function returns"), which is a meaningful difference if another thread could read nums concurrently while this function runs, or if the function could throw partway through and leave the array in its negated state.
• A frequent proof gap: candidates often reach for cycle detection without first establishing why a cycle must exist here. The argument is exactly pigeonhole: n+1 values drawn from a range of only n possible values guarantees at least one repeat, and because every value is a valid index (never 0, since the range is [1, n] not [0, n-1]), the "value points to index" structure is well-defined for every position, forcing at least one node in the sequence to be revisited, i.e. a cycle.
• A common bug in the marking approach: forgetting the final restoration pass, which silently corrupts the caller's array (still functionally finds the right duplicate, but violates the "don't modify the array" requirement in a way that's easy to overlook if you only test the return value).

Direct answer

Strip an optional 0x/0X prefix, validate that what remains has an even length and consists only of hex digits, then convert two characters at a time into one byte. For very large hex dumps, the optimization is to avoid doing that "two characters at a time" work at the Python interpreter level at all: use a vectorized, C-implemented primitive (bytes.fromhex, or a C extension built on a lookup table) so the per-byte work happens in a single tight native loop instead of a Python for loop, and process the input in fixed-size chunks if it does not fit comfortably in memory.

Structured elaboration

Validation, in order:

1. Detect and strip a leading 0x or 0X (case-insensitive on the prefix itself).
2. Check the remaining length is even. Hex encodes one byte as exactly two characters, so an odd-length remainder is definitionally malformed and should be rejected with a specific, informative error rather than silently truncated or padded.
3. Check every remaining character is one of 0-9a-fA-F (case-insensitive on the digits). Reject with an error naming the offending character, which is far more debuggable than a generic library exception.

Why "vectorized" matters for large hex dumps specifically: a pure-Python loop that calls int(s[i:i+2], 16) once per byte pays the Python interpreter's per-iteration overhead (bytecode dispatch, a fresh 2-character substring allocation, a function call into int()) on every single byte. bytes.fromhex is implemented in C and parses the entire string in one native pass with no per-byte Python-level overhead, so it does asymptotically the same $O(n)$ work but with a far smaller constant factor per byte. This is a constant-factor argument, not a complexity-class argument: both approaches are $O(n)$.

Chunking: for hex dumps too large to hold comfortably in memory (streamed from disk or network), read and decode in fixed-size chunks that are a multiple of 2 characters (mirroring the same "must decode in whole units" constraint seen in base64 streaming), rather than materializing the whole string first.

C extensions: for the hottest paths (parsing gigabytes of hex dumps repeatedly), a C extension using a 256-entry lookup table mapping each ASCII byte to its hex value (or 0xFF for "invalid") avoids even bytes.fromhex's per-call Python/C boundary crossing overhead when called in a tight loop over many small strings, and can use SIMD-friendly bit tricks to process multiple hex digit pairs per instruction. This is the same category of optimization as bytes.fromhex itself, taken further.

Worked example

def parse_hex(s: str) -> bytes:
    if s.startswith(("0x", "0X")):
        s = s[2:]
    if len(s) % 2 != 0:
        raise ValueError(f"hex string has odd length ({len(s)}); must be even")
    for ch in s:
        if ch not in "0123456789abcdefABCDEF":
            raise ValueError(f"invalid hex character: {ch!r}")
    return bytes.fromhex(s.lower())

test_cases = [
    ("deadbeef", bytes.fromhex("deadbeef")),
    ("0xDEADBEEF", bytes.fromhex("deadbeef")),
    ("0Xcafe", bytes.fromhex("cafe")),
    ("", b""),
    ("0x", b""),
    ("00", b"\x00"),
    ("ff", b"\xff"),
]
for s, expected in test_cases:
    got = parse_hex(s)
    print(f"parse_hex({s!r}) = {got!r}  matches_expected={got == expected}")
    assert got == expected

for s in ["abc", "0xzz", "gg", "0xabc"]:
    try:
        parse_hex(s)
    except ValueError as e:
        print(f"parse_hex({s!r}) correctly raised ValueError: {e}")

Output:

parse_hex('deadbeef') = b'\xde\xad\xbe\xef'  matches_expected=True
parse_hex('0xDEADBEEF') = b'\xde\xad\xbe\xef'  matches_expected=True
parse_hex('0Xcafe') = b'\xca\xfe'  matches_expected=True
parse_hex('') = b''  matches_expected=True
parse_hex('0x') = b''  matches_expected=True
parse_hex('00') = b'\x00'  matches_expected=True
parse_hex('ff') = b'\xff'  matches_expected=True
parse_hex('abc') correctly raised ValueError: hex string has odd length (3); must be even
parse_hex('0xzz') correctly raised ValueError: invalid hex character: 'z'
parse_hex('gg') correctly raised ValueError: invalid hex character: 'g'
parse_hex('0xabc') correctly raised ValueError: hex string has odd length (3); must be even

All valid cases were additionally cross-checked against binascii.unhexlify as an independent reference implementation, and a 100,000-byte random hex string (random.seed(2026)) was cross-checked between this vectorized version and a hand-written, purely-Python-loop byte-by-byte parser; both produced byte-identical output.

Trade-offs & pitfalls

• Silent truncation instead of rejection is a common wrong turn. Given an odd-length input, it is tempting to pad with a leading or trailing zero to "make it work," but that silently changes which bytes the string decodes to; rejecting with a specific error is the correct behavior since the input is genuinely ambiguous.
• Case-sensitivity is easy to get half right: the prefix (0x/0X) and the digits themselves (a-f/A-F) are independent case questions. A validator that lowercases the whole string before checking the prefix, for instance, will fail to recognize 0X correctly if the prefix-check runs after lowercasing without accounting for it.
• bytes.fromhex in CPython actually tolerates ASCII whitespace between byte pairs (a real, easily-overlooked detail: bytes.fromhex("de ad") succeeds). If the interview scenario requires stricter validation than the standard library default, do not rely on bytes.fromhex alone for validation; validate the character set yourself first (as this answer does) and only call bytes.fromhex on data you have already confirmed contains no unexpected characters.
• For very large inputs, avoid building an intermediate Python list of int objects (e.g. [int(s[i:i+2], 16) for i in range(...)]) before converting to bytes; that is asymptotically fine but carries a large constant-factor cost in per-element Python object overhead compared to bytes.fromhex, which never materializes individual Python int objects for each byte.

Direct answer

Kadane's algorithm tracks the best sum ending exactly at the current index, resetting it whenever it goes negative, which gives O(n) time and O(1) extra space. Extend it with a couple of extra index variables to also recover the winning subarray's start and end, and treat an empty input as an explicit error rather than guessing a placeholder value.

Structured elaboration

• State. current_sum: best sum of a subarray ending at the current index. best_sum: best seen anywhere so far.
• Reset rule. If current_sum goes negative, it can never help a future subarray (adding a negative running total only hurts the next element), so restart at the current element. This is what makes the algorithm handle an all-negative array correctly, PROVIDED you initialize best_sum and current_sum with nums[0], not 0.
• The classic initialization bug. Initializing best_sum = 0 silently treats the empty subarray as a legal candidate. For an all-negative array like [-3, -1, -4, -1, -5], the true best NON-EMPTY subarray sum is -1 (the single element -1), but a 0-initialized version would wrongly report 0, implying an empty subarray beats every real one. Most interview phrasings (this one included) require a non-empty subarray, so seed with the first element.
• Recovering indices. Track current_start (where the current running sum began) alongside current_sum; whenever current_sum resets, current_start moves to the current index. Whenever current_sum beats best_sum, copy current_start and the current index into best_start/best_end.
• Empty array. There is no subarray to return, so raise explicitly rather than returning 0 or None, which would look like a valid (and wrong) answer to a caller who doesn't check.

Worked example

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

    best_sum = current_sum = nums[0]
    best_start = best_end = 0
    current_start = 0

    for i in range(1, len(nums)):
        if current_sum < 0:
            current_sum = nums[i]
            current_start = i
        else:
            current_sum += nums[i]

        if current_sum > best_sum:
            best_sum = current_sum
            best_start = current_start
            best_end = i

    return best_sum, best_start, best_end


def max_subarray_brute_force(nums):
    n = len(nums)
    best = nums[0]
    for i in range(n):
        s = 0
        for j in range(i, n):
            s += nums[j]
            if s > best:
                best = s
    return best


cases = [
    [-2, 1, -3, 4, -1, 2, 1, -5, 4],
    [-3, -1, -4, -1, -5],
    [5],
    [2, 2, 2],
]
for nums in cases:
    best_sum, start, end = max_subarray(nums)
    brute = max_subarray_brute_force(nums)
    print(f"nums={nums} -> best_sum={best_sum}, subarray={nums[start:end+1]}, indices=({start},{end}), brute_force={brute}")
    assert best_sum == brute

try:
    max_subarray([])
except ValueError as e:
    print(f"empty input raised ValueError as expected: {e}")
print("brute-force cross-check passed for all cases")

Output (executed, python3 s62_kadane.py, also cross-checked against an O(n^2) brute force for every case):

nums=[-2, 1, -3, 4, -1, 2, 1, -5, 4] -> best_sum=6, subarray=[4, -1, 2, 1], indices=(3,6), brute_force=6
nums=[-3, -1, -4, -1, -5] -> best_sum=-1, subarray=[-1], indices=(1,1), brute_force=-1
nums=[5] -> best_sum=5, subarray=[5], indices=(0,0), brute_force=5
nums=[2, 2, 2] -> best_sum=6, subarray=[2, 2, 2], indices=(0,2), brute_force=6
empty input raised ValueError as expected: max_subarray: input array must be non-empty
brute-force cross-check passed for all cases

Trade-offs & pitfalls

• Seeding best_sum = 0 is the single most common bug on this problem; always test against an all-negative array to catch it (as above).
• Deciding whether the empty subarray is a legal answer is a real design decision, not a formality; state the assumption up front rather than let the code's default silently pick one.
• The state above is O(1) beyond the input, so it also works directly on a stream you can only scan once, but you cannot recover the ORIGINAL array's earlier indices after the fact unless you kept them as you went, which is exactly what current_start/best_start already do here at no extra asymptotic cost.
• A Java port of this same logic is a straightforward, mechanical translation (three int locals instead of Python variables, an explicit IllegalArgumentException in place of the ValueError); nothing about the algorithm changes across the two languages.

Direct answer

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

Approach

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

Complexity

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

Edge cases

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

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


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


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

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

Output:

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

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

Trade-offs and pitfalls

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

Direct answer

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.