Solution 1Prefix Suffix
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
p = 1
result = []
for num in nums:
result.append(p)
p *= num
p = nums[-1]
for i in range(len(nums)-2,-1,-1):
result[i] *= p
p *= nums[i]
return resultpublic int[] productExceptSelf2(int[] nums) {
int n = nums.length;
int[] arr = new int[n];
int left = 1, right = 1;
for (int i=0; i<n; i++) {
arr[i] = left;
left *= nums[i];
}
for (int i = n - 1; i >= 0; i--) {
arr[i] *= right;
right *= nums[i];
}
return arr;
}Solution 2Suffix Array
Java
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] back = new int[n];
back[n-1] = nums[n-1];
for (int i = n-2; i > 0; i--) {
back[i] = nums[i] * back[i+1];
}
for (int i = 1; i < n; i++) {
nums[i] = nums[i] * nums[i-1];
}
int[] output = new int[n];
output[0] = back[1];
output[n-1] = nums[n-2];
for (int i = 1; i < n-1; i++) {
output[i] = nums[i-1] * back[i+1];
}
return output;
}