Products excluding each element of the array

Question

Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.

For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].

Is there a better solution for this problem?

Note: Division is not allowed.

public class DailyCodingProblem2 {
    public static void main(String args[]) {
        int[] arr = { 1, 2, 3, 4, 5 };
        int[] ans = solution(arr, arr.length);
        System.out.println(Arrays.toString(ans));

        arr = new int[] { 3, 2, 1 };
        ans = solution(arr, arr.length);
        System.out.println(Arrays.toString(ans));
    }

    private static int[] solution(int[] arr, int n) {
        int[] left = new int[n];
        int[] right = new int[n];
        int[] res = new int[n];
        left[0] = 1;
        right[n - 1] = 1;

        for (int i = 1; i < n; i++) {
            left[i] = arr[i - 1] * left[i - 1];
        }

        for (int i = n - 2; i >= 0; i--) {
            right[i] = arr[i + 1] * right[i + 1];
        }
        for (int i = 0; i < n; i++) {
            res[i] = left[i] * right[i];
        }
        return res;
    }
}

Answer 1

Time complexity-wise, I think not. You're required to 'visit' all numbers, and your solution is O(n), so that can't be improved.

Code clarity could be improved, as it's not very obvious what the intention is. Some comments would help that. I think shifting indices by 1 might make it clearer (left[i+1] = arr[i] * left[i]), but then maybe not because it'd mess up the last loop.

Have you explored different algorithms? I wonder if straightforward memoization makes a very clear solution for this.