~/leetcode $ 238. Product-Of-Array-Except-Self

Note: skipped Encode and Decode question on Neetcode as that one is blocked on leetcode (need to subsribe)

The most obvious solution for this problem is to have the product of all numbers first and then just divide that by the current number to get the result value for that index. However, in the problem, they want you to do the question in O(n) time using no division operator.

I already knew the solution for this problem as I have done it before and in my opinion, it’s definitely not intuitive (idk if I would have gotten it on my first attempt)…

The basic idea is that we want to keep track of two values for each element, the product of the prefixes and the product of suffixes of the array (so product of all elements before that element and the product of all elements after that element in the array).

Why do we care about the prefix and suffixes? It’s because we can compute these dynamically in O(n) time. The key idea is that each value of the prefix (so each prefix product) is the previous prefix product times the current value (so we only have to compute one value at a time). This is the same for the suffix product as well (just backwards).

After we compute these values, the result[i] is equal to prefix[i] * suffix[i], which we can compute in O(n).

One small optimization we can do is to use result[i] as the prefix array and then keep track of the current suffix (which we dynamically update - this takes the role of the suffix array). Then, we only need space for the resulting vector/array. Resulting in O(1) space if we exclude the result vector.

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int length {static_cast<int>(nums.size())};
        vector<int> result {1};

        // first do the prefixes
        for (int i = 1; i < length; ++i) {
            result.push_back(result[i - 1] * nums[i - 1]);
        }

        // next do the suffixes
        int current_suffix {1};
        for (int i = length - 2; i > -1; --i) {
            current_suffix *= nums[i + 1];
            result[i] *= current_suffix;
        }

        return result;
    }
}

Time Complexity: O(n)

Space Complexity: O(1)

Time Taken: 10m 37s