Computer Science fundamentals in JavaScript

cs.js

// Build a tree using a compacted object with no pointer for the left/right children
function buildTree(A) {
  // Shuffle the array. so we gain a more balanced search tree
  A.sort(function() { return parseInt(Math.random()*3) - 1; });

  var tree = {'0': A[0]}, current = 1;
  var inserted, node, treeSize = 1;

// This will take O(N * log N) if we have a balanced tree
// the worst case cost will be O(N^2)
  for (var i = 1; i < A.length; i++) {
    node = A[i];
    inserted = false;
    current = 1;
    while (!inserted) {
      if ( treeSize <= current ) {
        treeSize += current - treeSize;
      }
      if (tree[current - 1] === undefined) {
        tree[current - 1] = node;
        inserted = true;
      } else if (tree[current - 1] < node) {
        // go to the right
        current = current * 2 + 1;
      } else {
        current = current * 2;
      }
    }
  }
  tree.length = treeSize;
  return tree;
}
po
// Levenshtein distance in O(2^n)
function strDistance(str1, str2, i, j) {
  if (i === 0 || j === 0) {
    return Math.max(i, j);
  }
  var distance = (str1.charAt(i) == str2.charAt(j)) ? 0 : 1;
  
  return Math.min(
    strDistance(str1, str2, i - 1, j) + 1
    , strDistance(str1, str2, i, j - 1) + 1
    , strDistance(str1, str2, i - 1, j - 1) + distance
  );
}

// Levenshtein distance in O(n^2)
function strDistance(str1, str2, len1, len2) {
  var distance, 
    memo = new Array(len1 + 1);

  for (var i = 0; i <= len1; i++) {
   memo[i] = new Array(len2 + 2);
   memo[i][0] = i;
  }
  for (var i = 0; i <= len2; i++) {
    memo[0][i] = i;
  }
  for (var i = 1; i <= len1; i++) {
    for (var j = 1; j <= len2; j++) {
      distance = (str1.charAt(i) == str2.charAt(j)) ? 0 : 1;
      memo[i][j] = Math.min(
        memo[i - 1][j] + 1
        , memo[i][j - 1] + 1
        , memo[i - 1][j - 1] + distance
      );
    }
  }
  return memo[len1][len2];
}

// Get nodes relative to a given target if their distance equal 'distance'
function getNodesWithDistance(flatTree, distances, index, distance, visited) {
  if (index < 0 || index > flatTree.length || visited[index] === true) {
    return [];
  }
  if (distance === 0) {
    return (flatTree[index - 1] === undefined) ? [] : [flatTree[index - 1]];
  }

  visited[index] = true;

  var result = [];

  result = result.concat(
      getNodesWithDistance(flatTree, distances, index * 2, distance - 1, visited)
    , getNodesWithDistance(flatTree, distances, index * 2 + 1, distance - 1, visited)
    , getNodesWithDistance(flatTree, distances, parseInt(index / 2), distance - 1, visited)
  );

  return result;
}
// Get all elements which have a distance of `D` (distance) from node `N` (node)
function treeLevel(flatTree, node, distance) {
  var distances = {};
  var treeSize = flatTree.length;
  var currentIndex = 0;
  var queue = [1];

  // Place a sentinel
  distances[-1] = -1; 

  while (queue.length > 0 && currentIndex < treeSize) {
    // queue.shift() is slow! O(N) uuuuh!
    // Instead implement an amortized dequeue operation.
    currentIndex = queue.shift();

    // Get the distance of the parent and add 1
    distances[currentIndex - 1] = distances[parseInt(currentIndex / 2) - 1] + 1;
    queue.push(currentIndex * 2);
    queue.push(currentIndex * 2 + 1);
  }

  currentIndex = 1;

  while (currentIndex <= treeSize) {
    if (flatTree[currentIndex - 1] == node) {
      return getNodesWithDistance(flatTree, distances, currentIndex, distance, {});
    } else if (flatTree[currentIndex - 1] > node) {
      currentIndex = currentIndex * 2;
    } else {
      currentIndex = currentIndex * 2 + 1;
    }
  }
  return null;
}

// Integer partition problem in O(2^n) uhh. can be reduced to polynomial time using DP
function intPartition(target, maxValue, append) {
  if (target === 0) {
    return [append];
  } else {
    var parts, result = [];
    if (maxValue > 1) {
      parts = intPartition(target, maxValue-1, append.slice(0));
      for (var i = 0; i < parts.length; i++) {
        result.push(parts[i]);
      }
    }
    if (target >= maxValue) {
      parts = intPartition(target - maxValue, maxValue, append.concat([maxValue]));
      for (var i = 0; i < parts.length; i++) {
        result.push(parts[i]);
      }
    }
    return result;
  }
}

// Money change problem
// Given an amount and a list of bills, return all the possible ways you can give change
// Example: getChange(5,5,[1,2], [])
//  sample output -> [[1,1,1,1,1], [1,2,2]]
function getChange(amount, maxVal, bills, append) {
  if (amount === 0) {
    return [append];
  }

  var results = [];

  if (maxVal > 1) {
    var result1 = getChange(amount, maxVal - 1, bills, append.slice(0));

    result1.forEach(function(a) {
      results.push(a);
    });
  }
 
  if (amount >= maxVal) {
    if (~bills.indexOf(maxVal)) {
      var result2 = getChange(amount - maxVal, maxVal, bills, append.concat([maxVal]));
      result2.forEach(function(a) {
        results.push(a);
      });
    }
  }
  return results;
}
// Set partition problem
// Returns true if A can be partitioned into two subsets such that the sum of the elements
// of both half is the same
// @param {Bool} recursive if you want a O(2^n) cost, false if you are smart and want O(n^2)
function partition(A, recursive) {
  var findSubset;
  var POS_STAY = 0;
  var POS_UP = 1;
  var POS_UP_LEFT = 2;

  if (recursive === true) {
    // O(2^n) Ouhh!
    findSubset = function(A, n, sum) {
      if (sum == 0) {
        return true;
      }
      if (n == 0 && sum != 0) {
        return false;
      }
      if (A[n-1] > sum) {
        return findSubset(A, n - 1, sum);
      }
      return findSubset(A, n - 1, sum) || findSubset(A, n - 1, sum - A[n - 1]);
    };
  } else {
    // Dynamic programming
    findSubset = function(A, n, sum) {
      var memo = new Array(n + 1);

      for (var i = 0; i <= n; i++) {
        memo[i] = new Array(sum + 1);
        memo[i][0] = {sol: true, pos: POS_STAY};
      }

      for (var i = 1; i <= sum; i++) {
        memo[0][i] = {sol: false, pos: POS_STAY};
      }

      for (var i = 1; i <= n; i++) {
        for (var j = 1; j <= sum; j++) {
          if (A[i-1] > j) {
            memo[i][j] = {sol: memo[i-1][j].sol, pos: POS_UP};
          } else {
            if (memo[i-1][j].sol) {
              memo[i][j] = {sol: true, pos: POS_UP};
            } else if (memo[i-1][j-A[i-1]].sol) {
              memo[i][j] = {sol: true, pos: POS_UP_LEFT};
            } else {
              memo[i][j] = {sol: false, pos: POS_STAY};
            }
          }
        }
      }

      // If we have a solution
      if (memo[n][sum].sol) {
        var setA = [];
        var setB = [];

        var j = sum;
        var i = n;
        while (i > 0 && j>=0) {
          if (memo[i][j].pos == POS_UP_LEFT) {
            // This is a solution for setA
            setA.push(A[i-1]);
            i = i - 1;
            j = j - A[i];
          } else if (memo[i][j].pos == POS_UP) {
            i = i - 1;
            setB.push(A[i]);
          } else {
            i = i - 1;
            setB.push(A[i]);
          }
        }

        while (i > 0) {
          i--;
          setB.push(A[i]);
        }

        return [setA, setB]; 
      } else {
        return [];
      }
    };
  }

  var sum = 0;
  for (var i = 0; i < A.length; i++) {
    sum += A[i];
  }
  if (sum % 2 != 0) {
    return [];
  }
  return findSubset(A, A.length, sum / 2);
}

// Object mixin
var extend = function(obj) {
    var args = Array.prototype.slice.call(arguments, 1);
 
    for (var i = 0, len = args.length; i < len; i++) {
      for (var prop in args[i]) {
        obj[prop] = args[i][prop];
      }
    }
};s

// Extend an Object
Model.extend = function(proto) {
  var parent = this;
  var child = function() { return parent.apply(this, arguments); };
  // static 
  extend(child, parent);

  var Dummy = function() { this.constructor = child; };
  Dummy.prototype = parent.prototype;

  child.prototype = new Dummy();

  extend(child.prototype, proto);

  child.__super__ = parent.prototype;

  return child;
};

// Test
var User = Model.extend({
  init: function(username, password) {
    this.props.username = username;
    this.props.password = password;
  }
});
// Subtype of User
var AdminUser = User.extend({
  init: function(username, password) {
    this.__super__.init(username, password);
  }
})


// Swap two values in an array A using bit manipulation. 
// The V8 engine may optimize swap if you store a copy of the value, but it's an interesting hack
function swap(A, i, j) {
  A[i] = A[i] ^ A[j];
  A[j] = A[i] ^ A[j];
  A[i] = A[i] ^ A[j];
}

// Get a random index within [l, r] inclusive
function randomIndex(l, r) {
  return parseInt((r - l + 1) * Math.random()) + l;
}

// Partition subrutine.
// Takes an array A and partition the array such that 
// A[i] for each i in 0...pivot-1 <= A[pivot] <= A[j] for each j in pivot+1...sizeof(A) 
// This procedure runs in O(n)
function partition(A, l, r) {
  var pivotIndex = randomIndex(l, r);
  var pivot = A[pivotIndex];
  var q = pivotIndex;

  for (var i = l + 1; i <= r; i++) {
    if (A[i] < pivot) {
      swap(A, i, q);
      q++;
    }
  }
  return q;
}

// Quicksort
// This is the randomized version which runs in O(n*log n)  :)
function quicksort(A, l, r) {
  if (l < r ) {
    var q = partition(A, l, r);
    quicksort(A, l, q);
    quicksort(A, q + 1, r);
  }
}
// Gets the nth element in an unsorted array in O(n) time. 
// for example nth([2,8,9,1,10,25], 0, 5, 1) will return the first element in the array which is 1, in O(n)! 
// no sorting is required
function nth(A, l, r, n) {
  if (l == r) {
    return A[l]
  } else {

    var q = partition(A, l, r);
    var k = q - l + 1;

    if (k == n) {
      return A[q];
    } else if (n < k) {
      return nth(A, l, q - 1, n);
    } else {
      return nth(A, q + 1, r, n - k);
    }
  }
}

// Get the hight of a given tree or subtree.
function treeHeight(tree) {
  if (tree === null) {
    return 0;
  }
  return Math.max(treeHeight(tree.left), treeHeight(tree.right)) + 1;
}

// Get the Lowest common ancestor of two nodes in a tree
function lca(root, a, b) {
  if (root == null) {
    return null;
  }
  if (a > root.value && b > root.value) {
    return lca(root.right, a, b);
  } else if (a < root.value && b < root.value) {
    return lca(root.left, a, b);
  } else {
    return root;
  }
}

// 3SUM problem for a sorted list
// Return a triple where A[i] + A[j] = A[t]  where {i, j , t} >= 0 && <= sizeof(list) -1
// Runtime: O(n^2), memory: O(1)
function sums(list) {
  var solutions = [];

  for (var i = list.length-1; i >= 2; i--) {
    var c = list[i];
    var r = i - 1;
    var l = 0;

    while (l < r) {
      var a = list[l];
      var b = list[r];
      var sum = a + b;
      if (sum == c) {
        solutions.push([a, b, c]);
        l = l + 1;
        r = r - 1;
      } else if (sum < c) {
        l = l + 1;
      } else {
        r = r - 1;
      }
    }
  }
  return solutions;
}

// 3SUM problem for an unsorted list
// Runtime: O(n^2) , memory: O(n)
function sums2(list) {
  var solutions = [];

  for (var i = 0; i < list.length; i++) {
    var c = list[i];
    var memo = {};
    for (var j = 0; j < list.length; j++) {
      if (j != i) {
        if (memo[c - list[j]]) {
          solutions.push([list[j], c - list[j], c]);
        }
        memo[list[j]] = true;
      }
    }
  }

  return solutions;
}

// Take a sorted list and 
// return an array of 2-tuples where A[i] + A[j] = target
// Runtime: o(n)
function eqTarget(list, target) {
  var solutions = [];
  var l = 0;
  var r = list.length - 1;
  var sum;

  while (l < r) {
    sum = list[l] + list[r];
    if (sum === target) {
      solutions.push([list[l], list[r]]);
      l = l + 1;
      r = r - 1;
    } else if (sum < target) {
      l = l + 1;
    } else {
      r = r - 1;
    }
  }
  return solutions;
}

// Takes an unsorted list and 
// return an array of 2-tuples where A[i] + A[j] = target
// Runtime: o(n)
function eqTarget2(list, target) {
  var solutions = [];
  var memo = {};
  for (var i = 0; i < list.length; i++) {
    if (memo[target - list[i]]) {
      solutions.push([list[i], target - list[i]]);
    }
    memo[list[i]] = true;
  }

  return solutions;
}

// Find a value in a sorted list using a binary search
// Runtime: O(log n)
function find(list, value) {
  var l = 0;
  var r = list.length;
  var mid;

  while (l <= r) {
    mid = Math.ceil(( l + r ) / 2);

    if (list[mid] < value) {
      l = mid + 1;
    } else if (list[mid] > value) {
      r = mid - 1;
    } else {
      return mid;
    }
  }

  return -1;
}

// Return the max crossing sum in a list where  l <= m <= r
function maxCrossing(list, l, m, r) {
  var leftMax = -Infinity;
  var leftSum = 0;
  var leftIndex;

  for (var i = m; i >= l; i--) {
    leftSum += list[i];
    if (leftSum > leftMax) {
      leftMax = leftSum;
      leftIndex = i;
    }
  }
  var rightMax = -Infinity;
  var rightSum = 0;
  var rightIndex;

  for (var i = m + 1; i <= r; i++) {
    rightSum += list[i];
    if (rightSum > rightMax) {
      rightMax = rightSum;
      rightIndex = i;
    }
  }

  return {
    sum: leftMax + rightMax,
    left: leftIndex,
    right: rightIndex
  }
}

// Returns the maximum crossing subarray in an array
// runtime O(n*log n)
function maxSubarray(list, l, r) {
  if (l === r) {
    return {left: l, right: r, sum: list[l]};
  } else {
    var mid = Math.floor((l + r ) / 2);
    var left = maxSubarray(list, l, mid);
    var right = maxSubarray(list, mid + 1, r);
    var crossing =  maxCrossing(list, l, mid, r);

    if (left.sum >= crossing.sum && left.sum >= right.sum) {
      return {left: left.left, right: left.right, sum: left.sum};
    } else if (right.sum >= crossing.sum && right.sum >= left.sum) {
      return {left: right.left, right: right.right, sum: right.sum};
    } else {
      return {left: crossing.left, right: crossing.right, sum: crossing.sum};
    }
  }
}
// Sorts an array using bubble sort
// runtime: O(n^2)
function bubbleSort(A) {
  var wasSwaped = false;
  do {
    wasSwaped = false;
    for (var j = 1; j < A.length; j++) {
      if (A[j - 1] > A[j]) {
        swap(A, j - 1, j);
        wasSwaped = true;
      }
    }
  } while (wasSwaped);

  return A;
}

// Sorts an array using selection sort
// runtime: O(n^2)
function selectionSort(A) {
  for (var i = 0; i < A.length; i++) {
    var k = i;
    var min = A[i];
    for (var j = i + 1; j < A.length; j++) {
      if ([j] < min) {
        min = A[j];
        k = j;
      }
    }
    if (k != i) {
      swap(A, i, k);
    }
  }
  return A;
}

// Sorts an array using insertion sort
// runtime: O(n^2)
function insertionSort(A) {
  for (var i = 0; i < A.length; i++) {
    var j = i;
    while (j > 0 && A[j - 1] > A[j]) {
      swap(A, j - 1, j);
      j--;
    }
  }
  return A;
}

// Merge two sorted arrays into one array
// runtime: O(n)
function merge(A, B) {
  var list = [];
  var j  = 0;
  var i = 0;

  while (i < A.length && j < B.length) {
    if (A[i] < B[j]) {
      list.push(A[i]);
      i++;
    } else {
      list.push(B[j]);
      j++;
    }
  }
  while (i < A.length) {
    list.push(A[i]);
    i++;
  }
  while (j < B.length) {
    list.push(B[j]);
    j++;
  }

  return list;
}

// Sort an array using merge sort
// runtime: O(n*log n). memory: O(n)

function mergeSort(list, l, r) {
  if (l === r) {
    return [list[l]];
  }
  var mid = Math.floor( (l + r) / 2);
  var left = mergeSort(list, l, mid);
  var right = mergeSort(list, mid + 1, r);

  return merge(left, right);
}

// Return the power set of a set.
// That is, all the possible subsets within a set
// runtime: O(2^n)

function powerSet(set) {
  if (set.length === 0) {
    return [];
  }
  if (set.length === 1) {
    return [[set[0]]];
  }
 
  var result = [ [set[0]] ];
  var subset = powerSet(set.slice(1));
 
  for (var i = 0; i < subset.length; i++) {
      result.push(subset[i]);
      result.push([set[0]].concat(subset[i]));
  }
  return result;
}
 
// Return a list with all the permutations of a given string
// Runtime: O(n!)
function permutation(str) {
  if (str === '') {
    return [];
  } else if (str.length === 1) {
    return [str];
  } else {
    var solutions = [];
    for (var i = 0; i < str.length; i++) {
      var character = str.charAt(i);
      var permutes = permutation(str.substr(0, i) + str.substr(i + 1));
      for (var j = 0; j < permutes.length; j++) {
        solutions.push(character + permutes[j]);
      }
    }
    return solutions;
  }
}
 
// Return a list with all the permutations of a given array
// Runtime: O(n!)
function permutation2(arry) {
  if (arry.length === 0) {
    return [];
  } else if (arry.length === 1) {
    return [[arry[0]]];
  } else {
    var solutions = [];
    for (var i = 0; i < arry.length; i++) {
      var character = arry[i];
      var permutes = permutation2(arry.slice(0, i).concat(arry.slice(i + 1)));
      for (var j = 0; j < permutes.length; j++) {
        solutions.push([character].concat(permutes[j]));
      }
    }
    return solutions;
  }
}

// Return the first `num` binary numbers
function binary(num) {
  if (num <= 1) {
    return ['0', '1'];
  }
 
  var b = binary(num - 1);
  var result = [];
 
  for (var i = 0; i < b.length; i++) {
    result.push(b[i] + '0');
    result.push(b[i] + '1');
  }
   
  return result;
}
 
// Longest common subsquence problem
// Return the string that contains the most elements in common
// runtime: O(n^2)
function lcs(str1, str2) {
  var len1 = str1.length;
  var len2 = str2.length;
  var table = new Array(len1+1);
  var POSITION = {LEFT: 1, UP: 2, LEFTUP: 3, NONE: 0};
 
  for (var i = 0; i <= len1; i++) {
    table[i] = new Array(len2+1);
    table[i][0] = {len: 0, dest: POSITION.NONE};
  }
  for (var j = 0; j <= len2; j++) {
    table[0][j] = {len: 0, dest: POSITION.NONE};
  }
  for (var i = 1; i <= len1; i++) {
    for (var j = 1; j <= len2; j++) {
      if (str1.charAt(i-1) == str2.charAt(j-1)) {
        table[i][j] = {len: table[i-1][j-1].len + 1, dest: POSITION.LEFTUP};
      } else {
        if (table[i-1][j].len > table[i][j-1].len) {
          table[i][j] = {len: table[i-1][j].len, dest: POSITION.LEFT};
        } else {
          table[i][j] = {len: table[i][j-1].len, dest: POSITION.UP};
        }
      }
    }
  }
  var i = len1;
  var j = len2;
  var str = '';
  
  while (i > 0 && j > 0) {
    if (table[i][j].dest === POSITION.LEFT) {
      i--;
    } else if (table[i][j].dest === POSITION.UP) {
      j--;
    } else if (table[i][j].dest === POSITION.LEFTUP) {
      str = str1.charAt(i-1) + str;
      i--;
      j--;
    } else {
      break;
    }
  }
  return str;
}

// Diff algorithm
// Return the difference character by character between two strings using lcs
// runtime: O(n^2)
function diff(str1, str2) {
  var sub = lcs(str1, str2);
  var len1 = str1.length;
  var len2 = str2.length;
  var changes = '';
 
  var i = 0, j = 0, s = 0;
   
  while (i < len1 && j < len2 && s < sub.length) {
    if (str1.charAt(i) == sub.charAt(s)) {
      if (str2.charAt(j) == sub.charAt(s)) {
        changes += '*' + str1.charAt(i);
        i++;
        s++;
        j++;
      } else {
         changes += '+' + str2.charAt(j);
         j++;
      }
    } else {
      changes += '-' + str1.charAt(i);
      i++;
    }
  }
 
  while (i < len1) {
    changes += '-' + str1.charAt(i);
    i++;
  }
   while (j < len2) {
    changes += '+' + str2.charAt(j);
    j++;
  }
  return changes;
}

// Subset sum problem
// Return a subset of `a` such that if you sum all the elements within that subset
// they will equal a target number `q`

// Recurrence: 
// i : means include the ith element in A
// target: the current target value
// P(i, target) -> true  if i = 0 && target = 0 (don't include any element)
//              -> false if i = 0 && target!=0
//              -> (target >= A[i - 1] && P(i - 1, target - A[i - 1])) || P(i - 1, target) otherwise
//
// * The exponential function:
// function getSubset(A, i, target) {
//    if (i === 0) {
//      return (target === 0);
//    } else {
//      return (target >= A[i-1] && getSubset(A, i - 1, target - A[i-1])) || getSubset(A, i-1, target);
//    }
// }
// Example:  getSubset([1,2,3,4,5], 5, 7) -> true because  5+2 or 3+4 or 1+2+4 is 7
//
//
// DP Solution Runtime: O(n^2)
function getSubset(A, q) {
  var listSize = A.length;
  var memo = new Array(listSize + 1);
 
  var solutions = [];
 
  for (var i = 0; i <= listSize; i++) {
    memo[i] = new Array(q + 1);
  }
  for (var i = 1; i <= q; i++) {
    memo[0][i] = {belong: false, exists: false};
  }
 
  memo[0][0] = {belong: false, exists: true};
 
  for (var i = 1; i <= listSize; i++) {
    for (var j = 0; j <= q; j++) {
        memo[i][j] = {belong: false, exists: false};
 
      if (j >= A[i-1] && memo[i-1][j-A[i-1]].exists) {
        memo[i][j].exists = true;
        memo[i][j].belong = true;
        solutions.push(A[i - 1]);
      } else if (memo[i - 1][j].exists) {
        memo[i][j].exists = true;
      } 
    }
  }
  return memo[listSize][q].exists;
}


// Rod cutting problem in O(2^n)
// Giving a list `A` where A[i] represents the cost of a rod of length i
// Return the maximum cost you can get from a rod of size n if you cut 
// it in smaller pieces
function cutRod(A, n) {
  if (t === 0) {
    return 0;
  }
  var max = -Infinity;
  for (var i = 1; i <= n; i++) {
    max = Math.max(max, A[i] + cutRod(A, n - i));
  }
  return max;
}

// Rod cutting problem in O(n^2) using DP
// Example: cutRodDP([0,1,5,8,9,10,17,17,20,24,30],9) -> { maxCost: 25, parts: [ 3, 6 ] }
// 
function cutRodDP(A, n) {
  var memo = new Array(n + 1);
  var parts = new Array(n + 1);

  memo[0] = 0;

  for (var i = 1; i <= n; i++) {
    maxCost = - Infinity;
    for (var j = 1; j <= i; j++) {
      costIncludingJ =  A[j] + memo[i - j];
      if (costIncludingJ > maxCost) {
         maxCost = costIncludingJ;
         parts[i] = j;
      }
    };
     memo[i] = maxCost;
  }
  
  var solutions = [];
  var i = n;
  
  while (i > 0) {
    solutions.push(parts[i]);
    i = i - parts[i];
  }
  return  {maxCost: memo[n], parts: solutions};
}

// Longest increasing subsquence
// Example: longestIncreasingSubsquence([2,9,0,10)
//          ->  [ 2, 9, 10 ]
// Based on http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms
function longestIncreasingSubsquence(list) {
  var maxLength = 0;
  var lengths = new Array(list.length + 1);
  var previous = new Array(list.length);

  lengths[0] = 0;

  for (var i = 0; i < list.length; i++) {
    var lo = 1;
    var hi = maxLength;
    while (lo <= hi) {
      var mid = Math.ceil((lo + hi) / 2);
      if (list[i] > list[lengths[mid]]) {
        lo = mid + 1;
      } else if (list[i] < list[lengths[mid]]) {
        hi = mid - 1;
      }
    }

    var newLength = lo;
    lengths[newLength] = i;
    previous[i] = lengths[newLength-1];

    if (newLength > maxLength) {
      maxLength = newLength;
    }
  }

  var last = lengths[maxLength];
  var result = new Array(maxLength);

  for (var k = maxLength - 1; k >= 0; k--) {
    result[k] = list[last];
    last = previous[last];
  }
  return result;
}

// Minimum path sum problem
// https://oj.leetcode.com/problems/minimum-path-sum/
function path(A) {
    var rows = A.length;
    var columns = A[0].length;
    var dp = new Array(rows);

    dp[0] = new Array(columns);
    dp[0][0] = A[0][0];

    for (var i = 1; i < rows; i++) {
        dp[i] = new Array(columns);
        dp[i][0] = dp[i - 1][0] + A[i][0];
    }
    for (var i = 1; i < columns; i++) {
        dp[0][i] =  dp[0][i - 1] + A[0][i];
    }
    for (var i = 1; i < rows; i++) {
        for (var j = 1; j < columns; j++) {
            dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + A[i][j];
        }
    }
    return dp[rows - 1][columns - 1];
}