C++ O(n) 5 liner one pass solution, and O(n) count zeros solution


  • 1

    While "one passes" has cleaner code, "count zeros" is more efficient because it will end early if more than 1 zeros are found.

    One pass:

    vector<int> productExceptSelf(vector<int>& nums) {
            vector<int> ans(nums.size(), 1);
            
            // i is the position of left product pointer, lp is left product
            // j is the position of right product pointer, rp is right product
            for (int i = 0, j = nums.size() - 1, lp = 1, rp = 1; i < nums.size(); lp *= nums[i++], rp *= nums[j--]) {
                ans[i] *= lp, ans[j] *= rp;             // update ans elements
            }
            
            return ans;
    }
    

    Count zeros:

    vector<int> productExceptSelf(vector<int>& nums) {
            vector<int> ans(nums.size(), 0);
            int p = 1, zcnt = 0, zi = 0;                // p is the current product; zcnt is zero count; zi is zero element index
            for (int i = 0; i < nums.size(); i++) {
                if (nums[i] == 0) {
                    zi = i;
                    if (++zcnt > 1) { return ans; }     // if nums has more than 1 zeros, ans is all 0s
                } else {
                    p *= nums[i];
                }
            }
            
            if (zcnt == 1) {                            // if has one 0, the only non-zero element is on zi position
                ans[zi] = p;
            } else {                                    // meaning zcnt == 0
                for (int i = 0; i < nums.size(); i++) { ans[i] = p / nums[i]; }
            }
            return ans;
        }
    

Log in to reply
 

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