Array Of Products

Tags

Array Of Products

Category

Arrays

Difficulty

Medium

Problem Statement

Given a non-empty array of integers, return an array of the same length where each element at index i is equal to the product of every other element in the original array (i.e., the product of all elements except array[i]). Solve it without using division.

Intuition

For each index i, the product of all elements except array[i] equals the product of all elements to the left of i multiplied by the product of all elements to the right of i. By precomputing prefix products (left-to-right) and suffix products (right-to-left), we can combine them in a final pass.

Approach

  1. Create an output array of the same length, initialized to 1.
  2. First pass (left to right): maintain a running product. For each index i, set output[i] = runningProduct, then multiply runningProduct by array[i].
  3. Second pass (right to left): maintain a running product. For each index i from the end, multiply output[i] by runningProduct, then multiply runningProduct by array[i].
  4. Return the output array.

Pseudocode

function arrayOfProducts(array):
    n = length(array)
    products = array of size n, filled with 1

    leftRunning = 1
    for i from 0 to n - 1:
        products[i] = leftRunning
        leftRunning *= array[i]

    rightRunning = 1
    for i from n - 1 down to 0:
        products[i] *= rightRunning
        rightRunning *= array[i]

    return products

Time & Space Complexity

  • Time: O(n) — two linear passes through the array.
  • Space: O(n) for the output array. If the output array does not count as extra space, the auxiliary space is O(1).

Key Insights

  • The two-pass approach elegantly avoids division, which would fail with zeros in the array.
  • The running product variable replaces the need for separate prefix and suffix arrays, saving space.
  • This pattern of left-right accumulation appears in many array problems (e.g., trapping rain water).

Edge Cases

  • Array of length 1: the product of no other elements is 1, so return [1].
  • Array contains a zero: all products except at the zero's index will be 0. If there are two or more zeros, every product is 0.
  • Array contains negative numbers: the algorithm handles them naturally since multiplication is sign-aware.
  • Very large products: consider overflow in languages without arbitrary-precision integers.

Linked mentions