Array Product Exclusions — Problem Statement & Solution Guide

ArraysMediumPrefix Sum / Array Traversal

TimeO(N)

SpaceO(1)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Arrays and solve the Array Product Exclusions problem optimally.

TopicArrays

PatternPrefix Sum / Array Traversal

TimeO(N)

SpaceO(1)

Problem Description

Given a zero-indexed integer array values consisting of $N$ integers, construct and return a new array result of length $N$ such that each entry result[i] represents the total product of all elements in values except values[i].

Your solution must compute the output without using any division arithmetic operations (/ or %). Furthermore, the solution must run in linear time complexity, $O(N)$, and execute using $O(1)$ auxiliary space. Memory allocated for the returned answer array does not count toward the extra space requirement.

Ensure that your logic properly handles non-positive values, including zeros, while avoiding integer overflow issues by adhering to the given problem constraints.

DSA Pattern Breakdown

"Array Product Exclusions"

medium

WHY DOES IT MATTER?

Mastering prefix and suffix accumulations is essential for transforming O(N^2) range query problems into linear time O(N) executions without requiring complex spatial tree structures.

OPTIMIZATION CHALLENGE

The challenge is replacing two separate full-sized dynamic auxiliary arrays (Prefix and Suffix) with a single pass backward using a scalar accumulator variable to achieve O(1) auxiliary space complexity.

REAL-WORLD CONNECTION

In distributed databases and financial ledgers, computing aggregate state changes excluding a single node or transaction failure uses prefix-suffix rollups to quickly compute alternative cluster configurations.

In interviews, clearly separate the dynamic programming state array allocation from the auxiliary algorithm space. State upfront that using the output array as dynamic working memory satisfies the O(1) extra space constraint.

COMPLEXITY AT A GLANCE

⏱ Time:O(N)

💾 Space:O(1)

Core Theory — Why This Approach?

The fundamental challenge of calculating the product of an array excluding the current element lies in bypassing the division operation while achieving linear performance. A naive division approach would calculate the total product of all elements and divide by each element individually; however, this fails immediately when zeros are present due to division-by-zero errors, and violates explicit problem constraints that disallow division operators. Additionally, computing the product using nested iteration yields an O(N^2) complexity, which scales poorly for large inputs where N exceeds 10^5 elements.

To achieve linear O(N) execution time without division, we decompose the total product excluding index i into two independent scalar sub-products: the prefix product (the product of all elements strictly to the left of index i) and the suffix product (the product of all elements strictly to the right of index i). Mathematically, for any index i, result[i] = Prefix[i - 1] * Suffix[i + 1], with boundary conditions defined such that Prefix[-1] = 1 and Suffix[N] = 1.

By leveraging the Prefix/Suffix pattern, we transform the problem into two sequential linear sweeps over the array. The first pass populates the prefix products into our output array, while the second pass iterates backward, maintaining a running suffix product scalar to dynamically update the final result in-place. This optimal approach operates in O(N) time and requires O(1) auxiliary space beyond the memory allocated for the returned result array.

Interview Questions on This Problem

Q1How would you handle integer overflow if the product of array elements exceeds standard 32-bit integer limits?

To prevent integer overflow, we can cast intermediate multiplications to 64-bit integers (e.g., long long in C++ or long in Java/C#) or return the result modulo a specified large prime (e.g., 10^9 + 7). In Python, integers automatically scale to arbitrary precision, avoiding hard overflow, though computational overhead increases.

Q2Can this prefix/suffix decomposition approach be generalized to non-multiplicative operations?

Yes, this pattern works for any algebraic monoid operation that possesses an associative property and an identity element. Examples include cumulative sums (identity 0), bitwise XOR (identity 0), minimum/maximum bounds, and matrix multiplications, provided the order of operations is maintained.

Q3If we were allowed to use division, how would the edge cases involving zeros be explicitly handled?

If division were permitted: 1) If there are 2 or more zeros, every element in the output array is 0. 2) If there is exactly 1 zero, all elements except the zero's index will be 0, while the zero's index gets the product of all non-zero elements. 3) If there are no zeros, result[i] = total_product / values[i].

Examples

Example 1

Input

values = [2, 4, 1, 5]

Output

[20, 10, 40, 8]

Explanation: For index 0: 4 * 1 * 5 = 20. For index 1: 2 * 1 * 5 = 10. For index 2: 2 * 4 * 5 = 40. For index 3: 2 * 4 * 1 = 8.

Example 2

Input

values = [-3, 0, 2, -1]

Output

[0, 6, 0, 0]

Explanation: For index 0: 0 * 2 * (-1) = 0. For index 1: (-3) * 2 * (-1) = 6. For index 2: (-3) * 0 * (-1) = 0. For index 3: (-3) * 0 * 2 = 0.

Example 3

Input

values = [3, -2, -4, 2]

Output

[16, -24, -12, 24]

Explanation: For index 0: (-2) * (-4) * 2 = 16. For index 1: 3 * (-4) * 2 = -24. For index 2: 3 * (-2) * 2 = -12. For index 3: 3 * (-2) * (-4) = 24.

Example 4

Input

values = [7, 1]

Output

[1, 7]

Explanation: For index 0: the product of all elements except values[0] is 1. For index 1: the product of all elements except values[1] is 7.

Constraints

2 <= values.length <= 10^5
-30 <= values[i] <= 30
The product of any prefix or suffix of values is guaranteed to fit within a 32-bit signed integer.

Optimal Approach & Strategy

The optimal approach uses a two-pass technique using prefix and suffix running products. The first pass stores left prefix products in the output array, and the second backward pass multiplies right suffix products using a single scalar variable in O(N) time and O(1) extra space.

Brute Force Approach

The brute force approach uses a nested loop where for each element at index i, an inner loop multiplies every other element at index j where j != i. This results in an inefficient O(N^2) time complexity and O(1) space.

Code Solutions

Language:

JavaScript Solution

Time: O(N)

function arrayProductExclusions(values) {
    const n = values.length;
    const result = new Array(n).fill(1);
    let prefix = 1;
    for (let i = 0; i < n; ++i) {
        result[i] = prefix;
        prefix *= values[i];
    }
    let suffix = 1;
    for (let i = n - 1; i >= 0; --i) {
        result[i] *= suffix;
        suffix *= values[i];
    }
    return result;
}

console.log(arrayProductExclusions([2, 4, 1, 5]).join(' '));

#include <iostream>
#include <vector>

std::vector<long long> arrayProductExclusions(const std::vector<int>& values) {
    size_t n = values.size();
    std::vector<long long> result(n, 1);
    long long prefix = 1;
    for (size_t i = 0; i < n; ++i) {
        result[i] = prefix;
        prefix *= values[i];
    }
    long long suffix = 1;
    for (size_t i = n; i-- > 0;) {
        result[i] *= suffix;
        suffix *= values[i];
    }
    return result;
}

int main() {
    std::vector<int> values = {2, 4, 1, 5};
    std::vector<long long> result = arrayProductExclusions(values);
    for (size_t i = 0; i < result.size(); ++i) {
        std::cout << result[i];
        if (i + 1 < result.size()) std::cout << " ";
    }
    std::cout << std::endl;
    return 0;
}

import java.util.*;

public class Main {
    public static long[] arrayProductExclusions(int[] values) {
        int n = values.length;
        long[] result = new long[n];
        long prefix = 1;
        for (int i = 0; i < n; ++i) {
            result[i] = prefix;
            prefix *= values[i];
        }
        long suffix = 1;
        for (int i = n - 1; i >= 0; --i) {
            result[i] *= suffix;
            suffix *= values[i];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] values = {2, 4, 1, 5};
        long[] result = arrayProductExclusions(values);
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i]);
            if (i + 1 < result.length) System.out.print(" ");
        }
        System.out.println();
    }
}

def array_product_exclusions(values):
    n = len(values)
    result = [1] * n
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= values[i]
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= values[i]
    return result

if __name__ == "__main__":
    print(' '.join(map(str, array_product_exclusions([2, 4, 1, 5]))))

function arrayProductExclusions(values) {
    const n = values.length;
    const result = new Array(n).fill(1);
    let prefix = 1;
    for (let i = 0; i < n; ++i) {
        result[i] = prefix;
        prefix *= values[i];
    }
    let suffix = 1;
    for (let i = n - 1; i >= 0; --i) {
        result[i] *= suffix;
        suffix *= values[i];
    }
    return result;
}

console.log(arrayProductExclusions([2, 4, 1, 5]).join(' '));

Asked in Top Tech Interviews

OracleTCS

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.