Easy Guide to Solving Product of Array Except Self on Leetcode

We have been asked to return an integer array such that it has elements in respective indices of a given integer array which are products of all the other elements except itself.

I.e., the array to be returned (say) output has elements such that, output[i] is the product of all elements in the given array nums, except nums[i].

The given constraints are:

• The given array has at least 2 elements and a maximum of 105.

• The individual element in the array can be in a range of -30 to 30 integers.

Let's try the method that would've probably come to your mind after reading the question (at least, this is what I got and am getting for any question I read in LeetCode for a while).

---

Nested Loops

vector<int> productExceptSelf(vector<int>& nums) {
  int len = nums.size();
  vector<int> result; // DO NOT Specify Size while DECLARING.
// It would create a array of size len with some junk or
// null values depending on the compiler. This would create a problem
// when using the push_back() function, as it will increase size and add the new element.
  int product;
  for (int i = 0; i < len; ++i) {
    product = 1;
    for (int j = 0; j< len; ++j) {
      if (i != j) {
        product *= nums[j];
      }
    }
    result.push_back(product);
  }
  return result;
}

Time Complexity: O(n2)

Cuz there is a loop inside a loop.

---

Dynamic Programming Approach

vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> o(n);
        o[0] = 1;
        for (int i = 1; i < n; ++i) {
            o[i] = o[i-1] * nums[i-1]; // multiplies the previous left
// values with the previous value. like if in [1, 2, 3, 4] we are in 3,
// this loop multiplies (1*2) * 3. where (1*2) is already present.
        }
        int right = 1;
        for (int i = n-1; i >=0; --i) { // this loop does a similar process
// as the previous loop, but the right var multiplies elements to the right
// of element [i].
            o[i] *= right;
            right *= nums[i];
        }

        return o;

Time Complexity: O(n)

This is like the time function adds n and n for each loop separately, hence the time complexity just takes n, ignoring the coefficient.

Please correct any mistakes that you encounter. I am and will still keep learning.

I did not mention the third method which does a good job with time complexity, but not so with space complexity. I did not add it here because it felt redundant as it was similar in approach to the second method. [2 loops here, 3 loops there]