Tasks

Dynamic Programming

Index	Task Name	Task Number	Difficulty	Link
1	Climbing Stairs	70	Easy	Link
2	House Robber	198	Easy	Link
3	Maximum Subarray	53	Easy	Link
4	Unique Paths	62	Medium	Link
5	Longest Increasing Subsequence	300	Medium	Link
6	Word Break	139	Medium	Link
7	Coin Change	322	Medium	Link
8	Decode Ways	91	Medium	Link
9	Regular Expression Matching	10	Hard	Link
10	Edit Distance	72	Hard	Link
11	N-th Tribonacci Number	1137	Easy	Link
12	Min Cost Climbing Stairs	746	Easy	Link
13	Partition Equal Subset Sum	416	Medium	Link
14	01 Matrix	542	Medium	Link
15	House Robber II	213	Medium	Link
16	Maximum Product Subarray	152	Medium	Link
17	Palindromic Substrings	647	Medium	Link
18	Longest Common Subsequence	1143	Medium	Link

// 70. Climbing Stairs

// Time: O(n) | Space: O(1)
var climbStairs = function(n) {
    if (n < 2) {
        return n;
    }
    let a = 1;
    let b = 1;
    let c;
    for (let i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
};

/*
Dynamic Programming
-------------------------------
1. Define the objective function.
   f(i) is the number of distinct ways to reach the i-th stair.
2. Identify the base cases:
   f(0) = 1;
   f(1) = 1;
3. Write down the recurrence relation for the optimized objective function.
   f(n) = f(n - 1) + f(n - 2).
4. What is the order of execution?
   bottom-up
5. Where to look for the answer
   f(n)
-------------------------------
Time: O(n) | Space: O(1)
*/

// 139. Word Break

// Time: O(n^3) | Space: O(n)
var wordBreak = function(s, wordDict) {
    const n = s.length;
    // Converts the word dictionary list into a set for constant time O(1) lookup.
    const wordSet = new Set(wordDict);
    
    // Each index i in this array will represent whether the substring of s 
    // from the start up to index i can be segmented using words from the dictionary.
    const dp = new Array(n + 1).fill(false);

    // Sets the base case. An empty string can always be segmented (using zero words).
    dp[0] = true;

    for (let i = 1; i <= n; i++) {
        for (let j = 0; j < i; j++) {
            // Checks if the substring up to index j is segmentable (dp[j] is true) 
            // and the substring from j to i exists in the word dictionary.
            if (dp[j] && wordSet.has(s.substring(j, i))) {
                // this substring can be segmented.
                dp[i] = true;
                break;
            }
        }
    }

    return dp[n];
};

// 322. Coin Change

// Time: O(n * amount) | Space: O(amount)
var coinChange = function(coins, amount) {
  // Get the number of coin denominations
  const n = coins.length;

  // Create an array (dp) to store the minimum number of coins needed for each amount of change.
  // Initialize all elements with Infinity initially, representing an impossible or unknown state.
  const dp = Array(amount + 1).fill(Infinity);

  // Set the number of coins needed to make change for 0 as 0, as it requires no coins.
  dp[0] = 0;

  // Iterate over each coin denomination.
  for (let i = 0; i < n; i++) {

    // Iterate over each amount from the current coin denomination to the target amount.
    for (let j = coins[i]; j <= amount; j++) {
      // Calculate the minimum number of coins needed by either including the current coin
      // (1 + number of coins needed for the remaining amount after considering the current coin)
      // or excluding the current coin (minimum number of coins needed without considering the current coin).
      // Choose the option with a smaller number of coins.
      dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
    }
  }

  // If the minimum number of coins needed for the target amount is still Infinity (impossible),
  // return -1. Otherwise, return the minimum number of coins needed for the target amount.
  return dp[amount] === Infinity ? -1 : dp[amount];
}

/*
Dynamic Programming
------------------------------------
1. Iterate over each coin denomination.
2. Iterate over each amount from current denomination to the target amount.
3. Calculate the minimum number of coins including/excluding the current coin.
4. Return the last calculated value as a result.

https://www.youtube.com/watch?v=H9bfqozjoqs

------------------------------------
Time: O(n amount) | Space: O(amount)
*/

// 91. Decode Ways

// Time: O(n) | Space: O(n)
var numDecodings = function(s) {
    // Get the length of the string.
    const strLen = s.length;

    // Initialize a DP table where dp[i] represents the number of ways to decode a substring of length i.
    const dp = new Array(strLen + 1).fill(0);

    // Base case: an empty string can be decoded in 1 way (no way at all).
    dp[0] = 1;

    // If the first character is not '0', then it can be decoded. Otherwise, it can't be decoded.
    if (s[0] !== '0') {
        dp[1] = 1;
    } else {
        return 0; // Strings starting with '0' can't be decoded.
    }

    // Start decoding from the second character onwards.
    for (let i = 2; i <= strLen; i++) {
        // If the current character is not '0', it can be decoded on its own.
        // So, we add the number of ways to decode the string up to the previous character to dp[i].
        if (s[i - 1] !== '0') {
            dp[i] += dp[i - 1];
        }

        // Check if the current and previous character together form a valid encoding between '10' to '26'.
        // If so, add the number of ways to decode the string up to the character before the previous one to dp[i].
        if (s[i - 2] === '1' || (s[i - 2] === '2' && s[i - 1] <= '6')) {
            dp[i] += dp[i - 2];
        }
    }

    // Return the number of ways to decode the entire string.
    return dp[strLen];
};

// 1137. N-th Tribonacci Number

// Time: O(n) | Space: O(n)
var tribonacci_1 = function(n) {
    return dp(n, { 0: 0, 1: 1, 2: 1 });
};

function dp(n, memo) {
    if (n in memo) {
        return memo[n];
    }
    memo[n] = dp(n - 1, memo) + dp(n - 2, memo) + dp(n - 3, memo);
    return memo[n];
}

/*
Dynamic Programming (Top Down)
----------------------------
DFS + Memoization
----------------------------
Time: O(n) | Space: O(n)
*/

// Time: O(n) | Space: O(n)
var tribonacci_2 = function(n) {
    if (n < 3) {
        return n ? 1 : 0;
    }
    const dp = [0, 1, 1];
    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
    }
    return dp[n];
};

/*
Dynamic Programming (Bottom Up)
----------------------------
Tabulation
----------------------------
Time: O(n) | Space: O(n)
*/

// Time: O(n) | Space: O(1)
var tribonacci = function(n) {
    if (n < 3) {
        return n ? 1 : 0;
    }

    let [a, b, c] = [0, 1, 1];

    for (let i = 0; i < n - 2; i++) {
        [a, b, c] = [b, c, a + b + c];
    }
    return c;
};

/*
Dynamic Programming (Bottom Up)
----------------------------
Tabulation
----------------------------
Time: O(n) | Space: O(1)
*/

// 746. Min Cost Climbing Stairs

// Time: O(n) | Space: O(1)
var minCostClimbingStairs = function(cost) {
    if (cost.length === 2) {
        return Math.min(cost[0], cost[1]);
    }
    let a = cost[0];
    let b = cost[1];
    let c;
    for (let i = 2; i < cost.length; i++) {
        c = cost[i] + Math.min(a, b);
        a = b;
        b = c;
    }
    return Math.min(a, b);
};

/*
Dynamic Programming. Bottom-Up
-------------------------------
1. If length is 2 -> return min 0/1.
2. Go from 3rd element to n. Current price is i-th price + min(i-1, i-2).
3. Then i-2 = previous (i-1) price.
4. Previous (i-1) = current.
-------------------------------
Time: O(n) | Space: O(1)
*/

// 416. Partition Equal Subset Sum

// Time: O(n * target) | Space: O(target)
var canPartition = function(nums) {
    // Calculate the sum of all numbers in the array
    const sum = nums.reduce((a, b) => a + b);

    // If the sum is odd, it is not possible to partition the array into two equal subsets
    if (sum % 2 === 1) {
        return false;
    }

    // Calculate the target sum for each subset
    const target = sum / 2;

    // Create an array to store the maximum sum that can be achieved for each possible sum up to the target
    const dp = new Array(target + 1).fill(0);

    // Iterate over each number in the array
    for (let i = 0; i < nums.length; i++) {
        // Iterate backwards from the target sum to the current number
        for (let j = target; j >= nums[i]; j--) {
            // Update the maximum sum that can be achieved at the current sum by either including or excluding the current number
            dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            
            // Return true once we reach the target.
            if (dp[j] === target) {
                return true;
            }
        }
    }

    // There are no variants to reach the target.
    return false;
};

/*
Dynamic Programming. Bottom Up
--------------------------------------
1. Target is the sum/2 for all elements in the array.
2. It is not possible to divide the array in case sum is odd.
3. Create the target.size array to keep the dp results.
4. We try to add num to every i-th element in range from num to target.

Including: dp[j - nums[i]] + nums[i]

This part represents the sum that can be achieved by including the current number (nums[i]) in the subset.
dp[j - nums[i]] represents the maximum sum that can be achieved at the current sum (j - nums[i]) without including the current number.
Adding nums[i] to it includes the current number in the sum.

Excluding: dp[j]
--------------------------------------
Time: O(n * target) | Space: O(target)
*/

// 542. 01 Matrix

// Time: O(m * n) | Space: O(1)
var updateMatrix = function(mat) {
        // Number of rows
    let m = mat.length;

    // Number of columns
    let n = mat[0].length;

    // Top-Left to Bottom-Right traversal:
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            // Skip 0 elements in the mat
            if (mat[i][j] === 0) {
                continue;
            }
            // Prepare the cell to be correctly computed from its neighbors.
            mat[i][j] = Infinity;
            // Do not check top if we are on the 1st row
            if (i - 1 >= 0) {
                mat[i][j] = Math.min(mat[i][j], 1 + mat[i - 1][j]);
            }
            // Do not check left if we are on the 1st column
            if (j - 1 >= 0) {
                mat[i][j] = Math.min(mat[i][j], 1 + mat[i][j - 1]);
            }
        }
    }

    // Bottom-Right to Top-Left traversal
    for (let i = m - 1; i >= 0; i--) {
	    for (let j = n - 1; j >= 0; j--) {
            // Skip 0 elements in the mat
            if (mat[i][j] === 0) {
                continue;
            }
            // Do not check bottom if we are on the last row
            if (i + 1 < m) {
                mat[i][j] = Math.min(mat[i][j], 1 + mat[i + 1][j]);
            }
            // Do not check right if we are on the last column
            if (j + 1 < n) {
                mat[i][j] = Math.min(mat[i][j], 1 + mat[i][j + 1]);
            }
        }
    }

    return mat;
}

/*
* DP
* 1. Go from top-left to the bottom-right. Compute current mat[i][j] distance from top and left elements.
* 2. Go from the bottom-right to the top-left. Compute curent mat[i][j] distance from bottom anf right elements.
* 3. Return result. 
*
* Time: O(m * n)
* Space: O(1)
*/

// 213. House Robber II

// Time: O(n) | Space: O(1)
var rob = function(nums) {
    if (!nums.length) {
        return 0;
    }
    if (nums.length === 1) {
        return nums[0];
    }
    // Exclude the last house.
    const oddValue = robHelper(nums.slice(0, -1));

    // Exclude the first house.
    const evenValue = robHelper(nums.slice(1));

    // Return the max of two searches.
    return Math.max(oddValue, evenValue);
};

function robHelper(nums) {
    // to store the maximum amount of money that can be robbed up to the house 
    // before the previous one (i.e., up to house i-2).
    let prevMax = 0;

    // to store the maximum amount that can be robbed up to the current house 
    // (or the previous one as we iterate).
    let currMax = nums[0];

    for (let i = 1; i < nums.length; i++) {
        // Starts iterating from the second house, 
        // since the first house (index 0) is already considered in currentMax.
        let newMax = Math.max(currMax, prevMax + nums[i]);
        
        // Updates prevMax to hold the value of currentMax for the next iteration. 
        // This prepares it to represent the house i-2 for the next loop iteration.
        prevMax = currMax;
        
        // This prepares it to represent the house i-1 for the next loop iteration.
        currMax = newMax;
    }
    return currMax;
}

// 152. Maximum Product Subarray

// Time: O(n) | Space: O(1)
var maxProduct = function(nums) {
    if (!nums.length) {
        return 0;
    }
    let max = nums[0];
    let min = nums[0];
    let res = nums[0];

    for (let i = 1; i < nums.length; i++) {
        const possibleMax = max * nums[i];
        const possibleMin = min * nums[i];

        // Value might be 0, +num, -num.
        // nums[i] if possible min/max is 0.
        // possible min/max in every check because we never sure about sign.
        max = Math.max(nums[i], possibleMax, possibleMin);
        min = Math.min(nums[i], possibleMax, possibleMin);

        // Remember max for all iterations.
        res = Math.max(max, res);
    }
    return res;
};

// 647. Palindromic Substrings

// Time: O(n^2) | Space: O(n^2)
var countSubstrings = function(s) {
    // Initialize a count variable to store the number of palindromic substrings.
    let count = 0;

    // Create a 2D DP table. dp[i][j] will be 'true' if the substring s[i...j] is a palindrome.
    let dp = Array(s.length)
        .fill(false)
        .map(() => Array(s.length).fill(false));
    
    // Single characters are always palindromic, hence initialize diagonal to true.
    for (let i = 0; i < s.length; i++) {
        dp[i][i] = true;
        count++;
    }

    // Check for substring of length 2.
    for (let i = 0; i < s.length - 1; i++) {
        // If two consecutive characters are the same, then the substring is palindromic.
        dp[i][i + 1] = s[i] === s[i + 1];
        // Increase count if the current substring is palindromic.
        count += dp[i][i + 1];
    }

    // Check for substrings of length 3 to s.length.
    for (let length = 3; length <= s.length; length++) {
        // Use two pointers i and j to check palindromic substrings.
        for (let i = 0, j = length - 1; j < s.length; i++, j++) {
            // A substring is palindromic if its start and end characters are the same 
            // and its inner substring is also palindromic.
            dp[i][j] = dp[i + 1][j - 1] && s[i] === s[j];
            // Increase count if the current substring is palindromic.
            count += dp[i][j];
        }
    }
    
    // Return the total count of palindromic substrings.
    return count;
};

// 1143. Longest Common Subsequence

// DP
// Time: O(n * m) | Space: O(n * m)
var longestCommonSubsequence = function(str1, str2) {
  // Store the lengths of both strings.
  const n = str1.length;
  const m = str2.length;

  // Initialize a 2D DP table. The table will store the result of LCS for each substring.
  const dp = new Array(n);
  for (let i = 0; i < n; i++) {
    dp[i] = new Array(m).fill(-1);
  }

  // Start the recursive calculation for the LCS, starting from the beginning of both strings.
  return longestCommonSubsequenceHelper(str1, str2, 0, 0, dp);
}

function longestCommonSubsequenceHelper(str1, str2, i, j, dp) {
  // Base case: if we reach the end of one of the strings, the LCS length is 0.
  if (i === str1.length || j === str2.length) {
    return 0;
  } 
  // If the current LCS value for substrings starting from i, j isn't calculated yet:
  else if (dp[i][j] === -1) {
    // If the characters match, the LCS length is increased by 1.
    if (str1[i] === str2[j]) {
      dp[i][j] = 1 + longestCommonSubsequenceHelper(str1, str2, i + 1, j + 1, dp);
    } else {
      // If the characters don't match, we try two possibilities:
      // 1. Move forward in str1, keeping str2 position same.
      // 2. Move forward in str2, keeping str1 position same.
      // We take the maximum of these two possibilities.
      dp[i][j] = Math.max(
        longestCommonSubsequenceHelper(str1, str2, i + 1, j, dp),
        longestCommonSubsequenceHelper(str1, str2, i, j + 1, dp)
      );
    }
  }

  // Return the memoized result.
  return dp[i][j];
}