leetcode/javascript/0312-burst-balloons.js at main · neetcode-gh/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
/**
 * DP - Top Down
 * Matrix - Memoization
 * Time O(N^3) | Space O(N^2)
 * https://leetcode.com/problems/burst-balloons/
 * @param {number[]} nums
 * @return {number}
 */
var maxCoins = (nums) => {
    const _nums = [1, ...nums, 1]; /* Time O(N)         | Space O(N) */

    return search(_nums); /* Time O(N * N * N) | Space O((N * N) + HEIGHT) */
};

var search = (
    nums,
    left = 1,
    right = nums.length - 2,
    memo = initMemo(nums),
) => {
    const isBaseCase = right - left < 0;
    if (isBaseCase) return 0;

    const hasSeen = memo[left][right] !== -1;
    if (hasSeen) return memo[left][right];

    return dfs(
        nums,
        left,
        right,
        memo,
    ); /* Time O(N * N * N) | Space O((N * N) + HEIGHT) */
};

var initMemo = (nums) =>
    new Array(nums.length)
        .fill() /* Time O(N) | Space O(N) */
        .map(() =>
            new Array(nums.length).fill(-1),
        ); /* Time O(N) | Space O(N) */

var dfs = (nums, left, right, memo, result = 0) => {
    for (let i = left; i <= right; i++) {
        /* Time O(N) */
        const gain = nums[left - 1] * nums[i] * nums[right + 1];
        const _left = search(
            nums,
            left,
            i - 1,
            memo,
        ); /* Time O(N * N) | Space O(HEIGHT) */
        const _right = search(
            nums,
            i + 1,
            right,
            memo,
        ); /* Time O(N * N) | Space O(HEIGHT) */
        const remaining = _left + _right;

        result = Math.max(result, remaining + gain);
    }

    memo[left][right] =
        result; /*                               | Space O(N * N) */
    return result;
};

/**
 * DP - Bottom Up
 * Matrix - Tabulation
 * Time O(N^3) | Space O(N^2)
 * https://leetcode.com/problems/burst-balloons/
 * @param {number[]} nums
 * @return {number}
 */
var maxCoins = (nums) => {
    const tabu = initTabu(nums); /* Time O(N * N)     | Space O(N * N) */

    search(nums, tabu); /* Time O(N * N * N) | Space O(N * N) */

    return tabu[1][nums.length];
};

var initTabu = (nums) =>
    new Array(nums.length + 2)
        .fill() /* Time O(N) | Space O(N) */
        .map(() =>
            new Array(nums.length + 2).fill(0),
        ); /* Time O(N) | Space O(N) */

var search = (nums, tabu) => {
    const _nums = [1, ...nums, 1]; /* Time O(N) | Space O(N) */

    for (let left = nums.length; 1 <= left; left--) {
        /* Time O(N) */
        for (let right = left; right <= nums.length; right++) {
            /* Time O(N) */
            for (let i = left; i <= right; i++) {
                const gain = _nums[left - 1] * _nums[i] * _nums[right + 1];
                const remaining = tabu[left][i - 1] + tabu[i + 1][right];

                tabu[left][right] =
                    /*   | Space O(N * N) */
                    Math.max(remaining + gain, tabu[left][right]);
            }
        }
    }
};