1
\$\begingroup\$

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.)

My solution

public class ProductExceptSelf {
    /**
     * Approach 1:- Find the left[i] at i containing all the left multiplication. Do same with right[i]
     */
    public int[] productExceptSelf(int[] nums) {

        int size = nums.length;

        int[] output = new int[size];
        int[] left = new int[size];
        int[] right = new int[size];

        int temp = 1;
        // Start filling up left array
        for (int i = 0; i < size; i++) {
            left[i] = temp;
            temp = temp * nums[i];
        }

        // Again set the temp to 1
        temp = 1;

        // Start filling up right array
        for (int i = size - 1; i >= 0; i--) {
            right[i] = temp;
            temp = temp * nums[i];
        }

        // Final traversal and return sum array.
        for (int i = 0; i < size; i++) {
            output[i] = left[i] * right[i];
        }

        return output;
    }
}

Please help me to improve Auxilary space, code readibility and any best practice if I am missing.

\$\endgroup\$
1
\$\begingroup\$

Every time you feel obliged to put a comment like

    // Start filling up left array

you really deal with a potentially important algorithm, which deserves a name, and a method of its own. In this case the algorithm is known as partial product. Consider factoring it out, and see the comments disappear.

Ditto for the second loop.

Regarding space complexity,

  • You don't need left: accumulate the partial products directly into output.

  • You don't need right as well: instead of accumulating the partial products, use it immediately:

        temp = 1;
    
        for (int i = size - 1; i >= 0; i--) {
            output[i] *= temp;
            temp = temp * nums[i];
        }
    
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.