product-of-array-except-itself
Last updated
Was this helpful?
Last updated
Was this helpful?
Intuitive solution is to product the whole array, result is to divide itself. Notice from problem, without division and solve it in O(n)
.
Idea is to product from left to right, then right to left:
Init res[len]
, res[0] = 1, left = 1;
Scan array from left to right, skip the last number, from
index = 1, left = left * nums[index -1], res[index] = left;
init right = nums[len - 1], from second right most element, from
index = len - 2, res[index] = res[index] * right, right = nums[index] * right
return res.
For example:
Time Complexity: O(N)
Space Complexity: O(N)
N - the length of array nums