Run your code 2 more times to open the solutions. The idea sticks better after an attempt. Product of Array Except Self in Python
3 reference approaches in Python, from brute force to the one to reach for. Compare them with yours.
For each position i, start a product at 1 and multiply in every element whose index is not i. It needs no extra list beyond the answer, but it does about n² multiplications.
def product_except_self(nums: list[int]) -> list[int]:
n = len(nums)
answer = []
for i in range(n):
p = 1
for j in range(n):
if j != i:
p *= nums[j]
answer.append(p)
return answer
left[i] holds the product of everything before i and right[i] the product of everything after it, both starting from 1 at the ends. One pass fills each list, and answer[i] is left[i] * right[i].
def product_except_self(nums: list[int]) -> list[int]:
n = len(nums)
left = [1] * n # product of nums[0..i-1]
right = [1] * n # product of nums[i+1..n-1]
for i in range(1, n):
left[i] = left[i - 1] * nums[i - 1]
for i in range(n - 2, -1, -1):
right[i] = right[i + 1] * nums[i + 1]
return [left[i] * right[i] for i in range(n)]
Write the left products straight into answer, then walk back from the end with a single number suffix that holds the product of everything to the right. Multiplying it in before updating it keeps nums[i] itself out. The output list doesn't count as extra space, so this is O(1) beyond it.
def product_except_self(nums: list[int]) -> list[int]:
n = len(nums)
answer = [1] * n
for i in range(1, n):
answer[i] = answer[i - 1] * nums[i - 1]
suffix = 1
for i in range(n - 1, -1, -1):
answer[i] *= suffix
suffix *= nums[i]
return answer
Product of Array Except Self in JavaScript
3 reference approaches in JavaScript, from brute force to the one to reach for. Compare them with yours.
For each index i, multiply every element whose index is not i into a product that starts at 1, then push it. Two nested loops, so about n² multiplications.
function productExceptSelf(nums) {
const answer = [];
for (let i = 0; i < nums.length; i++) {
let p = 1;
for (let j = 0; j < nums.length; j++) {
if (j !== i) p *= nums[j];
}
answer.push(p);
}
return answer;
}
left[i] is the product of everything before i, right[i] the product of everything after it; new Array(n).fill(1) sets the empty products at the ends. Each answer is left[i] * right[i].
function productExceptSelf(nums) {
const n = nums.length;
const left = new Array(n).fill(1);
const right = new Array(n).fill(1);
for (let i = 1; i < n; i++) left[i] = left[i - 1] * nums[i - 1];
for (let i = n - 2; i >= 0; i--) right[i] = right[i + 1] * nums[i + 1];
return left.map((l, i) => l * right[i]);
}
The first pass writes the left products into answer. The second walks back with one variable suffix, multiplying it into answer[i] before folding nums[i] into it. No array besides the output, so O(1) extra space.
function productExceptSelf(nums) {
const n = nums.length;
const answer = new Array(n).fill(1);
for (let i = 1; i < n; i++) answer[i] = answer[i - 1] * nums[i - 1];
let suffix = 1;
for (let i = n - 1; i >= 0; i--) {
answer[i] *= suffix;
suffix *= nums[i];
}
return answer;
}
Product of Array Except Self in TypeScript
3 reference approaches in TypeScript, from brute force to the one to reach for. Compare them with yours.
For each index i, multiply every other element into a product that starts at 1. Simple and obviously correct, but it costs about n² multiplications.
function productExceptSelf(nums: number[]): number[] {
const answer: number[] = [];
for (let i = 0; i < nums.length; i++) {
let p = 1;
for (let j = 0; j < nums.length; j++) {
if (j !== i) p *= nums[j];
}
answer.push(p);
}
return answer;
}
Two number[] arrays: left[i] is the product before i, right[i] the product after it, each 1 at its open end. The answer multiplies the two slot by slot.
function productExceptSelf(nums: number[]): number[] {
const n = nums.length;
const left: number[] = new Array(n).fill(1);
const right: number[] = new Array(n).fill(1);
for (let i = 1; i < n; i++) left[i] = left[i - 1] * nums[i - 1];
for (let i = n - 2; i >= 0; i--) right[i] = right[i + 1] * nums[i + 1];
return left.map((l, i) => l * right[i]);
}
Store the left products in answer, then sweep back with one suffix number: multiply it into answer[i], then fold nums[i] into it for the next slot. Only the output array is allocated.
function productExceptSelf(nums: number[]): number[] {
const n = nums.length;
const answer: number[] = new Array(n).fill(1);
for (let i = 1; i < n; i++) answer[i] = answer[i - 1] * nums[i - 1];
let suffix = 1;
for (let i = n - 1; i >= 0; i--) {
answer[i] *= suffix;
suffix *= nums[i];
}
return answer;
}
Product of Array Except Self in Java
3 reference approaches in Java, from brute force to the one to reach for. Compare them with yours.
For each index i, multiply every element at a different index into an int that starts at 1. The result array is the only allocation, but the double loop does about n² multiplications.
import java.util.*;
public class Main {
static int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] answer = new int[n];
for (int i = 0; i < n; i++) {
int p = 1;
for (int j = 0; j < n; j++) {
if (j != i) p *= nums[j];
}
answer[i] = p;
}
return answer;
}
}
left[i] holds the product of everything before i and right[i] everything after it. A new int[] starts as zeros, so the open ends are set to 1 by hand before the two passes.
import java.util.*;
public class Main {
static int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] left = new int[n];
int[] right = new int[n];
left[0] = 1;
for (int i = 1; i < n; i++) left[i] = left[i - 1] * nums[i - 1];
right[n - 1] = 1;
for (int i = n - 2; i >= 0; i--) right[i] = right[i + 1] * nums[i + 1];
int[] answer = new int[n];
for (int i = 0; i < n; i++) answer[i] = left[i] * right[i];
return answer;
}
}
The left products go straight into answer; the second pass walks back with one int suffix, multiplying it in before folding nums[i] into it. Nothing is allocated besides the result.
import java.util.*;
public class Main {
static int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] answer = new int[n];
answer[0] = 1;
for (int i = 1; i < n; i++) answer[i] = answer[i - 1] * nums[i - 1];
int suffix = 1;
for (int i = n - 1; i >= 0; i--) {
answer[i] *= suffix;
suffix *= nums[i];
}
return answer;
}
}
Product of Array Except Self in Go
3 reference approaches in Go, from brute force to the one to reach for. Compare them with yours.
For each index i, a product p starts at 1 and the inner range loop multiplies in every value at another index. About n² multiplications, no slice besides the result.
package main
func productExceptSelf(nums []int) []int {
answer := make([]int, len(nums))
for i := range nums {
p := 1
for j, v := range nums {
if j != i {
p *= v
}
}
answer[i] = p
}
return answer
}
left[i] is the product before i, right[i] the product after it. make zeroes a new slice, so the open ends are set to 1 first; the answer multiplies the two slices index by index.
package main
func productExceptSelf(nums []int) []int {
n := len(nums)
left := make([]int, n)
right := make([]int, n)
left[0] = 1
for i := 1; i < n; i++ {
left[i] = left[i-1] * nums[i-1]
}
right[n-1] = 1
for i := n - 2; i >= 0; i-- {
right[i] = right[i+1] * nums[i+1]
}
answer := make([]int, n)
for i := range answer {
answer[i] = left[i] * right[i]
}
return answer
}
The left products go straight into answer; then a loop from the end multiplies one running suffix into each slot before folding nums[i] into it. Only the result slice is allocated.
package main
func productExceptSelf(nums []int) []int {
n := len(nums)
answer := make([]int, n)
answer[0] = 1
for i := 1; i < n; i++ {
answer[i] = answer[i-1] * nums[i-1]
}
suffix := 1
for i := n - 1; i >= 0; i-- {
answer[i] *= suffix
suffix *= nums[i]
}
return answer
}
Product of Array Except Self in C#
3 reference approaches in C#, from brute force to the one to reach for. Compare them with yours.
For each index i, multiply every element at another index into a product that starts at 1. About n² multiplications, and no array besides the result.
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
public static int[] ProductExceptSelf(int[] nums)
{
int n = nums.Length;
var answer = new int[n];
for (int i = 0; i < n; i++)
{
int p = 1;
for (int j = 0; j < n; j++)
{
if (j != i) p *= nums[j];
}
answer[i] = p;
}
return answer;
}
}
left[i] holds the product before i and right[i] the product after it. A new int[] is all zeros, so the open ends start at 1; each answer is left[i] * right[i].
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
public static int[] ProductExceptSelf(int[] nums)
{
int n = nums.Length;
var left = new int[n];
var right = new int[n];
left[0] = 1;
for (int i = 1; i < n; i++) left[i] = left[i - 1] * nums[i - 1];
right[n - 1] = 1;
for (int i = n - 2; i >= 0; i--) right[i] = right[i + 1] * nums[i + 1];
var answer = new int[n];
for (int i = 0; i < n; i++) answer[i] = left[i] * right[i];
return answer;
}
}
The left products are written into answer; a second pass from the end multiplies one running suffix into each slot before folding nums[i] into it. Only the result array is allocated.
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
public static int[] ProductExceptSelf(int[] nums)
{
int n = nums.Length;
var answer = new int[n];
answer[0] = 1;
for (int i = 1; i < n; i++) answer[i] = answer[i - 1] * nums[i - 1];
int suffix = 1;
for (int i = n - 1; i >= 0; i--)
{
answer[i] *= suffix;
suffix *= nums[i];
}
return answer;
}
}
Product of Array Except Self in C++
3 reference approaches in C++, from brute force to the one to reach for. Compare them with yours.
For each index i, multiply every element at another index into a product that starts at 1. The vector is taken by reference, so nothing is copied, but the double loop does about n² multiplications.
#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = (int)nums.size();
vector<int> answer(n);
for (int i = 0; i < n; i++) {
int p = 1;
for (int j = 0; j < n; j++) {
if (j != i) p *= nums[j];
}
answer[i] = p;
}
return answer;
}
};
vector<int> left(n, 1) and right(n, 1) start every slot at the empty product. One pass fills the products before each index, one the products after it, and the answer multiplies them slot by slot.
#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = (int)nums.size();
vector<int> left(n, 1), right(n, 1);
for (int i = 1; i < n; i++) left[i] = left[i - 1] * nums[i - 1];
for (int i = n - 2; i >= 0; i--) right[i] = right[i + 1] * nums[i + 1];
vector<int> answer(n);
for (int i = 0; i < n; i++) answer[i] = left[i] * right[i];
return answer;
}
};
The left products go straight into answer; the second loop walks back with one int suffix, multiplying it in before folding nums[i] into it. The result vector is the only allocation.
#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = (int)nums.size();
vector<int> answer(n, 1);
for (int i = 1; i < n; i++) answer[i] = answer[i - 1] * nums[i - 1];
int suffix = 1;
for (int i = n - 1; i >= 0; i--) {
answer[i] *= suffix;
suffix *= nums[i];
}
return answer;
}
};
Product of Array Except Self in C
3 reference approaches in C, from brute force to the one to reach for. Compare them with yours.
malloc a result of numsSize ints and set *returnSize to the same length. For each index i, multiply every element at a different index into an int that starts at 1. Nothing else is allocated, but the double loop does about n² multiplications.
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
/**
* Note: the returned array must be malloc'ed; the caller frees it.
*/
int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
int* answer = malloc(numsSize * sizeof *answer);
for (int i = 0; i < numsSize; i++) {
int p = 1;
for (int j = 0; j < numsSize; j++) {
if (j != i) p *= nums[j];
}
answer[i] = p;
}
*returnSize = numsSize;
return answer;
}
Two scratch arrays: left[i] holds the product of everything before i and right[i] everything after it, with 1 at the open ends. The answer is their element-wise product; the scratch arrays are freed before returning, the result is not.
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
/**
* Note: the returned array must be malloc'ed; the caller frees it.
*/
int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
int* left = malloc(numsSize * sizeof *left);
int* right = malloc(numsSize * sizeof *right);
left[0] = 1;
for (int i = 1; i < numsSize; i++) left[i] = left[i - 1] * nums[i - 1];
right[numsSize - 1] = 1;
for (int i = numsSize - 2; i >= 0; i--) right[i] = right[i + 1] * nums[i + 1];
int* answer = malloc(numsSize * sizeof *answer);
for (int i = 0; i < numsSize; i++) answer[i] = left[i] * right[i];
free(left);
free(right);
*returnSize = numsSize;
return answer;
}
The left products go straight into the result; the second pass walks back with one int suffix, multiplying it into the slot before folding nums[i] into it. The only allocation is the result the caller frees.
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
/**
* Note: the returned array must be malloc'ed; the caller frees it.
*/
int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
int* answer = malloc(numsSize * sizeof *answer);
answer[0] = 1;
for (int i = 1; i < numsSize; i++) answer[i] = answer[i - 1] * nums[i - 1];
int suffix = 1;
for (int i = numsSize - 1; i >= 0; i--) {
answer[i] *= suffix;
suffix *= nums[i];
}
*returnSize = numsSize;
return answer;
}
Product of Array Except Self in Kotlin
3 reference approaches in Kotlin, from brute force to the one to reach for. Compare them with yours.
IntArray(n) { i -> … } builds the answer from a lambda: for each index i it multiplies every element at a different index into a var that starts at 1. Short, but about n² multiplications.
class Solution {
fun productExceptSelf(nums: IntArray): IntArray {
val n = nums.size
return IntArray(n) { i ->
var p = 1
for (j in 0 until n) {
if (j != i) p *= nums[j]
}
p
}
}
}
left[i] holds the product of everything before i and right[i] everything after it. Both start as IntArray(n) { 1 }, so the open ends are already the empty product; the answer multiplies them position by position.
class Solution {
fun productExceptSelf(nums: IntArray): IntArray {
val n = nums.size
val left = IntArray(n) { 1 }
val right = IntArray(n) { 1 }
for (i in 1 until n) left[i] = left[i - 1] * nums[i - 1]
for (i in n - 2 downTo 0) right[i] = right[i + 1] * nums[i + 1]
return IntArray(n) { left[it] * right[it] }
}
}
The left products go straight into answer; the second pass walks indices.reversed() with one var suffix, multiplying it into the slot before folding nums[i] in. Only the result is allocated.
class Solution {
fun productExceptSelf(nums: IntArray): IntArray {
val answer = IntArray(nums.size) { 1 }
for (i in 1 until nums.size) answer[i] = answer[i - 1] * nums[i - 1]
var suffix = 1
for (i in nums.indices.reversed()) {
answer[i] *= suffix
suffix *= nums[i]
}
return answer
}
}
Product of Array Except Self in Rust
3 reference approaches in Rust, from brute force to the one to reach for. Compare them with yours.
For each index i, iterate over nums with enumerate, skip the element at i and take the product() of the rest. One expression, but about n² multiplications.
impl Solution {
pub fn product_except_self(nums: Vec<i32>) -> Vec<i32> {
(0..nums.len())
.map(|i| {
nums.iter()
.enumerate()
.filter(|&(j, _)| j != i)
.map(|(_, &v)| v)
.product::<i32>()
})
.collect()
}
}
left[i] holds the product of everything before i and right[i] everything after it, both starting as vec![1; n] so the open ends are the empty product. Zipping the two vectors gives the answer.
impl Solution {
pub fn product_except_self(nums: Vec<i32>) -> Vec<i32> {
let n = nums.len();
let mut left = vec![1; n];
let mut right = vec![1; n];
for i in 1..n {
left[i] = left[i - 1] * nums[i - 1];
}
for i in (0..n - 1).rev() {
right[i] = right[i + 1] * nums[i + 1];
}
left.iter().zip(&right).map(|(l, r)| l * r).collect()
}
}
The left products go straight into answer; the second pass walks (0..n).rev() with one suffix, multiplying it into the slot before folding nums[i] in. Only the returned Vec is allocated.
impl Solution {
pub fn product_except_self(nums: Vec<i32>) -> Vec<i32> {
let n = nums.len();
let mut answer = vec![1; n];
for i in 1..n {
answer[i] = answer[i - 1] * nums[i - 1];
}
let mut suffix = 1;
for i in (0..n).rev() {
answer[i] *= suffix;
suffix *= nums[i];
}
answer
}
}
Product of Array Except Self in Swift
3 reference approaches in Swift, from brute force to the one to reach for. Compare them with yours.
For each index i, multiply every element at a different index into a var that starts at 1; where j != i on the inner loop skips the element itself. No extra arrays, but about n² multiplications.
class Solution {
func productExceptSelf(_ nums: [Int]) -> [Int] {
let n = nums.count
var answer = [Int](repeating: 1, count: n)
for i in 0..<n {
var p = 1
for j in 0..<n where j != i {
p *= nums[j]
}
answer[i] = p
}
return answer
}
}
left[i] holds the product of everything before i and right[i] everything after it, both created with repeating: 1 so the open ends are the empty product. zip multiplies them into the answer.
class Solution {
func productExceptSelf(_ nums: [Int]) -> [Int] {
let n = nums.count
var left = [Int](repeating: 1, count: n)
var right = [Int](repeating: 1, count: n)
for i in 1..<n {
left[i] = left[i - 1] * nums[i - 1]
}
for i in stride(from: n - 2, through: 0, by: -1) {
right[i] = right[i + 1] * nums[i + 1]
}
return zip(left, right).map { $0 * $1 }
}
}
The left products go straight into answer; the second pass walks indices.reversed() with one suffix, multiplying it into the slot before folding nums[i] in. Only the result is allocated.
class Solution {
func productExceptSelf(_ nums: [Int]) -> [Int] {
var answer = [Int](repeating: 1, count: nums.count)
for i in 1..<nums.count {
answer[i] = answer[i - 1] * nums[i - 1]
}
var suffix = 1
for i in nums.indices.reversed() {
answer[i] *= suffix
suffix *= nums[i]
}
return answer
}
}
Product of Array Except Self in PHP
3 reference approaches in PHP, from brute force to the one to reach for. Compare them with yours.
For each index $i, multiply every element at a different index into a product that starts at 1 and append it to $answer. No extra arrays, but about n² multiplications.
<?php
class Solution {
/**
* @param int[] $nums
* @return int[]
*/
function productExceptSelf(array $nums): array {
$n = count($nums);
$answer = [];
for ($i = 0; $i < $n; $i++) {
$p = 1;
for ($j = 0; $j < $n; $j++) {
if ($j !== $i) {
$p *= $nums[$j];
}
}
$answer[] = $p;
}
return $answer;
}
}
$left[$i] holds the product of everything before $i and $right[$i] everything after it, both from array_fill(0, $n, 1) so the open ends are the empty product. The answer multiplies them position by position.
<?php
class Solution {
/**
* @param int[] $nums
* @return int[]
*/
function productExceptSelf(array $nums): array {
$n = count($nums);
$left = array_fill(0, $n, 1);
$right = array_fill(0, $n, 1);
for ($i = 1; $i < $n; $i++) {
$left[$i] = $left[$i - 1] * $nums[$i - 1];
}
for ($i = $n - 2; $i >= 0; $i--) {
$right[$i] = $right[$i + 1] * $nums[$i + 1];
}
$answer = [];
for ($i = 0; $i < $n; $i++) {
$answer[] = $left[$i] * $right[$i];
}
return $answer;
}
}
The left products go straight into $answer; the second pass walks back with one $suffix, multiplying it into the slot before folding $nums[$i] in. Writing keys 0 to $n - 1 in order keeps $answer a list.
<?php
class Solution {
/**
* @param int[] $nums
* @return int[]
*/
function productExceptSelf(array $nums): array {
$n = count($nums);
$answer = [1];
for ($i = 1; $i < $n; $i++) {
$answer[$i] = $answer[$i - 1] * $nums[$i - 1];
}
$suffix = 1;
for ($i = $n - 1; $i >= 0; $i--) {
$answer[$i] *= $suffix;
$suffix *= $nums[$i];
}
return $answer;
}
}
Product of Array Except Self in Ruby
3 reference approaches in Ruby, from brute force to the one to reach for. Compare them with yours.
For each index i, multiply every element at a different index into a product that starts at 1. Plain while loops keep the n² multiplications cheap in the interpreter; a block per element would cost several times more.
# @param {Integer[]} nums
# @return {Integer[]}
def product_except_self(nums)
n = nums.length
answer = Array.new(n)
i = 0
while i < n
p = 1
j = 0
while j < n
p *= nums[j] if j != i
j += 1
end
answer[i] = p
i += 1
end
answer
end
left[i] holds the product of everything before i and right[i] everything after it, both from Array.new(n, 1) so the open ends are the empty product. zip and map multiply them into the answer.
# @param {Integer[]} nums
# @return {Integer[]}
def product_except_self(nums)
n = nums.length
left = Array.new(n, 1)
right = Array.new(n, 1)
(1...n).each { |i| left[i] = left[i - 1] * nums[i - 1] }
(n - 2).downto(0) { |i| right[i] = right[i + 1] * nums[i + 1] }
left.zip(right).map { |l, r| l * r }
end
The left products go straight into answer; the second pass counts down with downto and one suffix, multiplying it into the slot before folding nums[i] in. Only the result is allocated.
# @param {Integer[]} nums
# @return {Integer[]}
def product_except_self(nums)
n = nums.length
answer = Array.new(n, 1)
(1...n).each { |i| answer[i] = answer[i - 1] * nums[i - 1] }
suffix = 1
(n - 1).downto(0) do |i|
answer[i] *= suffix
suffix *= nums[i]
end
answer
end
Product of Array Except Self in Dart
3 reference approaches in Dart, from brute force to the one to reach for. Compare them with yours.
List.generate builds the answer: for each index i it multiplies every element at a different index into a product that starts at 1. Short, but about n² multiplications.
class Solution {
List<int> productExceptSelf(List<int> nums) {
final n = nums.length;
return List.generate(n, (i) {
var p = 1;
for (var j = 0; j < n; j++) {
if (j != i) p *= nums[j];
}
return p;
});
}
}
left[i] holds the product of everything before i and right[i] everything after it, both from List.filled(n, 1) so the open ends are the empty product. List.generate multiplies them into the answer.
class Solution {
List<int> productExceptSelf(List<int> nums) {
final n = nums.length;
final left = List.filled(n, 1);
final right = List.filled(n, 1);
for (var i = 1; i < n; i++) {
left[i] = left[i - 1] * nums[i - 1];
}
for (var i = n - 2; i >= 0; i--) {
right[i] = right[i + 1] * nums[i + 1];
}
return List.generate(n, (i) => left[i] * right[i]);
}
}
The left products go straight into answer; the second pass walks back with one suffix, multiplying it into the slot before folding nums[i] in. Only the result is allocated.
class Solution {
List<int> productExceptSelf(List<int> nums) {
final n = nums.length;
final answer = List.filled(n, 1);
for (var i = 1; i < n; i++) {
answer[i] = answer[i - 1] * nums[i - 1];
}
var suffix = 1;
for (var i = n - 1; i >= 0; i--) {
answer[i] *= suffix;
suffix *= nums[i];
}
return answer;
}
}
Product of Array Except Self in Scala
3 reference approaches in Scala, from brute force to the one to reach for. Compare them with yours.
Array.tabulate builds the answer: for each index i a while loop multiplies every element at a different index into a var that starts at 1. About n² multiplications, no boxing.
object Solution {
def productExceptSelf(nums: Array[Int]): Array[Int] = {
val n = nums.length
Array.tabulate(n) { i =>
var p = 1
var j = 0
while (j < n) {
if (j != i) p *= nums(j)
j += 1
}
p
}
}
}
scanLeft(1)(_ * _) gives every prefix product with the empty product 1 first, so left(i) is the product before i; scanRight does the same from the other end, so right(i + 1) is the product after i.
object Solution {
def productExceptSelf(nums: Array[Int]): Array[Int] = {
val left = nums.scanLeft(1)(_ * _) // left(i) = product of nums(0 until i)
val right = nums.scanRight(1)(_ * _) // right(i) = product of nums(i until n)
Array.tabulate(nums.length)(i => left(i) * right(i + 1))
}
}
The left products go straight into answer; the second pass counts down with nums.indices.reverse and one var suffix, multiplying it into the slot before folding nums(i) in. Only the result is allocated.
object Solution {
def productExceptSelf(nums: Array[Int]): Array[Int] = {
val n = nums.length
val answer = Array.fill(n)(1)
for (i <- 1 until n) answer(i) = answer(i - 1) * nums(i - 1)
var suffix = 1
for (i <- nums.indices.reverse) {
answer(i) *= suffix
suffix *= nums(i)
}
answer
}
}
FAQ for Python
Why not divide the total product by each element?
Because a single zero makes the total 0. The zero's own position should hold the product of all the others, but total // nums[i] there raises ZeroDivisionError. Handling that needs a zero count and special cases, and the problem forbids division anyway; the prefix and suffix passes need no special case at all.
Does Python integer overflow matter here?
No. Python integers grow as large as they need to, so the products never wrap. The 32-bit bound in the constraints is for languages with fixed-width int, where the same code would otherwise overflow silently.
Can math.prod replace the inner loop of the brute force?
Yes: math.prod(nums[:i] + nums[i + 1:]) is the same product in one call. It is still O(n²) overall, because each call walks almost the whole list, and it builds a new list every time.
Why does the running version multiply before updating suffix?
At position i, suffix must hold the product of the elements after i only. Multiplying answer[i] *= suffix first and then suffix *= nums[i] keeps nums[i] out of its own answer; swapping the two lines includes it.
Is itertools.accumulate a good fit for the prefix products?
list(accumulate(nums, operator.mul, initial=1)) gives the products of every prefix, one longer than nums, with the empty product 1 first. Its first n entries are exactly the left products; running it on nums[::-1] and reversing the first n entries gives the right ones.
FAQ for JavaScript
Why does my output show -0?
JavaScript numbers are floating point, so -2 * 0 is -0. console.log prints it as -0 and Object.is(-0, 0) is false, but -0 === 0 is true and JSON.stringify(-0) gives "0", so the tests here accept it. Add + 0 to an answer (-0 + 0 is 0) if you want it gone from the printout.
Why not divide the total by each element?
With one zero the total is 0, so every division gives 0 and the zero's own slot, which should hold the product of the others, is wrong; 0 / 0 there is NaN. Two zeros need yet another branch. The problem rules division out for exactly this reason.
Can reduce write the brute force more briefly?
Yes: nums.map((_, i) => nums.reduce((p, v, j) => (j === i ? p : p * v), 1)). It is the same O(n²) work, just as a one-liner.
Do large products lose precision?
Not within these constraints: every product fits a 32-bit integer, far below Number.MAX_SAFE_INTEGER (2^53 - 1). Above that, doubles round and the low digits go wrong; use BigInt values (1n, *) if you need exact huge products.
Why fill the arrays with 1 instead of 0?
1 is the empty product: the first slot has nothing on its left and the last slot nothing on its right, and multiplying by 1 leaves the other side unchanged. Filling with 0 would zero every answer.
FAQ for TypeScript
Why does new Array(n).fill(1) need a type annotation?
new Array(n) on its own is typed any[], and fill(1) keeps that. Writing const left: number[] = new Array(n).fill(1) (or Array<number>(n).fill(1)) makes later mistakes, such as storing a string, compile errors.
Would Int32Array be faster?
new Int32Array(n).fill(1) gives a compact typed array, and every product here fits 32 bits. It wraps silently past that range, though, and the function must still return a number[], so convert with Array.from(answer) at the end.
Why does a zero sometimes print as -0?
Numbers are IEEE doubles, so -2 * 0 is -0. -0 === 0 is true and JSON.stringify writes it as 0, which is why the tests accept it; Object.is(-0, 0) is the one check that tells them apart.
Why not divide the total product by nums[i]?
A zero makes the total 0, so the zero's own slot comes out as NaN (0 / 0) instead of the product of the others. The prefix and suffix approach needs no special case for zeros at all.
Does the running version really use O(1) space?
Beyond the result, yes: the only other storage is the suffix number. The output array is required by the signature, so it is not counted as extra space.
FAQ for Java
What happens if the products overflow an int?
Java int multiplication wraps silently at 32 bits, so an out-of-range product turns into a wrong number with no error. The constraints keep every product in range. For wider inputs use long arrays, or Math.multiplyExact to get an ArithmeticException instead of a wrapped value.
Why set left[0] and right[n - 1] to 1?
new int[n] fills the array with zeros, and a zero at an open end would zero every product built from it. 1 is the empty product, so it is the right start; Arrays.fill(left, 1) does the same for the whole array.
Why not divide the total product by each element?
One zero makes the total 0, and total / nums[i] at the zero throws ArithmeticException: / by zero. Even with a zero count to dodge that, the problem rules division out.
Can streams write this more briefly?
The brute force fits in one expression: IntStream.range(0, n).map(i -> IntStream.range(0, n).filter(j -> j != i).map(j -> nums[j]).reduce(1, (a, b) -> a * b)).toArray(). It is still O(n²) and slower than the loops; the prefix passes have no tidy stream form because each step depends on the previous one.
Does the running version count as O(1) space?
Yes, by the usual convention that the returned array is not extra space. Apart from it the method keeps one int.
FAQ for Go
Can the products overflow in Go?
Go int is 64 bits on the platforms you are likely to use, so these products are nowhere near its limit. When it does overflow it wraps silently, with no panic; for exact products of any size use math/big.
Why set the first slot to 1 after make?
make([]int, n) returns a slice of zeros, and the first slot has nothing on its left, so its product is the empty product 1. Leaving it at 0 would make every later prefix 0.
Should the result reuse the nums slice?
It could overwrite nums in place to save the allocation, but that changes the caller's data, because a slice shares its backing array. Allocating a fresh answer with make keeps the input intact, which is what callers expect.
Why not divide the total by each element?
Integer division by zero panics in Go (runtime error: integer divide by zero), so a single zero in the slice crashes the division approach unless you count zeros and branch. The prefix and suffix passes handle zeros with no special case.
Is the running version really O(1) extra space?
Yes, counting the returned slice as output rather than extra space, which is the usual convention. Besides it there is one int, suffix.
FAQ for C#
Can the products overflow an int?
C# int arithmetic wraps silently by default, so an out-of-range product becomes a wrong number. The constraints keep every product within 32 bits. Wrap the multiplications in checked(...) to get an OverflowException instead, or switch to long for wider inputs.
Why not divide the total product by nums[i]?
A zero makes the total 0, and total / nums[i] at the zero throws DivideByZeroException. Working around it takes a zero count and two special cases; the prefix and suffix passes need none, and the problem forbids division anyway.
Is there a LINQ one-liner?
For the brute force: nums.Select((_, i) => nums.Where((_, j) => j != i).Aggregate(1, (a, b) => a * b)).ToArray(). It is still O(n²) and allocates an iterator per element, so the loops are faster.
Could Span<int> help?
Span<int> lets you slice nums without copying, but every approach here already walks the array by index, so it adds nothing. It matters more when a helper needs a sub-range of the input.
Why does the running version count as O(1) space?
The returned array is the output, which the usual convention does not count. Apart from it the method keeps a single int suffix.
FAQ for C++
Is overflow a problem with int products?
Signed int overflow is undefined behaviour in C++, not just a wrapped value, so the compiler may assume it never happens. The constraints keep every product within 32 bits. For wider inputs use long long, or __builtin_mul_overflow on GCC and Clang to detect it.
Why loop from n - 2 down with an int instead of size_t?
A size_t counter is unsigned, so i >= 0 is always true and i-- past zero wraps to a huge index. Casting nums.size() to int once keeps the backward loops simple and safe.
Why not divide the total product by each element?
Integer division by zero is undefined behaviour and usually crashes with SIGFPE, so one zero in the input breaks it. The prefix and suffix passes need no zero handling, and the problem rules division out.
Can std::partial_sum compute the prefix products?
Yes: partial_sum(nums.begin(), nums.end() - 1, left.begin() + 1, multiplies<int>()) from <numeric> (with <functional>) fills left[1..n-1] with running products, leaving left[0] at 1. Reverse iterators do the same for the suffix side.
Should I use bits/stdc++.h?
No. It pulls in the whole standard library and costs a couple of seconds on every Run here. <vector> is all this problem needs.
FAQ for C
Why set returnSize to numsSize?
A returned int* carries no length, so the caller reads it from *returnSize. Every position gets an answer, so the result is exactly as long as the input: *returnSize = numsSize.
Can I write the answers into nums instead of mallocing a result?
Not for the running version: the second pass still reads nums[i] after the first pass would have overwritten it, and the caller owns nums. The result has to be its own malloc'ed block, which is also what the caller expects to free.
What if a product overflows an int?
Signed overflow is undefined behaviour in C, not a wrap, so the compiler may assume it never happens. The constraints keep every product within 32 bits; for wider inputs compute in long long or check with __builtin_mul_overflow.
Why not divide the total product by each element?
One zero makes the total 0, and total / nums[i] at the zero is a division by zero, which crashes with SIGFPE on most machines. The problem rules division out anyway, and the prefix and suffix passes need no zero handling.
Why does calloc not help for the prefix arrays?
calloc fills the block with zeros, and a zero at an open end zeros every product built from it. The empty product is 1, so the ends are set by hand and every other slot is written by the loop, which makes plain malloc enough.
FAQ for Kotlin
What happens if a product overflows an Int?
Kotlin Int multiplication wraps silently at 32 bits on the JVM, so an out-of-range product becomes a wrong number with no exception. The constraints keep every product in range; for wider inputs use LongArray, or Math.multiplyExact to throw instead of wrap.
Why IntArray(n) { 1 } and not IntArray(n)?
IntArray(n) is filled with zeros, and a zero at an open end zeros every product built from it. The initializer lambda fills each slot with 1, the empty product, so the ends need no special case.
Is nums.indices.reversed() slower than a downTo loop?
No. The Kotlin compiler treats it as an intrinsic and turns for (i in nums.indices.reversed()) into a plain counting loop, the same as for (i in nums.size - 1 downTo 0), without building a list.
Can fold or filter write the brute force more briefly?
nums.filterIndexed { j, _ -> j != i }.fold(1) { a, b -> a * b } is the same product, but it builds a new List<Int> of boxed values for every i. The plain loop over the IntArray avoids the boxing and the garbage.
Why not divide the total product by each element?
One zero makes the total 0, and total / nums[i] at the zero throws ArithmeticException: / by zero. The problem rules division out anyway, and the prefix and suffix passes need no zero handling.
FAQ for Rust
Will the products overflow an i32?
Not within the constraints: every prefix, suffix and answer fits in 32 bits. If one did not, this debug build would panic with attempt to multiply with overflow, while a release build wraps silently. checked_mul returns None instead, and i64 gives more room.
Why does (0..n - 1).rev() not underflow?
n is a usize, so n - 1 would panic for an empty vector. The constraints guarantee at least two elements, so it is at least 1; for an input that could be empty, (0..n.saturating_sub(1)).rev() is the safe spelling.
Why product::<i32>() with a turbofish?
Iterator::product is generic over its output type, so the compiler needs to know what to multiply into. Here the closure's result feeds collect into Vec<i32>, but naming the type on product makes the intent explicit and avoids an inference error if the code around it changes.
Can the running version iterate without indices?
Yes: for (a, &v) in answer.iter_mut().zip(&nums).rev() { *a *= suffix; suffix *= v; } does the second pass with no indexing. Both spellings are bounds-safe; the iterator form skips the bounds checks.
Why not divide the total product by each element?
One zero makes the total 0, and dividing by the zero element panics with attempt to divide by zero. The problem rules division out anyway, and the prefix and suffix passes need no zero handling.
FAQ for Swift
Can the products overflow an Int in Swift?
Swift Int is 64 bits here, far wider than the 32-bit products this problem allows. An overflow would not wrap: it traps at runtime with an arithmetic overflow error. The &* operator wraps on purpose, and multipliedReportingOverflow(by:) tells you whether it did.
Why stride(from: n - 2, through: 0, by: -1)?
A closed range 0...(n - 2) reversed works too, but stride with through: counts down directly and includes 0. With fewer than two elements a reversed 0...(n - 2) would trap on a bad range, while stride just runs zero times.
Is 1..<nums.count safe for the first pass?
It is because the constraints promise at least two elements. On an empty array 1..<0 traps with Range requires lowerBound <= upperBound; stride(from: 1, to: nums.count, by: 1) would run zero times instead.
Can reduce write the brute force more briefly?
nums.indices.map { i in nums.indices.filter { $0 != i }.reduce(1) { $0 * nums[$1] } } is the same O(n²) product, but it builds a filtered index array for every position. The plain loops allocate nothing per position.
Why not divide the total product by each element?
One zero makes the total 0, and dividing by the zero element traps with a division-by-zero error. The problem rules division out anyway, and the prefix and suffix passes need no zero handling.
FAQ for PHP
Can the products overflow a PHP int?
PHP int is 64 bits here, far wider than the 32-bit products this problem allows. If a product did pass PHP_INT_MAX, PHP would not wrap: it silently turns the result into a float, and the int return type would then reject it or lose precision.
Why build $answer in key order?
A PHP array is an ordered map, and json_encode writes it as a list only when its keys are 0, 1, 2… in insertion order. Both passes write the keys in that order the first time, so the result stays a list; assigning $answer[5] before $answer[4] would turn it into an object.
Is array_product a shortcut for the brute force?
array_product multiplies a whole array, so the brute force could be array_product(array_merge(array_slice($nums, 0, $i), array_slice($nums, $i + 1))). It is still O(n²), and it copies almost the whole array for every position.
Why $j !== $i and not !=?
Both are ints, so either works here. !== compares without type juggling, which is the safer habit in PHP when one side might be a string or null.
Why not divide the total product by each element?
One zero makes the total 0, and dividing by the zero element throws DivisionByZeroError in PHP 8. The problem rules division out anyway, and the prefix and suffix passes need no zero handling.
FAQ for Ruby
Do Ruby integers overflow here?
No. Ruby Integer grows past 64 bits on its own, so a product never wraps. The 32-bit bound in the constraints is for languages with fixed-width integers.
Why while loops in the brute force?
The large case does about four million multiplications. while runs them without a block call per step, which is noticeably faster in CRuby than each or times; for the O(n) versions the block forms cost nothing that matters.
Can inject replace the inner loop?
nums.each_with_index.inject(1) { |p, (v, j)| j == i ? p : p * v } gives the same product, and (nums[0...i] + nums[i + 1..]).inject(1, :*) is shorter still. Both stay O(n²) and allocate on every position, so they are slower than the loop.
Why Array.new(n, 1) and not Array.new(n) { 1 }?
With an immutable value like an Integer both give the same array; the shared-object pitfall of Array.new(n, value) only bites with mutable values such as strings or arrays. The block form is the habit for those.
Why not divide the total product by each element?
One zero makes the total 0, and total / nums[i] at the zero raises ZeroDivisionError. The problem rules division out anyway, and the prefix and suffix passes need no zero handling.
FAQ for Dart
Can the products overflow a Dart int?
On the Dart VM int is 64 bits, far wider than the 32-bit products this problem allows; past that it wraps silently. Compiled to JavaScript, int is a double and loses precision above 2⁵³ instead, so code meant for both should stay well inside the range.
Is List.filled(n, 1) growable?
No, it is fixed-length by default, which is all these passes need since every slot already exists. Pass growable: true if you want to add to it later.
Why List.generate for the brute force?
It allocates the list once at its final length and calls the closure for each index, so there is no add loop and no resizing. A for loop over List.filled(n, 0) is the same speed.
Can fold write the inner product more briefly?
nums.indexed.where((e) => e.$1 != i).fold(1, (p, e) => p * e.$2) gives the same product with records from Dart 3. It is still O(n²) and slower than the index loop, because it builds a record per element.
Why not divide the total product by each element?
One zero makes the total 0, and total ~/ nums[i] at the zero throws (with / you would get a double infinity instead). The problem rules division out anyway, and the prefix and suffix passes need no zero handling.
FAQ for Scala
What happens if a product overflows an Int?
Scala Int is the JVM 32-bit int, so multiplication wraps silently and an out-of-range product becomes a wrong number. The constraints keep every product in range; for wider inputs use Long, or Math.multiplyExact to throw instead.
Why is scanLeft one element longer than nums?
scanLeft(1) emits the start value first and then one running product per element, so it returns n + 1 values: the products of the first 0, 1, …, n elements. That is why left(i) excludes nums(i) and right(i + 1) excludes it from the other side.
Does scanLeft on an Array[Int] box the values?
The result is a primitive Array[Int], built through a ClassTag, so nothing boxed is kept. The generic method may box values while it runs the lambda, which is harmless for 2,000 elements; a while loop over the array avoids it in hot code.
Why a while loop inside the brute force?
A for over a Range compiles to foreach with a closure, which the JIT usually inlines but not always on the first, cold calls. The while loop runs the four million multiplications of the large case with no closure at all.
Why not divide the total product by each element?
One zero makes the total 0, and total / nums(i) at the zero throws ArithmeticException: / by zero. The problem rules division out anyway, and the prefix and suffix passes need no zero handling.
Keep going
Container With Most Water29 / 40 · Two pointers · MediumTry Product of Array Except Self in Python (Product of Array Except Self in Python), JavaScript (Product of Array Except Self in JavaScript), TypeScript (Product of Array Except Self in TypeScript), Java (Product of Array Except Self in Java), Go (Product of Array Except Self in Go), C# (Product of Array Except Self in C#), C++ (Product of Array Except Self in C++), C (Product of Array Except Self in C), Rust (Product of Array Except Self in Rust), Swift (Product of Array Except Self in Swift), PHP (Product of Array Except Self in PHP), Ruby (Product of Array Except Self in Ruby), Dart (Product of Array Except Self in Dart) or Scala (Product of Array Except Self in Scala) instead.