238. Product of Array Except Self - Leetcode Solution

LeetCode problem Solution code

đź’ˇ Step-by-Step Thought Process

Brute Force

  1. Understand the Problem:
    • For each element nums[i], we need to calculate the product of all other elements in the array, excluding nums[i].
    • The brute force approach would involve calculating the product for each element by looping through all other elements in the array.
  2. Loop Through All Elements:
    • We loop through each element in the array and calculate the product of all elements except the current one.
    • For each element nums[i], iterate over every other element in the array, multiplying the elements together (excluding the element at index i).
  3. Store the Result:
    • We store the result of the product for each element in a new array ans.
    • The product of the other elements for nums[i] is stored in ans[i].
  4. Return the Result:
    • After iterating through all the elements, return the ans array.

Code Solution (Brute Force)

# Brute Force Solution
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [0] * n

        for i in range(n):
            prod = 1
            for j in range(n):
                if i != j:
                    prod *= nums[j]
            ans[i] = prod
        
        return ans
        # Time: O(n^2)
        # Space: O(n)

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n, 0);

        for (int i = 0; i < n; i++) {
            int prod = 1;
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    prod *= nums[j];
                }
            }
            ans[i] = prod;
        }

        return ans;
    }
};
// Time: O(n^2)
// Space: O(n)
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];

        for (int i = 0; i < n; i++) {
            int prod = 1;
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    prod *= nums[j];
                }
            }
            ans[i] = prod;
        }

        return ans;
    }
}
// Time: O(n^2)
// Space: O(n)
function productExceptSelf(nums) {
    const n = nums.length;
    const ans = new Array(n).fill(0);

    for (let i = 0; i < n; i++) {
        let prod = 1;
        for (let j = 0; j < n; j++) {
            if (i !== j) {
                prod *= nums[j];
            }
        }
        ans[i] = prod;
    }

    return ans;
};
// Time: O(n^2)
// Space: O(n)

Why Brute Force is Inefficient

While the brute force approach works, it has a time complexity of O(n^2) because it loops through the array for each element and performs an inner loop for every other element. This can become very inefficient for large input sizes. The solution is slow for larger arrays, especially when n is large (e.g., n = 10^5).

Optimal Solution

  1. Avoid Nested Loops:
    • Instead of looping through the entire array for each element, we can break the problem into two parts: calculating the products to the left and right of each element.
    • We compute two arrays: one for the left product and one for the right product.
  2. Compute Left and Right Products:
    • First, iterate from left to right and compute the product of all elements to the left of the current element, storing the results in a left array.
    • Then, iterate from right to left and compute the product of all elements to the right of the current element, storing the results in a right array.
  3. Combine the Results:
    • The product for each element is the product of the corresponding left and right values. So, the final result for each element is ans[i] = left[i] * right[i].
  4. Return the Result:
    • After calculating the products for all elements, return the ans array.

Code Solution (Optimal)

# Optimal Solution
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        l_mult = 1
        r_mult = 1
        n = len(nums)
        l_arr = [0] * n
        r_arr = [0] * n
        
        for i in range(n): 
            j = -i -1
            l_arr[i] = l_mult
            r_arr[j] = r_mult
            l_mult *= nums[i]
            r_mult *= nums[j]

        return [l*r for l, r in zip(l_arr, r_arr)]

# Time Complexity: O(n)
# Space Complexity: O(n)

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n);
        
        int leftProduct = 1;
        int rightProduct = 1;
        
        // Calculate left products
        for (int i = 0; i < n; i++) {
            result[i] = leftProduct;
            leftProduct *= nums[i];
        }
        
        // Calculate right products and final result
        for (int i = n - 1; i >= 0; i--) {
            result[i] *= rightProduct;
            rightProduct *= nums[i];
        }
        
        return result;
    }
};

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        
        int leftProduct = 1;
        int rightProduct = 1;
        
        // Calculate left products
        for (int i = 0; i < n; i++) {
            result[i] = leftProduct;
            leftProduct *= nums[i];
        }
        
        // Calculate right products and final result
        for (int i = n - 1; i >= 0; i--) {
            result[i] *= rightProduct;
            rightProduct *= nums[i];
        }
        
        return result;
    }
}

function productExceptSelf(nums) {
    const n = nums.length;
    const result = new Array(n);
    
    let leftProduct = 1;
    let rightProduct = 1;
    
    // Calculate left products
    for (let i = 0; i < n; i++) {
        result[i] = leftProduct;
        leftProduct *= nums[i];
    }
    
    // Calculate right products and final result
    for (let i = n - 1; i >= 0; i--) {
        result[i] *= rightProduct;
        rightProduct *= nums[i];
    }
    
    return result;
}

Detailed Explanation

Understanding the Problem: Product of Array Except Self

The "Product of Array Except Self" problem asks us to build a new array such that each element at index i is the product of all the elements in the original array nums, except nums[i] itself. Importantly, we are not allowed to use division in this problem, and we must solve it with a time complexity of O(n).

For example, given the input [1, 2, 3, 4], the output should be [24, 12, 8, 6]. Here's why:

  • Element at index 0: 2 Ă— 3 Ă— 4 = 24
  • Element at index 1: 1 Ă— 3 Ă— 4 = 12
  • Element at index 2: 1 Ă— 2 Ă— 4 = 8
  • Element at index 3: 1 Ă— 2 Ă— 3 = 6

Why This Problem Matters

This problem is widely used in technical interviews and tests your ability to reason about array transformations, prefix and suffix accumulation, and in-place space optimization. It also teaches you how to compute results without violating constraints such as avoiding division or additional space usage.

Naive Approach: Brute Force

The brute force method involves creating a nested loop where for every element in the array, we iterate through the entire array again and multiply all elements except the one at index i. We store the result in a new output array.

While this approach is easy to understand, it has a time complexity of O(n²), which makes it inefficient for large arrays.

Optimal Solution: Prefix and Suffix Products

The optimal approach avoids division and nested loops by breaking the task into two linear passes:

  • In the first pass, we compute the prefix product for every element, which is the product of all the elements to the left of that index.
  • In the second pass, we compute the suffix product while traversing from the right, multiplying it with the prefix product stored earlier to get the final result.

The trick is to re-use the result array to avoid extra space: we fill it with left products first, and during the right pass, we keep a running right product that multiplies into the result.

Step-by-Step Example

Input: [1, 2, 3, 4]

Step 1: Compute prefix products
We initialize res = [1, _, _, _]

  • res[1] = res[0] * nums[0] = 1 * 1 = 1
  • res[2] = res[1] * nums[1] = 1 * 2 = 2
  • res[3] = res[2] * nums[2] = 2 * 3 = 6
Now res = [1, 1, 2, 6]

Step 2: Compute suffix products and combine
Initialize right = 1 and go from right to left:

  • res[3] = res[3] * right = 6 * 1 = 6, then right = right * nums[3] = 1 * 4 = 4
  • res[2] = res[2] * right = 2 * 4 = 8, then right = 4 * 3 = 12
  • res[1] = res[1] * right = 1 * 12 = 12, then right = 12 * 2 = 24
  • res[0] = res[0] * right = 1 * 24 = 24
Final result: [24, 12, 8, 6]

Time and Space Complexity

Time Complexity: O(n) — We perform two linear passes through the array.
Space Complexity: O(1) extra space if we exclude the result array, which is required by the output anyway. Otherwise, it is O(n) for the result.

Edge Cases

  • If the input array contains only one number, we return [1] since there are no other elements to multiply.
  • If the array contains zeros, those must be handled correctly: every position except the one with zero will yield zero, and the position with zero will contain the product of all other non-zero elements.
  • Negative numbers are supported as multiplication handles sign naturally.

Conclusion

The “Product of Array Except Self” problem is a perfect example of how clever precomputation techniques can drastically improve algorithm performance. By using prefix and suffix products, we avoid costly nested loops and deliver an elegant linear-time solution without using division. Understanding this pattern unlocks similar strategies for many other problems involving aggregate values with element exclusions.

NEW!Need help landing software roles? đź’ˇ