Q3 - Crosstalk-Aware Pipeline Gain

Scenario: An Apple signal processing pipeline runs n stages in series, each applying an integer gain (a multiplier), given in gains. Real hardware has crosstalk: when you isolate a stage to measure it, that stage and its k immediate neighbors on each side become unreliable. So to characterize the pipeline gain attributable to everything outside stage i's interference zone, you need the product of all gains except those in the window [i - k, i + k].

Return an array result where result[i] is the product of every gains[j] with j outside [i - k, i + k] (indices clamped to the array bounds). If that window covers the whole pipeline, the product is empty, so result[i] = 1. As before, no division is allowed, a disabled stage has a gain of 0, and it must run in linear time.

Input:  gains = [2, 3, 5, 7], k = 1
Output: [35, 7, 2, 6]
Why: stage 0 excludes window {0,1} -> keep {5,7} = 35.
        stage 1 excludes {0,1,2} -> keep {7} = 7.
        stage 2 excludes {1,2,3} -> keep {2} = 2.
        stage 3 excludes {2,3} -> keep {2,3} = 6.

Input:  gains = [2, 3, 5, 7, 11], k = 2
Output: [77, 11, 1, 2, 6]
Why: stage 2 excludes {0,1,2,3,4}, the entire pipeline, so its
        product is empty and equals 1. Stage 0 keeps {7,11} = 77.

Input:  gains = [2, 0, 5, 7], k = 1
Output: [35, 7, 2, 0]
Why: stage 3 excludes {2,3} -> keep {2,0} = 0. The zero outside the
        window correctly drives that result to 0, with no division anywhere.

Solution 1: Brute Force, Multiply Everything Outside the Window

State the obvious version first. For each stage i, compute its window [lo, hi], then walk the whole array multiplying every gain that falls outside it. It is correct and trivially handles zeros, the empty window, and the boundaries, which makes it a perfect reference to test the fast version against. The cost is O(n^2).

# O(n^2) time | O(1) extra space (excluding the output)
def crosstalk_gain(gains, k):
    n = len(gains)
    result = []
    for i in range(n):
        window_start, window_end = max(0, i - k), min(n - 1, i + k)
        product = 1
        for j in range(n):
            if j < window_start or j > window_end:
                product *= gains[j]
        result.append(product)
    return result

The Key Insight: Prefix and Suffix Products

Everything outside the window [i - k, i + k] splits cleanly into two contiguous runs: a left run gains[0 .. i-k-1] and a right run gains[i+k+1 .. n-1]. So the answer is just:

(product of the run strictly before the window) × (product of the run strictly after the window)

Precompute both directions once. Let prefix[j] be the product of gains[0 .. j-1] and suffix[j] the product of gains[j .. n-1]. Then for each stage the left run is prefix[i - k] and the right run is suffix[i + k + 1], with the indices clamped so an over-the-edge window contributes an empty product of 1. No division, and each stage is now O(1).

gains = [2, 3, 5, 7]   k = 1

prefix[j] = product of gains[0 .. j-1]   ->  [1, 2, 6, 30, 210]
suffix[j] = product of gains[j .. n-1]   ->  [210, 105, 35, 7, 1]

result[i] = prefix[max(0, i-k)] * suffix[min(n, i+k+1)]
  i=0: prefix[0] * suffix[2] = 1  * 35 = 35
  i=1: prefix[0] * suffix[3] = 1  * 7  = 7
  i=2: prefix[1] * suffix[4] = 2  * 1  = 2
  i=3: prefix[2] * suffix[4] = 6  * 1  = 6

Solution 2: Prefix and Suffix Products (Linear Time)

Before the code, here is the whole algorithm walked step by step on a small example, gains = [2, 3, 5, 7, 4] with k = 1: build the prefix products, build the suffix products, then combine them for each stage.

1 / 6

The combine step is where the window edges get handled: clamp both indices so an over-the-edge run is an empty product of 1.

for i in range(n):
    left_product = prefix[max(0, i - k)]        # product of the run strictly before the window
    right_product = suffix[min(n, i + k + 1)]   # product of the run strictly after the window
    result.append(left_product * right_product) # no division, one multiply per stage

# O(n) time | O(n) space
def crosstalk_gain(gains, k):
    n = len(gains)
    prefix = [1] * (n + 1)            # prefix[j] = product of gains[0 .. j-1]
    for j in range(1, n + 1):
        prefix[j] = prefix[j - 1] * gains[j - 1]
    suffix = [1] * (n + 1)            # suffix[j] = product of gains[j .. n-1]
    for j in range(n - 1, -1, -1):
        suffix[j] = suffix[j + 1] * gains[j]
    result = []
    for i in range(n):
        left_product = prefix[max(0, i - k)]          # run strictly before the window
        right_product = suffix[min(n, i + k + 1)]     # run strictly after the window
        result.append(left_product * right_product)
    return result

The Follow-Up: O(1) Extra Space

The Apple-style follow-up: drop the two helper arrays. The output array is free, so fold both runs into it, but now with a k-sized lag. Sweep left to right writing each stage's left-run product, where the running product trails the cursor by k + 1 (you only fold gains[i - k] in after using it). Then sweep right to left, multiplying in the right-run product with the same k + 1 lead. The only tricky part is getting those two offsets right.

gains = [2, 3, 5, 7], k = 1

pass 1 (left to right): result[i] = product of gains to the LEFT of the window;
the running "left" product trails the cursor by k+1 = 2 slots
  i=0 -> result[0] = 1
  i=1 -> result[1] = 1
  i=2 -> result[2] = 2            (gains[0])
  i=3 -> result[3] = 6            (gains[0] * gains[1])

pass 2 (right to left): multiply in the product to the RIGHT of the window;
the running "right" product leads by the same k+1 = 2 slots
  i=3 -> 6 * 1  = 6
  i=2 -> 2 * 1  = 2
  i=1 -> 1 * 7  = 7              (gains[3])
  i=0 -> 1 * 35 = 35            (gains[2] * gains[3])

result = [35, 7, 2, 6]

Solution 3: Constant Extra Space

The whole trick is the lag: on the left pass, write the running product first and only then fold in gains[i - k], so what you write always excludes the window.

left_product = 1
for i in range(n):
    result[i] = left_product          # left-run product so far, trailing the cursor
    if i - k >= 0:
        left_product *= gains[i - k]  # fold gains[i-k] in only AFTER writing it: the k+1 lag
# then a symmetric right-to-left pass multiplies in the right-run product

# O(n) time | O(1) extra space (the output array does not count)
def crosstalk_gain(gains, k):
    n = len(gains)
    result = [1] * n
    left_product = 1                          # running product of gains[0 .. i-k-1]
    for i in range(n):
        result[i] = left_product
        if i - k >= 0:
            left_product *= gains[i - k]
    right_product = 1                         # running product of gains[i+k+1 .. n-1]
    for i in range(n - 1, -1, -1):
        result[i] *= right_product
        if i + k < n:
            right_product *= gains[i + k]
    return result

Complexity Analysis

• Solution 1 (brute force): O(n^2) time, O(1) extra space. Re-scans the whole array for every stage. Fine to state, too slow to ship.
• Solution 2 (prefix/suffix products): O(n) time, O(n) space. Two precomputation passes, then O(1) per stage.
• Solution 3 (constant extra space): O(n) time, O(1) extra space beyond the output. Same two passes, but the running products trail and lead the cursor by k + 1.

Final Notes

1. Reduce the window to two clean runs. "Everything outside [i - k, i + k]" is just the run before the window times the run after it. Naming that split is the move that collapses an O(n^2) scan into prefix and suffix products.
2. The boundaries are the test. Clamp i - k and i + k + 1 to the array ends so an over-the-edge window contributes an empty product of 1. The whole-array-excluded case (Example 2) is the one interviewers love to check.
3. No division means a single zero cannot be undone. Prefix/suffix products sidestep this entirely: a 0 outside the window naturally zeroes the result, and a 0 inside it is correctly ignored, all with no special cases.
4. The k + 1 lag is the real follow-up. Reaching O(1) extra space for a windowed exclusion is meaningfully harder than the single-element version, the running product has to trail (and lead) the cursor by exactly k + 1. Get that offset right and the rest is the same two-pass sweep you already know. 🚀