forked from neetcode-gh/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
238-Product-of-Array-Except-Self.js
71 lines (58 loc) · 2.44 KB
/
238-Product-of-Array-Except-Self.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/**
* Array
* Time O(N) | Space O(N)
* https://leetcode.com/problems/product-of-array-except-self/
* @param {number[]} nums
* @return {number[]}
*/
var productExceptSelf = (nums) => {
const products = 2;
const [ leftProduct, rightProduct ] = getProducts(products, nums);
carryForward(nums, leftProduct); /* Time O(N) | Space O(N) */
carryBackward(nums, rightProduct); /* Time O(N) | Space O(N) */
return combineProducts(nums, leftProduct, rightProduct); /* Time O(N) | Ignore Auxillary Space O(N) */
}
const getProducts = (products, nums) => new Array(products).fill()
.map(() => new Array(nums.length).fill(1));
var carryForward = (nums, leftProduct) => {
for (let index = 1; index < nums.length; index++) {/* Time O(N) */
leftProduct[index] = nums[index - 1] * leftProduct[index - 1];/* Space O(N) */
}
}
var carryBackward = (nums, rightProduct) => {
for (let index = (nums.length - 2); 0 <= index; index--) {/* Time O(N) */
rightProduct[index] = nums[index + 1] * rightProduct[index + 1];/* Space O(N) */
}
}
const combineProducts = (nums, leftProduct, rightProduct) => {
const products = new Array(nums.length).fill(1);/* Ignore Auxillary Space O(N) */
for (let index = 0; index < nums.length; index++) {/* Time O(N) */
products[index] = leftProduct[index] * rightProduct[index];/* Ignore Auxillary Space O(N) */
}
return products;
}
/**
* Array - Ignore Auxillary Space
* Time O(N) | Space O(1)
* https://leetcode.com/problems/product-of-array-except-self/
* @param {number[]} nums
* @return {number[]}
*/
var productExceptSelf = (nums) => {
const products = new Array(nums.length).fill(1);/* Ignore Auxillary Space O(N) */
carryForward(nums, products); /* Time O(N) | Ignore Auxillary Space O(N) */
carryBackward(nums, products);/* Time O(N) | Ignore Auxillary Space O(N) */
return products;
};
var carryForward = (nums, products, product = 1) => {
for (let index = 0; index < nums.length; index++) {/* Time O(N) */
products[index] = product; /* Ignore Auxillary Space O(N) */
product *= nums[index];
}
}
var carryBackward = (nums, products, product = 1) => {
for (let index = (nums.length - 1); 0 <= index; index--) {/* Time O(N) */
products[index] *= product; /* Ignore Auxillary Space O(N) */
product *= nums[index];
}
}