leetcode/javascript/238_Product_of_Array_Except_Self.js at master · dieface/leetcode · GitHub

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
// https://leetcode.com/problems/product-of-array-except-self/

/*
238. Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)
*/

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
  var result = [];

  nums.forEach(function(n) {
    result.push(1);
  });

  var left = 1;
  for(var i = 0; i < nums.length - 1; i++) {
    left *= nums[i];
    result[i + 1] = left;
  }

  var right = 1;
  for(var i = nums.length - 1; i > 0; i--) {
    right *= nums[i];
    result[i-1] *= right;
  }

  return result;
};


//function CursorFromStart(nums){
//    // NOTE cursor to an array recording product in left side
//    this.index = 1;
//    this.productLeft = nums[0];
//    this.offsetRight = function(){
//        this.productLeft = this.productLeft * nums[this.index];
//        this.index++;
//
//        console.log('left product: ', this.productLeft);
//        console.log('left index: ', this.index);
//    };
//}
//
//function CursorFromEnd(nums){
//    // NOTE cursor to an array recording product in right side
//    this.index = 0;
//    this.productRight = productRightSide(1, nums);   // NOTE start from index 1
//    this.offsetRight = function(){
//        if (nums[this.index+1] !== 0){
//            this.productRight = this.productRight / nums[this.index+1];
//        } else {
//            this.productRight = productRightSide(this.index+2, nums);
//        }
//        this.index++;
//
//        console.log('right product: ', this.productRight);
//        console.log('right index: ', this.index);
//    };
//}
//
//function productRightSide(index, array){
//    var result = 1;
//    array.slice(index, array.length).forEach(function(n){
//        result *= n;
//    });
//    return result;
//}
//
//var productExceptSelf = function(nums) {
//
//    var result = [],
//        cur = new CursorFromStart(nums),
//        curFromEnd = new CursorFromEnd(nums);
//
//    // get first result from curFromEnd
//    result.push(curFromEnd.productRight);
//    console.log('init result: ', result);
//    console.log('init cur: ', cur);
//    console.log('init curFromEnd: ', curFromEnd);
//    curFromEnd.offsetRight();
//
//    // NOTE start from index 1
//    for (var i = 1; i < nums.length; i++) {
//        console.log('------ i: ', i);
//
//
//        console.log('cur: ', cur.productLeft);
//        console.log('curFromEnd: ', curFromEnd.productRight);
//
//        result.push(cur.productLeft * curFromEnd.productRight);
//        console.log('result: ', result);
//
//        console.log('- cur offset -');
//        cur.offsetRight();
//
//        console.log('- curFromEnd offset -');
//        curFromEnd.offsetRight();
//    }
//
//    return result;
//};

var input = [1,2,3,4];
var output = productExceptSelf(input);

console.log('input: ', input);
console.log('output: ', output);