algoadvance

Leetcode 238. Product of Array Except Self

Problem Statement:

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

You should solve it without using division and in O(n).

Clarifying Questions:

  1. What should be the behavior if the array contains zeros?
    • The problem can handle zeros, as the product except self for positions where zeros are present will be carefully computed without causing division by zero errors.
  2. Can the input contain negative numbers?
    • Yes, the input can contain negative numbers as per the problem’s constraints.
  3. What is the size constraint of the array?
    • The array will have at least two elements.

Strategy:

To achieve the desired output without using division and ensuring that the time complexity remains O(n), we can follow these steps:

  1. Create two arrays, left and right, of length n.
    • left[i] will contain the product of all elements to the left of index i.
    • right[i] will contain the product of all elements to the right of index i.
  2. Initialize the left array:
    • Set left[0] to 1 because there are no elements to the left of the first element.
    • Iterate through the array from left to right to fill the left array.
  3. Initialize the right array:
    • Set right[n-1] to 1 because there are no elements to the right of the last element.
    • Iterate through the array from right to left to fill the right array.
  4. Compute the result:
    • For each i, the result at i will be left[i] * right[i].

Code:

#include <vector>
using namespace std;

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> left(n, 1);
    vector<int> right(n, 1);
    vector<int> result(n);

    // Fill in the left array
    for (int i = 1; i < n; ++i) {
        left[i] = left[i - 1] * nums[i - 1];
    }

    // Fill in the right array
    for (int i = n - 2; i >= 0; --i) {
        right[i] = right[i + 1] * nums[i + 1];
    }

    // Fill in the result array
    for (int i = 0; i < n; ++i) {
        result[i] = left[i] * right[i];
    }

    return result;
}

Time Complexity:

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI