Coding Interview Questions | Product of Array Except Self

December 21st, 2023

Introduction:

This summary will talk about my solution to the product of array except self problem as seen on leetcode here.

Solution:

function productExceptSelf(nums: number[]): number[] {
  const n = nums.length;
  const prefix: number[] = new Array(n);
  const suffix: number[] = new Array(n);
  const answer: number[] = new Array(n);

  // Initialize prefix array
  prefix[0] = 1;
  for (let i = 1; i < n; i++) {
    prefix[i] = prefix[i - 1] * nums[i - 1];
  }

  // Initialize suffix array
  suffix[n - 1] = 1;
  for (let i = n - 2; i >= 0; i--) {
    suffix[i] = suffix[i + 1] * nums[i + 1];
  }

  // Calculate the final result array
  for (let i = 0; i < n; i++) {
    answer[i] = prefix[i] * suffix[i];
  }

  return answer;
}

Summary:

• Utilizing two auxiliary arrays, prefix and suffix, the products of elements on the left and right of each index in nums are obtained.
• Calculate prefix by traversing nums from left to right, and suffix by traversing from right to left.
• The final result, answer, is obtained by multiplying corresponding elements from prefix and suffix.
• The algorithm achieves linear time complexity O(n).
• The algorithm uses O(n) space complexity, where additional space is used for the prefix and suffix arrays.
• The division operation is avoided and adheres to the constraint of O(n) time complexity.