8 · Product of Array Except Self

In an Xcode test target:

import Testing

struct ProductOfArrayExceptSelfTests {

    @Test(arguments: [
        ([2, 3, 4, 5], [60, 40, 30, 24]),
        ([3, 0, 2], [0, 6, 0]),
        ([0, 5, 0], [0, 0, 0]),
    ])
    func multipliesEverythingButTheEntryAtEachPosition(numbers: [Int], expected: [Int]) {
        #expect(productExceptSelf(numbers) == expected)
    }

    // MARK: - Privates
    private func productExceptSelf(_ numbers: [Int]) -> [Int] {
        []
    }
}

In a playground:

func productExceptSelf(_ numbers: [Int]) -> [Int] {
    [] // your solution
}

let cases: [([Int], [Int])] = [
    ([2, 3, 4, 5], [60, 40, 30, 24]),
    ([3, 0, 2], [0, 6, 0]),
    ([0, 5, 0], [0, 0, 0]),
]
for (numbers, expected) in cases {
    let got = productExceptSelf(numbers)
    print(got == expected ? "PASS" : "FAIL", numbers, "→", got, "expected", expected)
}

Prefix and suffix products. The cue is "all the other numbers except the one at that position": everything except position i is everything to its left times everything to its right. Both of those are running totals, of products instead of sums, one built from the front and one from the back. "Without division" is what rules out the shortcut of dividing the total by each number.

Make two passes. In the first pass, go left to right and write into each position the product of everything before it; the first position gets 1, because nothing comes before it. In the second pass, go right to left carrying a running product of everything after the current position, starting at 1, and multiply it into each position before folding that position's own number into the running product. After both passes, each position holds (everything to its left) × (everything to its right), which is exactly the product of all the others.

Time O(n): two passes. Space O(1) beyond the output: the left products live in the output array itself and the right products in a single variable.

func productExceptSelf(_ numbers: [Int]) -> [Int] {
    var result = Array(repeating: 1, count: numbers.count)

    var leftProduct = 1
    for index in numbers.indices {
        result[index] = leftProduct          // everything before index
        leftProduct *= numbers[index]
    }

    var rightProduct = 1
    for index in numbers.indices.reversed() {
        result[index] *= rightProduct        // times everything after index
        rightProduct *= numbers[index]
    }
    return result
}

In both loops the order of the two lines is the whole trick: use the running product first, then fold in the current number, so a position never multiplies by itself.

Verified with swift test on Swift 6.4 in Swift 6 mode: the three examples above, five more (two numbers, one number, negatives, a single zero at the front, all ones), and 3,000 random arrays with values from −5 to 5, many with zeros, checked against an O(n²) brute force that multiplies everything except each position.

[2, 3, 4, 5]

The first pass fills the second column top to bottom; the second pass fills the third column bottom to top.

[3, 0, 2] — the left products are [1, 3, 0], the right products [0, 2, 1]; multiplied position by position that is [0, 6, 0]. The zero needs no special handling: it lands in every product except its own.

The division shortcut crashes in Swift, it doesn't just fail. Multiplying everything and then dividing by each number is the idea most people have first, and the statement forbids it for a reason: with a zero in the array, total / 0 is a runtime trap in Swift, not a wrong value or an infinity, and handling it means counting zeros as special cases. Explain the shortcut, say why it breaks, and write the two passes.

The quieter one: the constraints promise every product fits in 32 bits. Without that promise, Swift's * traps on overflow where C would silently wrap. If the interviewer drops the guarantee, say what you'd want instead: multipliedReportingOverflow(by:) to detect it, or &* only if wrapped values are acceptable.

• "Can you do it without the extra output array?" → The output is required, so O(1) extra is already the floor. The point of the follow-up is to put the left products in the output and keep the right ones in one variable.
• "Now return the sum of all others." → Total once, then total − numbers[i]; subtraction has no division-by-zero problem, so no passes are needed.
• "The array changes, with many queries afterwards." → Keep a segment tree of products: O(log n) per update and per query.