C++ solution O(2N) time and O(1) space with explanation


  • 0
    A
    class Solution {
    public:
        vector<int> productExceptSelf(vector<int>& nums) {
            int size = nums.size();
            vector<int> result(size, 1);
            // upper triangle
            for (int i = 1; i < size; i++)
            {
                result[i] = nums[i - 1] * result[i - 1]; 
            }
            
            int product = 1;
            // lower triangle
            for (int i = size - 2; i >= 0; i--)
            {
                product *= nums[i + 1];
                result[i] *= product; 
            }
            return result;
        }
    };
    
    1. Imagine calculating the product of each column of a matrix without the diagonal element
      enter image description here
    1. Calculate upper triangle and lower triangle to get the answer

  • 0

    Calculate upper triangle and lower triangle to get the answer

    Those triangles are Θ(n2) large...


  • 0
    A

    Yes, but you only have to use a for loop to calculate all the elements.
    For example: (upper triangle)
    If numbers array nums = { 1, 2, 3, 4, 5 }

    1. Declare a vector v = { 1, 1, 1, 1, 1 }
    2. for i = 1 to 4
    3. v[i] = v[i - 1] * nums[i - 1]
      v[1] = v[0] * nums[0], v = { 1, 1, 1, 1, 1 }
      v[2] = v[1] * nums[1], v = { 1, 1, 2, 1, 1 }
      v[3] = v[2] * nums[2], v = { 1, 1, 2, 6, 1 }
      v[4] = v[3] * nums[3], v = { 1, 1, 2, 6, 24 }
    4. Already get the upper triangle result by O(N) time

  • 0

    What is that v? The top row of the triangle? The rightmost column? What about the rest of the triangle? And where is the matrix? I only see your nums vector.

    I really don't think your triangle analogy is working unless you explain how it's a special case and what you actually mean.


  • 0
    A

    The matrix is just for explanation.
    If the numbers vector is { a0, a1, a2 }, the result vector is
    v[0] = 1 * a1 * a2
    v[1] = a0 * 1 * a2
    v[2] = a0 * a1 * 1
    I can declare an integer temp to store the result.
    For upper triangle,

    1. temp = 1
    2. temp = temp * a1 = a1
    3. temp = temp * a2 = a1 * a2
      For lower triangle,
    4. temp = 1
    5. temp = temp * a1 = a1
    6. temp = temp * a0 = a0 * a1

Log in to reply
 

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