Classic Interview 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 speeding up 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 involves 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;
        }
};