Topics
Dynamic Programming

Fibonacci Number (opens in a new tab)

  • A good approach would be calculate the nth fibonacci number either recursively or iteratively
  • As we know nth fibonacci number is sum of n-1 th and n-2th fibonacci numbers, we can start from 1st position till we calculate nth.
/**
 * @param {number} n
 * @return {number}
 */
var fib = function (n) {
  // initialize 0th and 1st fibonacci numbers
  let fib1 = 0, fib2 = 1;
 
  for (let i = 1; i <= n; i++) {
    temp = fib2;
    fib2 = fib1 + fib2; // next fibonacci number is sum of current and next
    fib1 = temp; // current fibonacci number is next fibonacci number
  }
 
  return fib1;
};
Complexity
  • Time: O(n)
  • Space: O(1)

Pascal's Triangle (opens in a new tab)

  • Start with a pascal 2D array with default array with value 1. Use nested loops; one for row generation and other for values inside the each row.
  • Let each value of the current row be calculated from previous row values excluding 1st and last element. Prepend and append 1 to each row value (pattern says by default)
/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function (numRows) {
  var pascal = [[1]];
 
  for (var i = 1; i < numRows; i++) {
    pascal[i] = [1]; // 1st element of all the rows is 1
 
    for (var j = 1; j < i; j++) {
      pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j];
    }
 
    pascal[i][i] = 1; // last element of all the rows is 1
  }
  return pascal;
};
Complexity
  • Time: O(n2)
  • Space: O(n2)
TreeBacktracking