Clean c++ solution


  • 0
    C

    o(n) time complexity, o(n) space complexity.

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

    o(n) time complexity, with constant space.

       vector<int> productExceptSelf(vector<int>& nums) {
            int n = nums.size();
            vector<int> ans(n, 1);
            for(int i = 1; i < n; ++i) {
                ans[i] = ans[i - 1] * nums[i - 1];
            }
            int right = 1;
            for(int i = n - 1; i >= 0; --i) {
                ans[i] = ans[i] * right;
                right = right * nums[i];
            }
            return ans;
        }

Log in to reply
 

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