C++ solution constant space with explanation


  • 3
    C

    This problem is everywhere. The basic idea is to compute 2 separate array: left and right. Left array value at position "i" the product of all element before "i" (1 if i = 0). Right array value at position "i" is the product of all element after "i" (1 if i = nums.size()-1). Each of these arrays can be computed in linear time.

    From there, we can modify the code to use either left or right array as the output, the other is just a constant.

    Here is the solution using both left and right array:

    class Solution {
    public:
        vector<int> productExceptSelf(vector<int>& nums) {
            vector<int> left(nums.size(), 1);
            vector<int> right(nums.size(), 1);
            for (int i = 1; i < nums.size(); i++) left[i] = left[i-1]*nums[i-1];
            for (int i = nums.size()-2; i >= 0; i--) right[i] = right[i+1]*nums[i+1];
            vector<int> res(nums.size(), 1);
            for (int i = 0; i < nums.size(); i++) res[i] = left[i]*right[i];
            return res;
        }
    };
    

    And here is the constant space version:

    class Solution {
    public:
        vector<int> productExceptSelf(vector<int>& nums) {
            // Constant space solution. Here we use right as output, left is just a number
            int left = 1;
            vector<int> right(nums.size(), 1);
            for (int i = nums.size()-2; i >= 0; i--) right[i] = right[i+1]*nums[i+1];
            for (int i = 0; i < nums.size(); i++) {
                right[i] = right[i]*left;
                left = left * nums[i];
            }
            return right;
        }
    };

  • 0
    E

    Same concept in one for loop:

        vector<int> result (nums.size(), 1);
        int left = 1, right = 1;
        for (int i = 1; i < nums.size(); i++){
            left *= nums[i - 1];
            result[i] *= left;
            right *= nums[nums.size() - i];
            result[nums.size() - i - 1] *= right;
        }
        return result;

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.