238. Product of Array Except Self

📝 Problem Details

• Title: 238. Product of Array Except Self
• Link: https://leetcode.com/problems/product-of-array-except-self/
• Difficulty: Medium
• Tags/Categories: Prefix-Sum Arrays

input array nums return an array answer such that answer[i] is equal to the product of all elements of nums except nums[i]

💭What Were My Initial Thoughts?

- brute force would be to iterate over the array for each index
	- multiplying all other numbers except itself 
	- this would be inefficient O(N^2)

💡 Explanation of Solution

Prefix and Postfix approach (two-pass)
We can solve in O(n) time using prefix and postfix multiplications

1. init a results array
	- result[i] will initially store the prefix product (product of all elements before index i)

2. compute prefix products
	- traverse left to right
	- store the cumulative product of elements before i in result[i]

3. compute postfix products and multiply 
	- traverse right to left 
	- multiply each result[i] by the cumulative product of elements after i

Example Walkthrough: nums = [1, 2, 3, 4]

first pass through: prefix

result = [1, 1, 1, 1] (initialize)

i = 0 → result[0] = 1
i = 1 → result[1] = 1 * nums[0] = 1 * 1 = 1
i = 2 → result[2] = 1 * nums[1] = 1 * 2 = 2
i = 3 → result[3] = 2 * nums[2] = 2 * 3 = 6

result after prefix pass: [1, 1, 2, 6]

second pass through: postfix

postfix = 1

i = 3 → result[3] = 6 * 1 = 6
        postfix *= nums[3] → postfix = 4

i = 2 → result[2] = 2 * 4 = 8
        postfix *= nums[2] → postfix = 12

i = 1 → result[1] = 1 * 12 = 12
        postfix *= nums[1] → postfix = 24

i = 0 → result[0] = 1 * 24 = 24

final result: [24, 12, 8, 6]

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1) since result is required for the return value its technically constant and doesnt require any *additional* space

💻 Implementation of Solution

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n,1);
        // we can assume that our results vector will have the same number of elements and will have a minimum value of 1
 
        int prefix = 1; // initially set to 1 to assist elements at the boundary
        for(int i=0; i < n; i++) {
            result[i] = prefix;
            prefix = prefix * nums[i];
        }
 
        int postfix = 1;
        for(int i=n-1; i >= 0; i--) {
            result[i] = result[i] * postfix;
            postfix = postfix * nums[i];
        }
 
        return result;
    }
};