238. Product of Array Except Self

Problem Statement

Pattern: Pattern Prefix Array

---

Naive Solution

public int[] productExceptSelf(int[] nums) {
	int prod = 1, zero = 0;
	for (int num : nums)
		if (num == 0) zero++;
		else prod *= num;
	
	for (int i = 0; i < nums.length; i++) {
		switch (zero) {
			case 0: {
				nums[i] = divide(prod, nums[i]);
				break;
			}
			case 1: {
				if(nums[i] == 0) nums[i] = prod;
				else nums[i] = 0;
				break;
			}
			default: {
				nums[i] = 0;
				break;
			}
		}
	}
	return nums;
}
// count the no. of times b can be subtracted from a
private  int divide(int a, int b) {
	// get absolute a b
	int sign = ((a > 0 && b > 0) || (a < 0 && b < 0)) ? 1 : -1;
	a = Math.abs(a);
	b = Math.abs(b);
	
	// edge cases
	if(a == 0) return 0;
	if(b == 1 || b == 0) return a*sign;
	
	// init
	int B = b, pow = 1, count = 0;
	
	// get the highest power of b less than a
	while(a >= B*b) {
		pow++;
		B *= b;
	}
	
	while (a!=0) {
		// get correct pow
		while(a < B)
			B = (int) Math.pow(b, --pow);
		// divide
		a -= B;
		// update count
		count += Math.pow(b, pow-1);
		//System.out.printf("Pow: %d  Count: %d\n", pow, count);
	}
	return count * sign;
}

Notes

• Works perfectly, but TLE if Input is too large 🤷‍♂️
• Basically we diviide how division works, except we increment decrement denominator in powers of itself 3 -> 3, 9, 27, 81
  • First increment to find largest power
  • Then as we start dividing (substracting from a) we reduce power when needed.
  • We update how many times we had to to remove b from a in the variable count

Smart Solution

public int[] productExceptSelf(int[] nums) {
	// init result array
	int n = nums.length;
	int[] res = new int [n];
	
	// convert res into prefix product array
	res[0] = 1;
	for (int i = 1; i < n ; i++) {
		res[i] = res[i-1]*nums[i-1];
	}
	
	// instead of suffix array we use suffix variable suffixProd
	int suffixProd = 1;
	// last el has no suffix i = n-2
	for (int i = n-2; i >= 0; i--) {
		// get suffix product
		suffixProd *= nums[i+1];
		res[i] *= suffixProd;
	}
	return res;
}

Notes

• Simply put
  • create 2 arrays
    • prefix array : store the product of all the elements BEFORE i at prefix[i]
    • suffix array : store the product of all the elements AFTER i at suffix[i]
  • so nums[i] would simply be prefix[i] * suffix[i] - that is the product of all the numbers before and after i
  • since we can’t have 2 extra arrays for storing the prefix and suffix separately
    • we store the prefix in the result array res, and multiply it with the current suffix suffixProd when we are moving backwards!!
• res is the result array so it does not count as extra space. It is still constant space. If they had asked for an in-place solution, only then would we have been unable to create the result array