Product Array

Given an array of integers, write a function buildProductArray that returns an array where each item is the product of all the items in the input array except for the item at that index.

Constraints:

Solve this without using division
You can create a results array, and it won't count against your space complexity
Memory may be a concern though, so try to limit your use of additional data structures

Breakdown

Approach and test strategy

Prefix and suffix products that both exclude the current position

Read the approach, boundary cases, and complexity

Write the product strictly to the left of each index into the output. Scan backward with a scalar product strictly to the right and multiply it into each output entry. Both accumulators start at one, the product of an empty segment. Update an accumulator after using it for the current position so the excluded value never enters its own result. Division is unnecessary, including when zeros occur.

Cases to check

Test empty input and a singleton, whose result is [1].
Try one zero, two zeros, and negative values.
Check input preservation and make the representable-product assumption explicit.

Cost model

Two scans take O(n) time, with O(1) auxiliary scalar state beyond the required O(n) output. Arbitrary-precision integer multiplication needs an additional numeric-size cost model.

Programming languages for this lesson

Starter code and reference implementations are available in:

The editor shows which of these languages can run on this deployment.

Follow teacher

Table of Contents

Validate My Answer

You may immediately recognize a brute force O(n²) answer. You can get this down to O(n).
You may want to add additional arrays to get the O(n) time complexity. However, you can solve this without any additional data structures other than your results array.
To get it to O(n) without additional arrays, you may have to perform sequential O(n) time complexity operations.
Does your solution handle 0 or negative numbers?

Follow teacher

Table of Contents

Test Results

Run your code and see results here...

/**
 * @param {List [int]} input
 * @return {List [int]}
 */
const buildProductArray = (input) => {
  // Your solution here
};

Product Array

Given an array of integers, write a function buildProductArray that returns an array where each item is the product of all the items in the input array except for the item at that index.

Constraints:

Solve this without using division
You can create a results array, and it won't count against your space complexity
Memory may be a concern though, so try to limit your use of additional data structures

/**
 * @param {List [int]} input
 * @return {List [int]}
 */
const buildProductArray = (input) => {
  // Your solution here
};