LeetCode: Russian Doll Envelopes Solution

Approach

Longest increasing subsequence

Implementation

1/**
2 * @param {number[][]} envelopes
3 * @return {number}
4 */
5var maxEnvelopes = function (envelopes) {
6  const N = envelopes.length
7  const mem = Array(N).fill(null)
8  envelopes.sort((a, b) => a[0] - b[0])
9
10  const lis = i => {
11    if (mem[i] !== null) {
12      return mem[i]
13    }
14
15    let res = 1
16    for (let j = 0; j < i; j++) {
17      if (
18        envelopes[j][0] < envelopes[i][0] &&
19        envelopes[j][1] < envelopes[i][1]
20      ) {
21        res = Math.max(res, 1 + lis(j))
22      }
23    }
24
25    return (mem[i] = res)
26  }
27
28  let max = -Infinity
29  for (let i = 0; i < N; i++) {
30    max = Math.max(max, lis(i))
31  }
32
33  return max
34}