LeetCode - Dynamic Programming

Posted on | In ,

Record the Dynamic Programming topic algorithm problems.

0005. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.
Example 2:
Input: “cbbd”
Output: “bb”

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

const longestPalindrome = function(s) {
    let max = '';
    for (let i = 0; i < s.length; i++) {
        for (let j = 0; j < 2; j++) {
            let left = i;
            let right = i + j;
            while (s[left] && s[left] === s[right]) {
                left--;
                right++;
            }
            if ((right - left - 1) > max.length) {
                max = s.substring(left + 1, right);
            }
        }
    }
    return max;
};

Runtime: 144 ms
Memory Usage: 36.2 MB

0062. Unique Paths

A robot is located at the top-left corner of a m x n grid.The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid. How many possible unique paths are there?
Note: m and n will be at most 100.
Example 1:
Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:

  1. Right -> Right -> Down
  2. Right -> Down -> Right
  3. Down -> Right -> Right
    Example 2:
    Input: m = 7, n = 3
    Output: 28

solution:

1
2
3
4
5
6
7
8
9
10
11
12
const uniquePaths = (m, n) => {
    let currentRow = new Array(n);
    for (let i = 0; i < n; i++) {
        currentRow[i] = 1;
    }
    for (let row = 1; row < m; row++) {
        for (let j = 1; j < n; j++) {
            currentRow[j] += currentRow[j - 1];
        }
    }
    return currentRow[n - 1];
};

Runtime: 64 ms
Memory Usage: 34 MB

For context, here’s an example for how to fill out a 3x6 grid in the more traditional DP regime:
0 | 1 | 1 | 1 | 1 | 1
1 | 2 | 3 | 4 | 5 | 6
1 | 3 | 6 | 10 | 15 | 21
Notice that for every i and j, matrix[i][j] is the total number of ways of getting to (i, j).

0064. Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
Example:
Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const minPathSum = (grid) => {
    let m = grid.length;
    let n = grid[0].length;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (i === 0 && j === 0) {
                continue;
            } else if (i === 0) {
                grid[i][j] = grid[i][j] + grid[i][j - 1];
            } else if (j === 0) {
                grid[i][j] = grid[i][j] + grid[i - 1][j];
            } else {
                grid[i][j] =  grid[i][j] + Math.min(grid[i - 1][j],  grid[i][j - 1]);
            }
        }
    }
    return grid[m - 1][n - 1];
};

Runtime: 72 ms
Memory Usage: 35.6 MB

0070. Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.
Example 1:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.

  1. 1 step + 1 step
  2. 2 steps
    Example 2:
    Input: 3
    Output: 3
    Explanation: There are three ways to climb to the top.
  3. 1 step + 1 step + 1 step
  4. 1 step + 2 steps
  5. 2 steps + 1 step

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const climbStairs = (n) => {
    // fibonacci
    if(n <= 2) {
        return n;
    }
    let one_step_before = 2;
    let two_steps_before = 1;
    let all_ways = 0;
    for(let i = 2; i < n; i++){
    all_ways = one_step_before + two_steps_before;
    two_steps_before = one_step_before;
        one_step_before = all_ways;
    }
    return all_ways;
};

Runtime: 64 ms
Memory Usage: 33.9 MB

0072. Edit Distance

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on a word:
Insert a character
Delete a character
Replace a character

Example 1:
Input: word1 = “horse”, word2 = “ros”
Output: 3
Explanation:
horse -> rorse (replace ‘h’ with ‘r’)
rorse -> rose (remove ‘r’)
rose -> ros (remove ‘e’)

Example 2:
Input: word1 = “intention”, word2 = “execution”
Output: 5
Explanation:
intention -> inention (remove ‘t’)
inention -> enention (replace ‘i’ with ‘e’)
enention -> exention (replace ‘n’ with ‘x’)
exention -> exection (replace ‘n’ with ‘c’)
exection -> execution (insert ‘u’)

solution1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const minDistance = (A, B) => {
    let go = (A, B, i, j, memo = {}) => {
        let key = `${i},${j}`;
        if (memo[key])
            return memo[key];
        if (!i || !j)
            return memo[key] = i + j;
        return memo[key] = Math.min(
            go(A, B, i - 1, j - 1, memo) + Number(A[i - 1] != B[j - 1]),
            go(A, B, i - 1, j, memo) + 1,
            go(A, B, i, j - 1, memo) + 1
        );
    };
    return go(A, B, A.length, B.length);
};

Runtime: 416 ms
Memory Usage: 74.9 MB

solution2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const minDistance = (A, B) => {
    let [M, N] = [A.length, B.length];
    let dp = [...Array(M + 1)].map(row => Array(N + 1).fill(0));
    for (let i = 0; i <= M; ++i) dp[i][0] = i; 
    for (let j = 0; j <= N; ++j) dp[0][j] = j;
    for (let i = 1; i <= M; ++i)
        for (let j = 1; j <= N; ++j)
            dp[i][j] = Math.min(
                dp[i - 1][j - 1] + Number(A[i - 1] != B[j - 1]),
                dp[i - 1][j] + 1,
                dp[i][j - 1] + 1,
            );
    return dp[M][N];
};

Runtime: 92 ms
Memory Usage: 44.6 MB

solution3:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const minDistance = (A, B) => {
    let [M, N] = [A.length, B.length];
    let pre = [...Array(N + 1)].map((_, i) => i);
    for (let i = 1; i <= M; ++i) {
        let cur = [...pre];
        cur[0] = i;
        for (let j = 1; j <= N; ++j) {
            cur[j] = Math.min(
                pre[j - 1] + Number(A[i - 1] != B[j - 1]),
                pre[j] + 1,
                cur[j - 1] + 1,
            );
        }
        [pre, cur] = [cur, pre]; // swap
    }
    return pre[N];
};

Runtime: 112 ms
Memory Usage: 43.9 MB

0085. Maximal Rectangle

Given a rows x cols binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

Example 1:
Input: matrix = [[“1”,”0”,”1”,”0”,”0”],[“1”,”0”,”1”,”1”,”1”],[“1”,”1”,”1”,”1”,”1”],[“1”,”0”,”0”,”1”,”0”]]
Output: 6

Example 2:
Input: matrix = []
Output: 0

Example 3:
Input: matrix = [[“0”]]
Output: 0

Example 4:
Input: matrix = [[“1”]]
Output: 1

Example 5:
Input: matrix = [[“0”,”0”]]
Output: 0

Constraints:
rows == matrix.length
cols == matrix.length
0 <= row, cols <= 200
matrix[i][j] is ‘0’ or ‘1’.

solution1:

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
const maximalRectangle = (matrix) => {
  if (!matrix.length || !matrix[0].length) return 0;
  const height = matrix.length;
  const width = matrix[0].length;
  const lefts = matrix[0].map(() => 0);
  const rights = matrix[0].map(() => width);
  const heights = lefts.slice();
  let max = 0;
  for (let row = 0; row < height; row++) {
    let left = 0;
    let right = width;
    for (let i = 0; i < width; i++) {
      if (matrix[row][i] === '1') {
        lefts[i] = Math.max(left, lefts[i]);
        heights[i]++;
      } else {
        lefts[i] = heights[i] = 0;
        left = i + 1
      }

      const rightIdx = width - 1 - i;
      if (matrix[row][rightIdx] === '1') {
        rights[rightIdx] = Math.min(right, rights[rightIdx])
      } else {
        rights[rightIdx] = width;
        right = rightIdx;
      }
    }
    for (let i = 0; i < width; i++) {
      max = Math.max(max,(rights[i] - lefts[i]) * heights[i]);
    }
  }
  return max
}

Runtime: 100 ms
Memory Usage: 41.5 MB

solution2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const maximalRectangle = (matrix) => {
  const n = matrix.length;
    if (n === 0) return 0;
    const m = matrix[0].length;
    const h = new Array(n).fill(0);
    let max = 0;
    for (let j = 0; j < m; j++) {
        for (let i = 0; i < n; i++) {
            if (matrix[i][j] === '1') h[i]++;
            else h[i] = 0;
        }
        for (let i = 0; i < n; i++) {
            let k1 = i - 1;
            while (k1 >= 0 && h[i] <= h[k1]) k1--;
            let k2 = i + 1;
            while (k2 < n && h[i] <= h[k2]) k2++;
            max = Math.max(max, h[i] * (k2 - k1 - 1));
        }
    }
    return max;
}

Runtime: 100 ms
Memory Usage: 42 MB

0096. Unique Binary Search Trees

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?
Example:
Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST’s

solution:

1
2
3
4
5
6
7
8
9
const numTrees = (n) => {
    function factorial( num ){
        if( num <= 0 )
            return 1;
        else
            return num * factorial( num - 1 );
    }
    return factorial( 2 * n ) / ( factorial( n + 1 ) * factorial( n ) );
};

Runtime: 48 ms
Memory Usage: 33.9 MB

0139. Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
Note:
The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.
Example 1:
Input: s = “leetcode”, wordDict = [“leet”, “code”]
Output: true
Explanation: Return true because “leetcode” can be segmented as “leet code”.
Example 2:
Input: s = “applepenapple”, wordDict = [“apple”, “pen”]
Output: true
Explanation: Return true because “applepenapple” can be segmented as “apple pen apple”.
Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
Output: false

solution 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const wordBreak = (s, wordDict) => {
  if (wordDict.length === 0) {
      return false;
  }
  const dict = new Set(wordDict);
  const visited = new Set();
  const q = [0];

  while (q.length) {
    const start = q.shift();

    if (!visited.has(start)) {
      for (let end = start + 1; end <= s.length; end++) {
        if (dict.has(s.slice(start, end))) {
          if (end === s.length) return true;
          q.push(end);
        }
      }
      visited.add(start);
    }
  }
  return false;
};

Runtime: 68 ms
Memory Usage: 36.9 MB

solution 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const wordBreak = (s, wordDict) => {
  if (wordDict.length === 0) {
      return false;
  }
  const dp = new Array(s.length + 1).fill(false);
  dp[0] = true;

  for (let i = 1; i <= s.length; i++) {
    for (let j = 0; j < i; j++) {
      const word = s.slice(j, i);
      if (dp[j] === true && wordDict.includes(word)) {
        dp[i] = true;
        break;
      }
    }
  }

  return dp[s.length];
};

Runtime: 60 ms
Memory Usage: 36.7 MB

0152. Maximum Product Subarray

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example 1:
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
const maxProduct = (nums) => {
  let res = -Number.MAX_VALUE;
  let min = 1;
  let max = 1;
  for (let num of nums) {
    [min, max] = [
      Math.min(num, min * num, max * num),
      Math.max(num, min * num, max * num),
    ];
    res = Math.max(res, max);
  }
  return res;
};

Runtime: 64 ms
Memory Usage: 37.6 MB

0198. House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 2:
Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const rob = (nums) => {
    const len = nums.length;
    if(len === 0) {
        return 0;
    }
    if(len === 1) {
        return nums[0];
    }
    let totals = [nums[0], Math.max(nums[0], nums[1])];
    for(let i = 2; i < len; i ++){
        totals[i] = Math.max(totals[i - 1], totals[i - 2] + nums[i]);
    }
    return totals[totals.length - 1];
};

Runtime: 76 ms
Memory Usage: 33.9 MB

0221. Maximal Square

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.
Example:
Input:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Output: 4

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const maximalSquare = (matrix) => {
    if (!matrix.length) {
        return 0;
    }
    let dp = new Array(matrix.length+1).fill(0).map(()=>new Array(matrix[0].length+1).fill(0));
    let max = 0;
    for (let r = 1; r < dp.length; r++) {
        for (let c = 1;c < dp[0].length; c++) {
            if (matrix[r-1][c-1] != 0) {
                dp[r][c] = Math.min(dp[r][c-1], dp[r-1][c], dp[r-1][c-1]) + 1;
                max = Math.max(dp[r][c], max);
            }
        }
    }
    return max**2;
};

Runtime: 76 ms
Memory Usage: 40.5 MB

0300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.
Example:
Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Note:
There may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?

solution 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const lengthOfLIS = (nums) => {
    if (!nums.length) {
        return 0;
    }
    const lis = [];
	for (let i = 0; i < nums.length; i++) {
		lis.push(1);
		for (let j = 0; j < i; j++) {
			if (nums[j] < nums[i]) {
                lis[i] = Math.max(lis[i], lis[j] + 1);
            }
		}
	}
	return Math.max.apply(null, lis);
};

Runtime: 88 ms
Memory Usage: 34.7 MB

solution 2:

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
const lengthOfLIS = (nums) => {
    if (!nums.length) {
        return 0;
    }
    const tails = [];
    tails[0] = nums[0];
    for(let i = 1; i < nums.length; i++) {
        // replace current nums[i] with head if it's smaller
        if(nums[i] < tails[0]) {
            tails[0] = nums[i];
        // if current nums[i] is bigger than the largest value we've recorded
        // we can extend our tails by current nums[i]
        } else if(nums[i] > tails[tails.length-1]) {
            tails.push(nums[i]);
        } else {
            // using binary search to find the insertion point of current nums[i]
            // return r because we're looking to replace index of tail that's greater than nums[i]
            let l = 0;
            let r = tails.length-1;
            while(l < r) {
                const mid = (l+r)/2 >> 0;
                if(tails[mid] >= nums[i]) {
                    r = mid
                } else {
                    l = mid + 1;
                }
            }
            tails[r] = nums[i];
        }
    }
    return tails.length;
};

Runtime: 56 ms
Memory Usage: 34.6 MB

0309. Best Time to Buy and Sell Stock with Cooldown

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
Example:
Input: [1,2,3,0,2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]

solution 1:

1
2
3
4
5
6
7
8
9
10
const maxProfit = (prices) => {
    let buy = -Number.MAX_VALUE;
    let cooldown = 0;

    return prices.reduce((sell, price) => {
       buy = Math.max(buy, cooldown - price);
       cooldown = Math.max(cooldown, sell);
       return Math.max(sell, buy + price);
    }, 0);
};

Runtime: 80 ms
Memory Usage: 34.7 MB

solution2:

1
2
3
4
5
6
7
8
9
10
11
const maxProfit = (prices) => {
  let n = prices.length;
  let dpi0 = -Infinity, dpi1 = 0, dpi2 = 0;
  for (let i = 0; i < n; i++) {
      let tmp = dpi0;
      dpi0 = Math.max(dpi0, dpi2 - prices[i]);
      dpi2 = dpi1;
      dpi1 = Math.max(dpi1, tmp + prices[i]);
  }
  return dpi1;
};

Runtime: 72 ms
Memory Usage: 33.7 MB

0322. Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Example 1:
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:
Input: coins = [2], amount = 3
Output: -1
Note:
You may assume that you have an infinite number of each kind of coin.

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
const coinChange = (coins, amount) => {
    const dp = new Array(amount + 1);
    dp.fill(Number.MAX_VALUE);
    dp[0] = 0;
    for (let i = 1; i <= amount; i++) {
        for (let j = 0; j < coins.length; j++) {
            if (i - coins[j] >= 0) {
                dp[i] = Math.min(dp[i - coins[j]] + 1, dp[i]);
            }
        }
    }
    return dp[amount] === Number.MAX_VALUE ? -1 : dp[amount];
};

Runtime: 92 ms
Memory Usage: 36.9 MB

0338. Counting Bits

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.
Example 1:
Input: 2
Output: [0,1,1]
Example 2:
Input: 5
Output: [0,1,1,2,1,2]

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const countBits = (num) => {
  let arr = [0, 1, 1];
  for (let i = 3; i <= num; i++){
    let even = 0;
    let temp = i;
    let odd = 0;
    if((i/2) !== Math.floor(i/2)) {
      even += 1;
      temp = i - 1;
    }
    odd = arr[temp/2];
    arr.push(even + odd);
  }
  return arr.slice(0, num+1);
};

Runtime: 92 ms
Memory Usage: 40.8 MB

0416. Partition Equal Subset Sum

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Note:
Each of the array element will not exceed 100.
The array size will not exceed 200.
Example 1:
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const canPartition = (nums) => {
   let sum = 0;
   for(let num of nums){
       sum += num;
   }
   if(sum %2 !== 0) {
       return false;
   }
   let half= sum / 2;
   let dp = new Array(half + 1).fill(false);
   dp[0] = true;
   for(let num of nums){
       for(let i = half; i >= num; i--){
           dp[i] = dp[i] || dp[i-num];
       }
   }
   return dp[half];
};

Runtime: 96 ms
Memory Usage: 35.6 MB

0494. Target Sum

You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.
Find out how many ways to assign symbols to make sum of integers equal to target S.
Example 1:
Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
There are 5 ways to assign symbols to make the sum of nums be target 3.
Note:
The length of the given array is positive and will not exceed 20.
The sum of elements in the given array will not exceed 1000.
Your output answer is guaranteed to be fitted in a 32-bit integer.

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const findTargetSumWays = (nums, S) => {
    if (!nums || nums.length === 0) {
        return count;
    }
    function helper(pos, sum, hash, nums, S) {
        let key = `${pos}->${sum}`;
        if (hash.hasOwnProperty(key)) {
            return hash[key];
        }
        if (pos === nums.length) {
            return sum === S ? 1 : 0;
        }
        let add = helper(pos + 1, sum + nums[pos], hash, nums, S);
        let minus = helper(pos + 1, sum - nums[pos], hash, nums, S);
        hash[key] = add + minus;
        return hash[key];
    };
    return helper(0, 0, {}, nums, S);
};

Runtime: 272 ms
Memory Usage: 42.8 MB