LeetCode Entry
238. Product of Array Except Self
Array of suffix-prefix products
238. Product of Array Except Self medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/539
Problem TLDR
Array of suffix-prefix products #medium
Intuition
Observe an example:
// 1 2 3 4
// * 2*3*4
// 1 * 3*4
// 1*2 * 4
// 1*2*3 *
As we can’t use / operation, let’s precompute suffix and prefix products.
Approach
Then we can think about the space & time optimizations.
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\)
Code
fun productExceptSelf(nums: IntArray): IntArray {
val suf = nums.clone()
for (i in nums.lastIndex - 1 downTo 0) suf[i] *= suf[i + 1]
var prev = 1
return IntArray(nums.size) { i ->
prev * suf.getOrElse(i + 1) { 1 }.also { prev *= nums[i] }
}
}
pub fn product_except_self(nums: Vec<i32>) -> Vec<i32> {
let n = nums.len(); let (mut res, mut p) = (vec![1; n], 1);
for i in 1..n { res[i] = nums[i - 1] * res[i - 1] }
for i in (0..n).rev() { res[i] *= p; p *= nums[i] }; res
}