Product of Array Except Self

Medium Arrays

Return an array where each element is the product of all others, in O(n) without using division (prefix and suffix passes).

Sample input

[1, 2, 3, 4]

Sample output

24 12 8 6

Solution

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

print(*product_except_self([1, 2, 3, 4]))

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

console.log(productExceptSelf([1, 2, 3, 4]).join(" "));

import java.util.Arrays;
import java.util.stream.Collectors;

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

    public static void main(String[] args) {
        int[] res = productExceptSelf(new int[]{1, 2, 3, 4});
        System.out.println(Arrays.stream(res).mapToObj(String::valueOf).collect(Collectors.joining(" ")));
    }
}

fun productExceptSelf(nums: IntArray): IntArray {
    val n = nums.size
    val result = IntArray(n) { 1 }
    var prefix = 1
    for (i in 0 until n) {
        result[i] = prefix
        prefix *= nums[i]
    }
    var suffix = 1
    for (i in n - 1 downTo 0) {
        result[i] *= suffix
        suffix *= nums[i]
    }
    return result
}

fun main() {
    println(productExceptSelf(intArrayOf(1, 2, 3, 4)).joinToString(" "))
}

func productExceptSelf(_ nums: [Int]) -> [Int] {
    let n = nums.count
    var result = [Int](repeating: 1, count: n)
    var prefix = 1
    for i in 0..<n {
        result[i] = prefix
        prefix *= nums[i]
    }
    var suffix = 1
    for i in stride(from: n - 1, through: 0, by: -1) {
        result[i] *= suffix
        suffix *= nums[i]
    }
    return result
}

print(productExceptSelf([1, 2, 3, 4]).map(String.init).joined(separator: " "))

List<int> productExceptSelf(List<int> nums) {
  final n = nums.length;
  final result = List.filled(n, 1);
  var prefix = 1;
  for (var i = 0; i < n; i++) {
    result[i] = prefix;
    prefix *= nums[i];
  }
  var suffix = 1;
  for (var i = n - 1; i >= 0; i--) {
    result[i] *= suffix;
    suffix *= nums[i];
  }
  return result;
}

void main() {
  print(productExceptSelf([1, 2, 3, 4]).join(' '));
}

#include <iostream>
#include <vector>
using namespace std;

vector<int> productExceptSelf(const vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, 1);
    int prefix = 1;
    for (int i = 0; i < n; i++) {
        result[i] = prefix;
        prefix *= nums[i];
    }
    int suffix = 1;
    for (int i = n - 1; i >= 0; i--) {
        result[i] *= suffix;
        suffix *= nums[i];
    }
    return result;
}

int main() {
    vector<int> res = productExceptSelf({1, 2, 3, 4});
    for (int i = 0; i < (int) res.size(); i++) {
        cout << res[i];
        if (i < (int) res.size() - 1) cout << " ";
    }
    cout << endl;
    return 0;
}

#include <stdio.h>

int main() {
    int nums[] = {1, 2, 3, 4};
    int n = 4;
    int result[4];
    int prefix = 1;
    for (int i = 0; i < n; i++) {
        result[i] = prefix;
        prefix *= nums[i];
    }
    int suffix = 1;
    for (int i = n - 1; i >= 0; i--) {
        result[i] *= suffix;
        suffix *= nums[i];
    }
    for (int i = 0; i < n; i++) {
        printf("%d", result[i]);
        if (i < n - 1) printf(" ");
    }
    printf("\n");
    return 0;
}