238. Product of Array Except Self (Medium)

https://leetcode.com/problems/product-of-array-except-self/

Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

Input:  [1,2,3,4]
Output: [24,12,8,6]

Note: Please solve it without division and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

Solutions

class Solution {

    // Calculate the left production from head to specific element.
    // Calculate the right production from tail to specific element.

    public int[] productExceptSelf(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }

        int len = nums.length;
        int[] ans = new int[len];
        ans[0] = 1;

        for (int i = 1; i < len; i++) {

            // Update ans[i] to assign the production of values before i to it.
            ans[i] = ans[i - 1] * nums[i - 1];
        }

        // ans[len-1] has already sorted out.

        // right production after i
        int rp = 1;

        for (int i = len - 2; i >= 0; i--) {
            // right production after i
            rp = rp * nums[i + 1];

            // Since ans[i] already contains the production of values before i, we are
            // expected to multiply the production of right side elements so that we can
            // gain the desired production.
            ans[i] = ans[i] * rp;
        }

        return ans;
    }
}

2.

class Solution {

    // Problem requires solution without division, but this is also a good solution.

    // Take care of situations that elements contain zeros

    public int[] productExceptSelf(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }

        int len = nums.length;

        int[] ans = new int[len];
        Arrays.fill(ans, 0);

        int fullProd = 1;
        int zeroNum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                zeroNum++;
                continue;
            }

            fullProd *= nums[i];
        }

        // 1. >= 2 zeros, all the production should be 0

        if (zeroNum >= 2) {
            return ans;
        }

        // 2. 1 zero, all the production should be 0 except ith element which is of 0 value

        if (zeroNum == 1) {
            for (int i = 0; i < len; i++) {
                if (nums[i] != 0) {
                    continue;
                }

                ans[i] = fullProd;

                return ans;
            }
        }

        // 3. 0 zero, normal situation

        for (int i = 0; i < nums.length; i++) {
            ans[i] = fullProd / nums[i];
        }

        return ans;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2020-03-21 17:08:43

results matching ""

    No results matching ""