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;
 }
}

• Mast: Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers .
• Solomon Ucko: "Note: Division is not allowed." Why? Is it because of a restriction for the assignment?
• Maclean Pinto: @SolomonUcko Yes it is a restriction for the assignment

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.