Solution by ccwei


  • 3
    C

    Approach #0

    If there's no restriction on solving it without division, a way to solve the problem is to compute a product of all nums[i] as totalProduct, and then output[i] = totalProduct/nums[i] to exclude nums[i]. However, we need to be careful when nums[i] == 0, also the problem explicitly prohibits the use of division, so this solution doesn't solve the problem according to the problem description.


    Approach #1 Brute Force [Time Limit Exceeded]

    The naive approach is to simply follow what the problem asks as to do. For all index i, loop through the entire array to calculate the product and only skips index i for that iteration to exclude self.

    Approach #1 Naive approach [Time Limit Exceeded]

    C#

    public class Solution {
        public int[] ProductExceptSelf(int[] nums) {
            int[] result = new int[nums.Length];
            
            for(int i = 0; i < nums.Length; i++) {
                int product = 1;
                for(int j = 0; j < nums.Length; j++) {
                    if(j != i) { // exclude self
                        product *= nums[j];
                    }
                }
                result[i] = product;
            }
            
            return result;
        }
    }
    

    Complexity Analysis

    • Time complexity : $$O(n^2)$$. There are two loops nested and each with $$O(n)$$ running time

    • Space complexity : $$O(1)$$. We only use extra constant space for product variable.


    Approach #2 Two product arrays [Accepted]

    Algorithm

    We can keep two arrays, one is productFromLeft where productFromLeft[i] contains the product of nums[0...i], i.e. productFromLeft[i] = nums[0] * nums[1] * nums[2] * .... nums[i]. Another one is similar but contains all the products from the right hand side, where productFromRight[i] contains the product of nums[i...n-1], i.e. productFromRight[i] = nums[i] * nums[i + 1] * nums[i + 2] * .... nums[n - 1].

    Given array of productFromLeft and productFromRight, we can calucate output[i] = productFromLeft[i - 1] * productFromRight[i + 1], which is nums[0] * nums[1] * ... nums[i - 1] * nums[i + 1] * nums[i + 2] * ... nums[n - 1].

    0_1502766926443_238_approach2.png

    C#

    public class Solution {
        public int[] ProductExceptSelf(int[] nums) {
            int n = nums.Length;
    
            // Process edge cases first
            if(n <= 1) {
                return new int[0];
            }
            
            int[] productFromLeft = new int[nums.Length];
            int[] productFromRight = new int[nums.Length];
            
            // Populate productFromLeft, O(n) time, O(n) space
            int product = 1;
            for(int i = 0; i < n; i++) {
                product *= nums[i];
                productFromLeft[i] = product;
            }
            
            // Populate productFromRight, O(n) time, O(n) space
            product = 1;
            for(int i = n - 1; i >= 0; i--) {
                product *= nums[i];
                productFromRight[i] = product;
            }
            
            int[] output = new int[n];
            
            // Special case boundary indices to avoid index out of range issues
            output[0] = productFromRight[1];
            output[n - 1] = productFromLeft[n - 2];
    
            // Populate all other output[i]
            for(int i = 1; i < n - 1; i++) {
                output[i] = productFromLeft[i - 1] * productFromRight[i + 1];
            }
            
            return output;
        }
    }
    

    Complexity Analysis

    • Time complexity : $$O(3n) = O(n)$$.

    • Space complexity : $$O(2n) = O(n)$$.


    Approach #3 Two passes use output array as temp memory [Accepted]

    Algorithm

    To further optimize the space complexity, as the hint suggested, we can use the output array as the temporary storage for interim calculation result. Similar idea of Approach#2, we are going to scan the input array twice, first time from the left and second time from the right.

    The first time we scan it from left, we are going to calculate output[i] as product of nums[0..i - 1], i.e. output[i] = nums[0] * nums[1] * ... nums[i - 1], where output[0] = 1. As we scan it from the left, we can easily calculate output[i] = output[i - 1] * nums[i - 1] because output[i - 1] = nums[0] * nums[1] * ... nums[i - 2].

    The second pass we scan it from right, and we are trying to calculate output[i] as the final result, which means output[i] = nums[0] * nums[1] * ... nums[i - 1] * nums[i + 1] * nums[i + 2] * ... nums[n - 1], in the first pass, we already calculate output[i] = nums[0] * nums[1] * ... nums[i - 1], so we only need to focus on how to calculate nums[i + 1] * nums[i + 2] * ... nums[n - 1]. We can acheive this by keeping an product variable similar to the second pass in Approach #2 to keep track of the "product from right", i.e. when index = i, product = nums[i + 1] * nums[i + 2] * ... nums[n - 1]. So when the loop arrives at index i, we can calulcate output[i] = output[i] * product to get the final result for index i.
    0_1502767571125_238_approach3.png

    C#

    public class Solution {
        public int[] ProductExceptSelf(int[] nums) {
            int n = nums.Length;
            int[] output = new int[n];
            
            // First pass, calculate output[i] = nums[0] * nums[1] * ... nums[i - 1]
            output[0] = 1;
            for (int i = 1; i < n; i++) {
                output[i] = output[i - 1] * nums[i - 1];
            }
    
            // Second pass, calculate output[i] = nums[0] * nums[1] * ... nums[i - 1] * nums[i + 1] * nums[i + 2] * ... nums[n - 1]
            int product = 1;  // Special case when i = n - 1, product = 1 since it's the right most element.
            for (int i = n - 1; i >= 0; i--) {
                output[i] *= product; // product = nums[i + 1] * nums[i + 2] * ... nums[n - 1]
                product *= nums[i];
            }
            return output;
        }
    }
    

    Complexity Analysis

    • Time complexity : $$O(2n) = O(n)$$.

    • Space complexity : $$O(1)$$.


Log in to reply
 

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