Interview Classic 150 Questions P238 Product of Array Except Self

---

Timeline

Timeline

2025-10-05

init

Application of Prefix Sum

---

Problem:

P238 Product of Array Except Self

https://leetcode.cn/problems/product-of-array-except-self/description/?envType=study-plan-v2&envId=top-interview-150

Prefix Sum is one of the most common and practical “preprocessing techniques” in algorithms. It allows you to quickly find the sum of any interval, greatly accelerating calculations.

Given an array:

$$nums = [a₁, a₂, a₃, ..., aₙ]$$

We define its prefix sum array prefix as: (i.e., the sum of the first i numbers)

$$prefix[i] = a₁ + a₂ + ... + aᵢ$$

And we agree: prefix[0] = 0

This problem is multiplication, so prefix[0] = 1;

#include <vector>
using std::vector;

class Solution {
public:
  vector<int> productExceptSelf(vector<int> &nums) {
    int i;
    // n>=2
    int n = nums.size();

    vector<int> prefix(n);
    vector<int> suffix(n);
    vector<int> result(n);
    prefix[0] = 1;

    for (i = 1; i < n; i++) {
      prefix[i] = nums[i - 1] * prefix[i - 1];
    }
    suffix[n - 1] = 1;

    for (i = n - 2; i >= 0; i--) {
      suffix[i] = nums[i + 1] * suffix[i + 1];
    }
    for (i = 0; i < n; i++) {
      result[i] = prefix[i] * suffix[i];
    }
    return result;
  }
};

leetcode hot 100 rewrite

#include <vector>
using std::vector;

class Solution {
    public:
        vector<int> productExceptSelf(vector<int> &nums)
        {
                int i, n = nums.size();
                vector<int> prefix_multiply(n);
                vector<int> suffix_multiply(n);
                vector<int> answer(n);

                prefix_multiply[0] = 1;
                for (i = 1; i < n; i++) {
                        prefix_multiply[i] = prefix_multiply[i - 1] * nums[i - 1];
                }

                suffix_multiply[n - 1] = 1;
                for (i = n - 2; i >= 0; i--) {
                        suffix_multiply[i] = suffix_multiply[i + 1] * nums[i + 1];
                }

                for (i = 0; i < n; i++) {
                        answer[i] = prefix_multiply[i] * suffix_multiply[i];
                }

                return answer;
        }
};