Arrays, Strings, and Hashing Questions

Direct answer

Make two passes over the array without ever dividing. In the first pass, fill the output with the running PREFIX product (the product of everything to the left of each index). In the second pass, walk from the right and multiply each entry by a running SUFFIX product (the product of everything to the right of each index). After both passes, output[i] holds the product of every element except nums[i].

Structured elaboration

Approach

def product_except_self(nums):
    n = len(nums)
    output = [1] * n

    prefix = 1
    for i in range(n):
        output[i] = prefix
        prefix *= nums[i]

    suffix = 1
    for i in range(n - 1, -1, -1):
        output[i] *= suffix
        suffix *= nums[i]

    return output


def naive_division(nums):
    """The disallowed shortcut, shown only to make its zero-element failure
    concrete rather than asserted: multiply everything once, then divide by
    each element in turn."""
    total = 1
    for x in nums:
        total *= x
    out = []
    for x in nums:
        if x == 0:
            out.append(None)  # division by the zero element is undefined
        else:
            out.append(total // x)
    return out

This is O(n) time (two linear passes) and O(1) extra space, not counting the output array itself, exactly as the question specifies, since only two running scalar accumulators (prefix and suffix) are kept alongside the output.

Why prefix and suffix products work, and why no division is needed

Every position i's answer is exactly (product of nums[0..i-1]) * (product of nums[i+1..n-1]), the product of everything strictly to the left, times the product of everything strictly to the right. The first pass computes and stores the left-hand factor for every index in one sweep (writing it into output[i] before nums[i] itself is folded into the running prefix). The second pass computes the right-hand factor the same way while sweeping backward, multiplying it directly into the value already stored. Because the two factors are built and combined without ever needing nums[i] itself in the final expression, this naturally avoids the "divide the total product by nums[i]" approach, which is both explicitly disallowed here and would break outright on any zero in the input (division by zero, or worse, silently wrong results if a naive implementation tries to special-case just one zero).

Leave-one-out features (the question's explicit ask)

The prefix/suffix accumulation pattern used here is the general technique behind computing a "leave-one-out" aggregate for every position without recomputing the whole aggregate from scratch each time. The most common leave-one-out feature in practice is a SUM (for example, "total spend across a group, excluding this member"), computed the same way with running prefix and suffix sums instead of products; the product version shown here applies the identical idea whenever the aggregate you need excluded is a product rather than a sum, for example computing a joint likelihood or a normalization factor across a set of independent factors while excluding one factor at a time.

Worked example

Executed with python3 s84.py (both functions defined above):

product_except_self([1, 2, 3, 4]) = [24, 12, 8, 6]
manual check: [24, 12, 8, 6]

Manually: excluding index 0 leaves 2*3*4=24; excluding index 1 leaves 1*3*4=12; excluding index 2 leaves 1*2*4=8; excluding index 3 leaves 1*2*3=6. All four match the function's output exactly.

product_except_self([1, 2, 0, 4]) = [0, 0, 8, 0]
naive division-based version on the same input = [0, 0, None, 0]  <- breaks on the zero element

With a zero present, every output except the one at the zero's own index is 0 (since every other output's product still includes the zero), while the output AT the zero's index is the product of everything else (1*2*4=8). A division-based approach (compute the total product, then divide by nums[i]) fails outright here: dividing by the zero element itself is undefined, shown above returning None rather than the correct value 8.

Trade-offs and pitfalls

• The division-based shortcut (multiply everything, then divide by nums[i] for each output) is both explicitly disallowed by the question and fundamentally broken the moment any element is zero; the executed comparison above makes this concrete rather than asserted.
• The two-pass prefix/suffix technique generalizes directly to any associative combining operation (sum, product, min, max, and so on) wherever a "leave-one-out" aggregate is needed without an inverse operation (subtraction for sum, division for product) available or safe to use.
• If the array can be very large and the values themselves can be large integers, the running prefix and suffix products can grow to very large magnitudes; in a fixed-width integer language (unlike Python's arbitrary-precision integers), this needs an explicit overflow check or a different numeric representation, which is worth naming even though Python itself does not hit this limit.

Direct answer

Sort the intervals by their start value, then sweep through them once, keeping a running "last merged interval": if the next interval's start is at or before that interval's end (an overlap, or an exact touch), extend the running interval's end to cover it; otherwise, the next interval begins a new, separate merged interval. This is O(n log n) time, dominated entirely by the initial sort, and O(n) space for the output.

Structured elaboration

Why sort by start first. Without imposing an order, a single forward pass cannot be trusted to have already seen every interval that might overlap the one currently being examined; an interval appearing later in the input array could easily start earlier than one already processed. Sorting by start guarantees that once the sweep has moved past a given point, every remaining interval starts at or after it, which is exactly what makes a single linear sweep afterward sufficient.

The merge step itself. Initialize the output with the first (now sorted) interval. For each subsequent interval [s, e], compare s against the END of the last interval currently in the output. If s <= last.end, the two intervals overlap or exactly touch, so extend the last interval's end to max(last.end, e), using max rather than just assigning e directly, because a later interval can be fully NESTED inside the one already being extended (a smaller end than the current running interval), and assigning e unconditionally would incorrectly shrink coverage that the merged interval already legitimately spans. If s > last.end, there is a genuine gap, and [s, e] starts a new entry in the output.

Complexity. The sort is O(n log n) and dominates the total cost; the sweep afterward visits each interval exactly once, O(n). The output requires O(n) space in the worst case (no intervals overlap at all, so every input interval becomes its own output entry).

Touching versus overlapping, a design decision worth naming. Whether two intervals that exactly touch (one's end equals the next one's start, such as [1,4] and [4,5]) should merge is a real semantic choice, not an automatic consequence of the algorithm. Using <= in the overlap check treats a touch as mergeable (matching how meeting-room-style problems usually intend adjacency: back-to-back meetings occupy no coverage gap), while a strict < would keep them as separate, back-to-back intervals; a senior answer should state explicitly which convention is being used rather than leave it implicit.

Worked example

def merge_intervals(intervals):
    if not intervals:
        return []
    ordered = sorted(intervals, key=lambda pair: pair[0])
    merged = [list(ordered[0])]
    for start, end in ordered[1:]:
        last = merged[-1]
        if start <= last[1]:
            last[1] = max(last[1], end)
        else:
            merged.append([start, end])
    return merged

print(merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]]))

# Independent cross-check: a genuinely different method (an event-counting sweep
# line) rather than a second copy of the same merge logic.
def sweep_line_reference(intervals):
    if not intervals:
        return []
    events = []
    for s, e in intervals:
        events.append((s, 0, 1))   # start: delta +1, processed before ends at same coord
        events.append((e, 1, -1))  # end:   delta -1
    events.sort()
    result = []
    active = 0
    run_start = None
    for pos, _, delta in events:
        if active == 0 and delta == 1:
            run_start = pos
        active += delta
        if active == 0:
            result.append([run_start, pos])
    return result

import random
random.seed(3)
hand_picked = [
    [[1, 4], [4, 5]],             # touching intervals
    [[5, 8], [1, 3]],             # unsorted input
    [[2, 5], [1, 10]],            # fully nested interval
    [[1, 2]],                     # single interval
    [],                           # empty input
    [[5, 6], [1, 2]],             # unsorted, non-overlapping
    [[1, 3], [2, 6], [8, 10], [15, 18]],
]
mismatches = 0
for tc in hand_picked:
    if merge_intervals(tc) != sweep_line_reference(tc):
        mismatches += 1
for _ in range(3000):
    n = random.randint(1, 6)
    intervals = [[a, a + random.randint(0, 5)] for a in (random.randint(0, 15) for _ in range(n))]
    if merge_intervals(intervals) != sweep_line_reference(intervals):
        mismatches += 1
print(f"7 hand-picked cases + 3000-trial random sweep (seed 3): mismatches = {mismatches}")

Output:

[[1, 6], [8, 10], [15, 18]]
7 hand-picked cases + 3000-trial random sweep (seed 3): mismatches = 0

matching the question's own example exactly: [1,3] and [2,6] overlap (2 <= 3) and merge into [1,6]; [8,10] and [15,18] each start after the previous merged interval's end, so they remain separate. This was additionally cross-checked against the independently-implemented sweep-line reference above (treating each interval as a +1/-1 event at its start/end and rebuilding runs where the event count returns to zero), which is a genuinely different method rather than a second copy of the same merge logic, on 7 hand-picked cases (touching intervals, unsorted input, a fully nested interval, a single interval, empty input, and unsorted non-overlapping intervals) plus a 3,000-trial random sweep (seed 3); the printed line confirms zero mismatches across all of it, giving real cross-validation rather than testing the code against itself.

Trade-offs and pitfalls

The most consequential bug is assigning last[1] = end directly instead of last[1] = max(last[1], end) when merging: this passes every test case where intervals only partially overlap or extend each other, and only fails on a fully nested interval, which is easy to omit from a quick manual test set and then breaks silently in production by shrinking coverage that should have been preserved. A second common bug is skipping the initial sort, either because the candidate assumes input is already given in start order (sample inputs in problem statements are often, misleadingly, already sorted) or forgets that an unsorted input makes a single forward sweep unreliable; always sort explicitly rather than relying on an assumption about input order. Finally, treat the touching-versus-overlapping boundary as a decision to state out loud (<= merges touching intervals, < does not) rather than an arbitrary implementation detail, since which one is correct depends on what the intervals represent.

Direct answer

Scan the string once, counting how long each run of an identical character is, and emit that count followed immediately by the character ('aaabcc' becomes '3a1b2c'). Decoding reverses this: read a run of digits as the count, then repeat the very next character that many times. Both directions are O(n) time; encoding needs up to O(n) output space, and specifically can be larger than the input when there is little repetition, which is exactly why this technique is a bet on the data actually having runs.

Structured elaboration

Encoding. Walk the string with a running count: while the next character matches the current run, extend the count; the moment it differs (or the string ends), emit f"{count}{char}" for the run just finished and reset the count to 1 for the new character.

Decoding. Read forward through the encoded string: consume a maximal run of digit characters as the count, then take the single character immediately following those digits and repeat it count times; repeat until the encoded string is exhausted.

Where this fits in an ETL (extract, transform, load) context. Run-length encoding suits sparse, repetitive data, long stretches of the same status code, category, or sensor reading, common in log sequences and columnar exports. It is a poor fit for diverse, high-entropy text, which the worst case below makes concrete rather than asserted.

Worked example

def rle_encode(s: str) -> str:
    if not s:
        return ""
    result = []
    count = 1
    for i in range(1, len(s) + 1):
        if i < len(s) and s[i] == s[i - 1]:
            count += 1
        else:
            result.append(f"{count}{s[i - 1]}")
            count = 1
    return ''.join(result)

def rle_decode(encoded: str) -> str:
    result = []
    i, n = 0, len(encoded)
    while i < n:
        j = i
        while j < n and encoded[j].isdigit():
            j += 1
        count = int(encoded[i:j])
        char = encoded[j]
        result.append(char * count)
        i = j + 1
    return ''.join(result)

print(f"rle_encode('aaabcc') = {rle_encode('aaabcc')!r}")
print(f"rle_decode('3a1b2c') = {rle_decode('3a1b2c')!r}")
print()

for t in ["", "a", "aaaaaaaaaa", "abcdef", "aabbccddeeff", "zzzzzzzzzzzzzzzz"]:
    enc = rle_encode(t)
    dec = rle_decode(enc)
    print(f"{t!r} -> {enc!r} -> {dec!r}   roundtrip_ok={dec == t}")
print()

worst = "abcdefgh"
enc = rle_encode(worst)
print(f"worst case, no repeats: {worst!r} (len {len(worst)}) -> {enc!r} (len {len(enc)})")

Output:

rle_encode('aaabcc') = '3a1b2c'
rle_decode('3a1b2c') = 'aaabcc'

               '' ->                        '' -> ''   roundtrip_ok=True
              'a' ->                      '1a' -> 'a'   roundtrip_ok=True
     'aaaaaaaaaa' ->                     '10a' -> 'aaaaaaaaaa'   roundtrip_ok=True
         'abcdef' ->            '1a1b1c1d1e1f' -> 'abcdef'   roundtrip_ok=True
   'aabbccddeeff' ->            '2a2b2c2d2e2f' -> 'aabbccddeeff'   roundtrip_ok=True
'zzzzzzzzzzzzzzzz' ->                     '16z' -> 'zzzzzzzzzzzzzzzz'   roundtrip_ok=True

worst case, no repeats: 'abcdefgh' (len 8) -> '1a1b1c1d1e1f1g1h' (len 16)

rle_encode('aaabcc') produces '3a1b2c' exactly as given in the question, and rle_decode recovers the original from it. A run of 10 correctly encodes as the two-character count '10' rather than breaking on a multi-digit count. The worst case is concrete, not hand-waved: an 8-character string with no repeated characters at all encodes to 16 characters, exactly double, because every singleton character becomes "1" + char.

Trade-offs and pitfalls

The worst-case doubling above means this should never be applied blindly. Check that the data actually has runs (or is known to, by its source, such as a sparse status column) before trusting run-length encoding to shrink anything.

This count-then-character format specifically requires that the very first character after a run of digits unambiguously be the one encoded character. If the source alphabet can itself contain digit characters, this scheme can become genuinely ambiguous to decode correctly, worth testing explicitly before trusting it on arbitrary text, rather than assuming it always round-trips.

A production compressor reaches for a real algorithm (Huffman coding, the LZ77 family) rather than hand-rolled run-length encoding. Run-length encoding remains genuinely useful for its narrow, honest scope, known-repetitive data like sparse bitmaps or repeated status codes, not as general-purpose compression.

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.

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.