\

Product Of Array Except Self

Difficulty: N/A | Solved: December 20, 2025

Problem

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

Input: nums = [1,2,3,4] Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0]

  • 🍅 (pomodoro::WORK) (duration:: 30m) (begin:: 2025-12-08 17:37) - (end:: 2025-12-08 18:18)

Brainstorming

okay the brute force solution is iterate for each element using for loop inside that you run another for loop for all the elements except i till end and then just multiply prefix_product

nums = [1,2,3,4]
prefix_product = []
for i in range(len(nums)):
	curr_prefix_product = 1
	for j in range(i+1, len(nums)):
		curr_prefix_product = curr_prefix_product * nums[j]
	prefix_product.append(curr_prefix_product)

print(prefix_product)

this is in correct since it does not take into account elements that are behind i

using python trickery

import math 

nums = [-1,1,0,-3,3]
prefix_product_array = []
for i in range(len(nums)):
	prefix_product = math.prod(nums[0:i])
	suffix_product = math.prod(nums[i+1:])
	curr_product = prefix_product * suffix_product
	prefix_product_array.append(curr_product)

print(prefix_product_array)

but this is not O(N) i believe

can we do something with 3 pointers? like what we do in dutch national flag problem , at any given point we create partitions like we have done in the above example one is what is from 0 till i the other could be from i+1 till len(nums)

the twist could be we somehow calculate the prefix product till i-1 and save it but then how will we look ahead from i + 1

  • 🍅 (pomodoro::WORK) (duration:: 20m) (begin:: 2025-12-08 18:19) - (end:: 2025-12-08 18:39)

Optimal Solution

You are off to a phenomenal start. Your analysis is spot on.

  1. Brute-Force: You correctly identified the O(N^2) brute-force approach of iterating for each element and then iterating again to calculate the product.

  2. “Python Trickery” / The Core Insight: Your second attempt is brilliant because it’s not just a trick; it reveals the fundamental structure of the problem.

    curr_product = prefix_product * suffix_product

    This is the key. For any index i, the answer is (product of all numbers to the left of i) * (product of all numbers to the right of i). Your math.prod solution implements this directly.

  3. Correctly Analyzing the “Trick”: You are also correct that this is not O(N). Each call to math.prod on a slice of length k takes O(k) time. Since you do this inside a loop of length N, the complexity is again O(N^2).

  4. Identifying the Next Step:

    “…we somehow calculate the prefix product till i-1 and save it but then how will we look ahead from i + 1”

    This is the exact question that leads to the optimal O(N) solution. You can’t solve the “look ahead” part in the same pass as the “look behind” part… unless you use multiple passes.

Let’s build on your insight. We need two pieces of information for each index i:

  1. The product of everything to the left (prefix_products[i]).
  2. The product of everything to the right (suffix_products[i]).

Question 1: The Two-Pass Approach

Imagine you have two new, empty arrays: prefix_products and suffix_products, both the same size as nums.

  • How could you fill the prefix_products array in a single O(N) pass from left to right? (Hint: How does prefix_products[i] relate to prefix_products[i-1]?)
  • How could you fill the suffix_products array in a single O(N) pass from right to left?
  • Once you have these two arrays, how do you combine them to get the final result in a third O(N) pass?

This approach uses O(N) space for the two new arrays. It’s a huge step towards the final optimal solution.

so we essentially will have 3 passes pass 1 to fill the prefix_products it can be done as follows

nums = [1,2,3,4]
prefix_products = [1]

for i in range(1,len(nums)):
	curr_prefix_prod = nums[i-1] * prefix_products[i-1]
	prefix_products.append(curr_prefix_prod)

print(prefix_products)

i am assuming its including current i if its not then what is the prefix product for nums[0]

Your logic for filling prefix_products is perfect! You’ve correctly identified the relationship: prefix[i] = nums[i] * prefix[i-1].

Now, let’s address your excellent question:

“i am assuming its including current i if its not then what is the prefix product for nums”

This is the crucial detail. For the final answer at output[i], we need the product of everything except the element at i. This means:

  • output[i] = (product of elements 0 to i-1) * (product of elements i+1 to end)

So, prefix_products[i] should store the product of everything before i. And suffix_products[i] should store the product of everything after i.

Let’s redefine our goal for the two arrays:

  • prefix_products[i] = product of nums[0] * ... * nums[i-1]
  • suffix_products[i] = product of nums[i+1] * ... * nums[n-1]

Question 1: What are the “identity” values?

  • What is the prefix product for the first element (prefix_products[0])? There are no elements before it. What is the product of no numbers? In multiplication, the identity value is 1.
  • Similarly, what is the suffix product for the last element (suffix_products[n-1])? It should also be 1.

(Prompt): With this new definition, modify your Pass 1 code.

  1. How would you initialize your prefix_products array?
  2. How does the loop change to calculate the product of everything before the current i?

Then, describe how you would do Pass 2 to fill the suffix_products array using the same logic but from the other direction.

Now for the suffix

nums = [1,2,3,4]
suffix_products = [1]*len(nums)

for i in range(len(nums)-2, -1,-1):
	curr_suffix_prod = nums[i+1] * suffix_products[i+1]
	suffix_products.append(curr_suffix_prod)

print(suffix_products)

You’ve got the direction and the core logic exactly right! This is great. Just a small Python implementation detail is tripping you up.

The Logic (which is correct):

  • Initialize an array of 1s.
  • Loop from right-to-left (your range(len(nums)-2, -1, -1) is perfect for this).
  • The formula nums[i+1] * suffix_products[i+1] correctly calculates the suffix product for position i.

The Python Detail: The line suffix_products.append(curr_suffix_prod) always adds an element to the end of the list. Since you’re iterating from right to left, you’re calculating the values for suffix_products[2], then suffix_products[1], etc., but you’re appending them to the end of the list.

You don’t want to append. You want to assign the calculated value to the correct index.

(Prompt): Change the append line to correctly assign the curr_suffix_prod to its proper place in the suffix_products array.

nums = [1,2,3,4]
suffix_products = [1]*len(nums)

for i in range(len(nums)-2, -1,-1):
	curr_suffix_prod = nums[i+1] * suffix_products[i+1]
	suffix_products[i]= curr_suffix_prod

print(suffix_products)

final pass we iterate from 1st element till the len(nums) at each i we look at prefix[i] that already contains product of everything to the left of i and multiply it to suffix[i] which contains product of everything to the right of i and we combines them

nums = [1,2,3,4]

suffix_products = [1]*len(nums)
prefix_products = [1]

for i in range(1,len(nums)):
	curr_prefix_prod = nums[i-1] * prefix_products[i-1]
	prefix_products.append(curr_prefix_prod)

for i in range(len(nums)-2, -1,-1):
	curr_suffix_prod = nums[i+1] * suffix_products[i+1]
	suffix_products[i]= curr_suffix_prod
	
product_of_array_except_self = []

for i in range(len(nums)):
	curr_product = prefix_products[i] * suffix_products[i]
	product_of_array_except_self.append(curr_product)

print(product_of_array_except_self)

O(1) space optimal

That is 100% correct. You have perfectly assembled all three passes into a working O(N) time and O(N) space solution.

Your final loop correctly calculates result[i] = prefix_products[i] * suffix_products[i].

Let’s trace the final result to confirm:

  • prefix_products = [1, 1, 2, 6]
  • suffix_products = [24, 12, 4, 1]
  • result[0] = 1 * 24 = 24 (Correct: 234)
  • result[1] = 1 * 12 = 12 (Correct: 134)
  • result[2] = 2 * 4 = 8 (Correct: 124)
  • result[3] = 6 * 1 = 6 (Correct: 123)

You’ve nailed the O(N) space solution. This is a huge step up from the brute-force method.

Now for the final, senior-level leap.

Question (The O(1) space optimization): Look at your three passes.

  1. Pass 1 (left-to-right) builds prefix_products.
  2. Pass 2 (right-to-left) builds suffix_products.
  3. Pass 3 (left-to-right) combines them.

Do you really need to store the entire suffix_products array?

Imagine you have already built the final result array using just the prefix products. So, result currently holds [1, 1, 2, 6].

Now, can you iterate from right-to-left, calculating the suffix product on the fly and multiplying it into your result array as you go?

  • You would need one variable to keep track of the “suffix product so far” as you iterate from the right.
  • For i = len-1, the suffix product is 1. result[len-1] gets multiplied by 1.
  • For i = len-2, the suffix product is nums[len-1]. result[len-2] gets multiplied by this.
  • And so on…

(Prompt): Try to combine Pass 2 and Pass 3 into a single, right-to-left pass that modifies the result array in place, using only one extra variable to track the suffix product. This will get you to the O(1) space solution (since the result array doesn’t count as extra space).

  • 🍅 (pomodoro::WORK) (duration:: 30m) (begin:: 2025-12-08 18:40) - (end:: 2025-12-08 19:10)