Solutions

1. Brute Force

O(n²) time | O(1) space

Intuition

For every index in the array, we can multiply all the elements except the element on that index with each other and save the answer.

Algorithm

Create an empty array for the result.
Iterate through the outer loop from the first element to the last element with i index.
For each outer loop iteration, create a product integer variable and iterate through the inner loop from the first element to the last element with j index.
Multiply the product by the element's value at each iteration except the outer element when i == j.
Add the product to the result when the inner loop finishes.

0123

i == j, skip

1 / 17

Code

def productExceptSelf(nums: list[int]) -> list[int]:
    result = []
    for i in range(len(nums)):
        product = 1
        for j in range(len(nums)):
            if j != i:
                product *= nums[j]
        result.append(product)
    return result

/**
 * @param {number[]} nums
 * @returns {number[]}
 */
var productExceptSelf = function (nums) {
  const result = []
  for (let i = 0; i < nums.length; i++) {
    let product = 1
    for (let j = 0; j < nums.length; j++) {
      if (j !== i) product *= nums[j]
    }
    result.push(product)
  }
  return result
}

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            int product = 1;
            for (int j = 0; j < nums.length; j++) {
                if (j != i) product *= nums[j];
            }
            result[i] = product;
        }
        return result;
    }
}

2. Division

O(n) time | O(1) space

Intuition

We can first calculate the total product of all the elements. Then the answer for each element will be the total product divided by this element.

However, we can't divide by zero, so it should be handled separately:

If there is more than one zero element in the array, the answer for all the elements will be zero since any number multiplied by zero is zero.
If there is one zero element in the array, the answer for each other element will be zero except the zero element itself.

Algorithm

Calculate the total product excluding zeroes and count the number of zeroes with one loop.
Return an array of zeroes if there is more than one zero.
Iterate through the whole array, calculating the answer for each element by dividing the total product by the element.
If there is one zero, the answer for each other element should be zero and the zero element's answer should be the total product.

0123

product = 1 * 1 = 1

1 / 9

Code

def productExceptSelf(nums: list[int]) -> list[int]:
    zeros = 0
    product = 1
    for n in nums:
        if n == 0:
            zeros += 1
        else:
            product *= n
    if zeros > 1:
        return [0] * len(nums)
    result = []
    for n in nums:
        if zeros == 0:
            result.append(product // n)
        else:
            result.append(product if n == 0 else 0)
    return result

/**
 * @param {number[]} nums
 * @returns {number[]}
 */
var productExceptSelf = function (nums) {
  let zeros = 0
  let product = 1
  for (const n of nums) {
    if (n === 0) zeros++
    else product *= n
  }
  if (zeros > 1) return new Array(nums.length).fill(0)
  const result = []
  for (const n of nums) {
    if (zeros === 0) result.push(product / n)
    else result.push(n === 0 ? product : 0)
  }
  return result
}

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int zeros = 0;
        int product = 1;
        for (int n : nums) {
            if (n == 0) zeros++;
            else product *= n;
        }
        int[] result = new int[nums.length];
        if (zeros > 1) return result;
        for (int i = 0; i < nums.length; i++) {
            if (zeros == 0) result[i] = product / nums[i];
            else result[i] = nums[i] == 0 ? product : 0;
        }
        return result;
    }
}

3. Prefix and Suffix

O(n) time | O(1) space

Intuition

The product of everything except one element is the product of everything on its left multiplied by the product of everything on its right.

Both of those can be precalculated for each element with one loop from the left and one loop from the right.

Algorithm

Create a result array of the same length as the input.
Create a prefix_product variable with initial value 1.
Iterate through the loop from the first element to the last element with i index, putting prefix_product into result on i and then multiplying it by the element on i.
Create a suffix_product variable with initial value 1.
Iterate through the loop from the last element to the first element with i index, multiplying result's element on i by suffix_product and then multiplying the suffix_product by the element on i.

0123

prefix_product = 1 * 1 = 1

1 / 9

Code

def productExceptSelf(nums: list[int]) -> list[int]:
    result = [1] * len(nums)
    prefix_product = 1
    for i in range(len(nums)):
        result[i] = prefix_product
        prefix_product *= nums[i]
    suffix_product = 1
    for i in range(len(nums) - 1, -1, -1):
        result[i] *= suffix_product
        suffix_product *= nums[i]
    return result

/**
 * @param {number[]} nums
 * @returns {number[]}
 */
var productExceptSelf = function (nums) {
  const result = new Array(nums.length).fill(1)
  let prefixProduct = 1
  for (let i = 0; i < nums.length; i++) {
    result[i] = prefixProduct
    prefixProduct *= nums[i]
  }
  let suffixProduct = 1
  for (let i = nums.length - 1; i >= 0; i--) {
    result[i] *= suffixProduct
    suffixProduct *= nums[i]
  }
  return result
}

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] result = new int[nums.length];
        int prefixProduct = 1;
        for (int i = 0; i < nums.length; i++) {
            result[i] = prefixProduct;
            prefixProduct *= nums[i];
        }
        int suffixProduct = 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            result[i] *= suffixProduct;
            suffixProduct *= nums[i];
        }
        return result;
    }
}