Associative Array + Preprocessing


  • 0
    N
    1. DS: Associative Array , Technique: Preprocessing
      Time Complexity: O(n)
      Space Complexity: O(N)
        vector<int> productExceptSelf(vector<int>& nums) {
            int len = nums.size(), product = 1;
            vector<int> prefix, suffix(len), output(len);
            // vector<int> prefix and vector<int> prefx(len);
            for (int i = 0; i < len; i++) {
                product *= nums[i];
                prefix.push_back(product);
            }
            
            product = 1;
            for (int i = len - 1; i >= 0; i--) {
                product *= nums[i];
                suffix[i] = product;
            }
            
            output[0] = suffix[1];
            output[len - 1] = prefix[len - 2];
            
            for (int i = 1; i < len - 1; i++) {
                output[i] = prefix[i - 1] * suffix[i + 1];
            }
            
            return output;
        }
    

    This is a straightforward approach, we can easily see that output[i] = prefix[i -1] * suffix[i + 1] ( 0 < i < last)

    Note 1: Declare vector<int> prefix(len) and prefix.push_back()

    2.Optimization
    Follow-up requires Space Complexity should be O(1), so we should improve from S:O(N) to S: O(1)
    This type of Improvement happens a lot in DP , etc fibonacci.It is still based on DP technique.we can use variables to bookkeeping instead of array . However in this problem, we can't. So we may need other techniques
    Another optimization is to focus on time complexity O(1). We can do two scans on output array . That means we don't have to calculate a correct value of output[i] immdiately when we first get to that index, which is what we do in the first approach. However i was not able to get an clever observation . Below links give

    https://discuss.leetcode.com/topic/18864/simple-java-solution-in-o-n-without-extra-space

    One reason I could not figure it out is because I forgot one important property of product.: 1 times N = N;

    Note: time complexity O(1), we can run two scans on a set.


Log in to reply
 

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