Product array puzzle

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

For each index i, product of all elements except nums[i]. No division, O(1) extra space.

Algorithm

1Left pass: result[i] = product of all elements left of i.
2Right pass: multiply result[i] by running product of all elements right of i.

Common Pitfalls

•Same as LC 238. Two passes. result[0]=1 (no elements left), result[n-1]=1 (no elements right).

Product array puzzle.java

Java

// Approach: Two passes: left product array, right product array. Result[i] = left[i] * right[i].
// Time: O(n) Space: O(n)
import java.util.*;

class Solution {
    public static long[] productExceptSelf(int nums[]) {
        int n = nums.length;

        long[] ans = new long[n];

        long p = 1;
        int zeroCnt = 0;

        for (int num : nums) {
            if (zeroCnt > 1) {
                Arrays.fill(ans, 0);
                return ans;
            }

            if (num == 0)
                zeroCnt++;
            else
                p *= num;
        }

        if (zeroCnt > 1) {
            Arrays.fill(ans, 0);
            return ans;
        }

        if (zeroCnt == 1) {
            Arrays.fill(ans, 0);
            for (int i = 0; i < n; i++) {
                if (nums[i] == 0)
                    ans[i] = p;
            }
        } else {
            for (int i = 0; i < n; i++) {
                ans[i] = p / nums[i];
            }
        }

        return ans;
    }
}

// Another version
class Solution {
    public static int[] productExceptSelf(int nums[]) {
        int n = nums.length;

        int[] ans = new int[n];

        int p = 1;
        int zeroCnt = 0;

        for (int num : nums) {
            if (zeroCnt > 1) {
                Arrays.fill(ans, 0);
                return ans;
            }

            if (num == 0)
                zeroCnt++;
            else
                p *= num;
        }

        if (zeroCnt > 1) {
            Arrays.fill(ans, 0);
            return ans;
        }

        if (zeroCnt == 1) {
            Arrays.fill(ans, 0);
            for (int i = 0; i < n; i++) {
                if (nums[i] == 0)
                    ans[i] = p;
            }
        } else {
            for (int i = 0; i < n; i++)
                ans[i] = p / nums[i];
        }

        return ans;
    }
}

Was this solution helpful?