Elements

ConstantSpaceDFSBST.js

function Node(val, parent) {
	return {parent: parent, val:val, left:null, right:null}
}
// Root
var two = Node(2, null)
// L
var one = Node(1, two)
two.left = one
var onefive = Node(1.5, one)
one.right = onefive
// R
var three = Node(3, two)
two.right = three
var four = Node(4, three)
three.right = four
var threefive = Node(3.5, four)
four.left = threefive
var five = Node(5, four)
four.right = five

DFS(two, function(x) {
	console.log(x.val)
})

function DFS(node, cb) {
  var root = node
  var wentLeft = false
  var wentRight = false
  while (node !== null) {
    // 'recurse left'
    while (!wentLeft && node.left) {
      node = node.left
    }
    // 'visit node'
    if (!wentRight) {
      cb(node)  
    }
    // 'recurse right'
    if (!wentRight && node.right) {
      wentLeft = false
      node = node.right
      continue
    }
    // 'return'
    // In a BST, 'returning' from the right subtree means we've already recursed right from the parent
    if (node.parent === null || node.parent.val < node.val) {
      wentRight = true
    } else {
      // recursing from the leftsubtree means we still have yet to recurse right from the parent
      wentRight = false
    }
    // either way returning means we MUST have gone (or tried) left
    wentLeft = true
    node = node.parent
  }
}

// Recursive for comparison
function DFS(node, cb) {
  if (!node) {
    return
  }
  if (node.left) {
    DFS(node.left, cb)
  }
  cb(node)
  if (node.right) {
    DFS(node.right, cb)
  }
  return
}

CountInversions.js

var arr = [3,6,4,2,5,1]
MergeSort(arr, 0, arr.length)

function MergeSort(A, start, end) {
	var count = 0
    if (start > end) {
        return [[], 0]
    }
    if (end == start) {
        return [[A[start]], 0]
    }
    var mid = Math.floor((end-start)/2) + start
    var left = MergeSort(A, start, mid)
    var right = MergeSort(A, mid+1, end)
    count += left[1] + right[1]
    var res = Merge(left[0], right[0])
    res[1] += count
    return res
}

function Merge(A, B) {
    var i = 0
    var j = 0
    var count = 0
    var merged = []
    while (i < A.length || j < B.length) {
        if (j < B.length && B[j] < A[i]) {
            merged.push(B[j])
            j++
            count+=A.length-i
        } else if (i < A.length && A[i] < B[j]) {
            merged.push(A[i])
            i++
        } else if (j >= B.length) {
            merged.push(A[i])
            i++
        } else if (i >= A.length) {
            merged.push(B[j])
            j++
        }
    }
    return [merged, count]
}

IterativeDFS.js

var five = {val: 5}
var four = {val: 4}
var three = {val: 3, left: four, right: five}
var two = {val: 2}
var one = {val: 1, left: two, right: three}

DFS(one)

function DFS(root) {
  var stack = [root]
  var out = []
  var node = root
  while (stack.length) {
  	//console.log('eyy', stack)
    while (node && node.wentLeft && node.wentRight) {
      out.push(node.val)
      node = stack.pop()
    }
    if (!node) {
    	continue
    }
    while (!node.wentLeft && node.left) {
  	  stack.push(node)
      node.wentLeft = true
      if (!node.right) {
        node.wentRight = true
      }
      node = node.left
    }
    if (!node.left) {
      node.wentLeft = true
    }
    if (!node.right) {
      node.wentRight = true
    }
    while (node.wentLeft && !node.wentRight && node.right) {
      stack.push(node)
      node.wentRight = true
      node = node.right
    }
  }
  out.pop()
  return out
}

LongestParens.js

function LP(P) {
  var maxS = 0
  var maxE = 0
  var s = -2
  var e = -2
  var max = 0
  var stack = []
  for (var i = 0; i < P.length; i++) {
    var char = P[i]
    if (char == ")") {
      if (stack.length) {
        var open = stack.pop()
        // valid close
        // wrap?
        if (open == s - 1 && i == e + 1) {
          s = open
          e = i
        // add?
        } else if (open == e + 1 && i == open + 1) {
          e = i
        } else {
          s = open
          e = i
        }
      } else {
        // set start and end to next
        s =  i + 1
        e = i
      }
      if (e - s > max) {
        maxS = s
        maxE = e
        max = e - s
      }  
    } else {
      stack.push(i)
    }
  }
  return P.slice(maxS, maxE+1)
}

MergeSortLinkedList.js

function MSLL(head) {
  if (!head || head.next == null) {
    return head
  }
  var right = null
  right = split(head)
  head = MSLL(head)
  right = MSLL(right)
  return zip(head, right)
}

function split(head) {
  var right = null
  var fast = head
  var slow = head
  while (fast !== null) {
    for (var i = 0; i < 2; i++) {
      fast = fast.next
      if (!fast) {
        right = slow.next
        slow.next = null
        return head, right
      }
    }
    slow = slow.next
  }
  return head, right
}

function zip(left, right) {
  var head = {next:null}
  var merged = head
  while(left || right) {
    var node = null
    if (left.val <= right.val) {
      node = left
      left = left.next
    } else {
      node = right
      right = right.next
    }
    node.next = null
    merged.next = node
    merged = node
    
    if (!left) {
      merged.next = right
      right = null
    } else if (!right) {
      merged.next = left
      left = null
    }
  }
  return head.next
}

Perms

var dict = {2:['A','B','C']}

perms("2222", dict)

function perms (nums, dict) {
  var out = [""]
  for (var i = nums.length-1; i >= 0; i--) {
    var build = []
    var num = nums[i]
    var chars = dict[num]
    for (var k = 0; k < chars.length; k++ ) {
      var char = chars[k]
      for (var j = 0; j < out.length; j++) {
        build.push(char + out[j])
      }
    }
    out = build
  }
  return out
}

Perms.js

console.log(Perms([1,2,3,4,5,6,7,8]))

function Perms(A, t, o) {
  var o = o || []
  var t = t || []
  if (A.length === 0) {
    o.push(copy(t))
    return o
  }
  
  for (var i = 0; i < A.length; i++) {
    t.push(A[i])
    Perms(splice(A, i), t, o)
    t.pop()
  }
  
  return o
}

function copy (A) {
	return A.map(function(x) { return x })
}

function splice(A, i) {
	var out = []
	for (var j = 0; j < A.length; j++) {
		if (j == i) {
			continue
		}
		out.push(A[j])
	}
	return out
}

Queuedepths.js

function BFS(s) {
  // separates each depth into own subarr
  var q = [s]
  var qs = [q,[]]
  var depth = 0
  var final = []
  while (q.length > 0) {
    for (var j = 0; j < q.length; j++) {
      var p = q[j]
      for (var i = 0; i < p.children.length; i++) {
        var c = p.children[i]
        qs[(depth+1)%2].push(c)
      }
    }
    // add this 'queue' to the final output
    final.push(qs[depth%2])
    //'empty' and switch tracks
    qs[depth%2] = []
    depth++
    q = qs[depth % 2]
  }
  return final
}

rebuildPreorderBinTree.js

var thing = ["H", "B", "F", null, null, "E", "A", null, null, null, "C", null, "D", null, "G", "I", null, null, null]


var t = rebuild(thing)
DFS(t, function (x) {
  console.log(x)
})

function rebuild(T) {
  var stack = []
  for (var i = T.length-1; i >= 0; i--) {
    if (T[i] === null) {
      stack.push(null)
    } else {
      var left = null
      var right = null
      if (stack.length > 1) {
      	right = stack.pop()
      	left = stack.pop()
      }
      
      var n = CreateNode(T[i], right, left)
      stack.push(n)
    }
  }
  return stack.pop()
}

function CreateNode(val, left, right) {
  left = left || null
  right = right || null
  return {
    val: val,
    left: left,
    right: right
  }
}

function DFS(N, cb) {
  if (!N) {
    cb(N)
    return
  }
  cb(N.val)
  DFS(N.left, cb)
  DFS(N.right, cb)
}

shortestPath.js

var D = {
	"cat": 1,
	"mad": 1,
	"fad":1,
	"dad":1,
	"cad": 1,
	"bat":1,
	"mod":1,
	"mot":1,
	"bot":1
}

console.log(findShortestPath('cat', 'bot', D))

function findShortestPath(s, e, D) {
  var G = createGraph(s, e, D)
  var start = G[s]
  var end = G[e]
  return BFS(start, end)
}

function getPath(node) {
  var out = []
  while (node) {
    out.push(node.word)
    node = node.parent
  }
  
  return reverse(out)
}

function reverse(A) {
  var i = 0
  var j = A.length-1
  while (i<j) {
    A = swap(A, i, j)
    i++
    j--
  }
  return A
}

function swap(A, i, j) {
  var temp = A[i]
  A[i] = A[j]
  A[j] = temp
  return A
}

function BFS(s, e) {
  var q = [s]
  while (q[0]) {
    var node = q.shift()
    node.visited = true
    if (node === e) {
      return getPath(node)
    }
    for (var i = 0; i < node.children.length; i++) {
      var child = node.children[i]
      if (child === e) {
      	child.parent = node
      	return getPath(child)
      }
      if (!child.visited || !child.queued) {
        node.queued = true
        child.parent = node
        q.push(child)
      }
    }
  }
  return []
}

function Node(word) {
  return {
    visited: false,
    queued: false,
    word: word,
    children : []
  }
}

function createGraph(s, e, D) {
  D[s] = s
  D[e] = e
  var G = {}
  return connectGraph(D, G)
}

function connectGraph(D, G) {
  for (var A in D) {
    if (!G[A]) {
      G[A] = Node(A)
    }
    for (var B in D) {
      if (A === B) {
        continue
      }
      if (!G[B]) {
        G[B] = Node(B)
      }
      if (offByOne(A, B)) {
        G[A].children.push(G[B]) // can save on calculations here
      }
    }
  }
  return G
}

function offByOne(A, B) {
  var diff = A.length-B.length
  if (Math.abs(diff) > 0) {
    return false
  }
  // just one character off
  diff = 0
  for (var i = 0; i < A.length; i++) {
    if (A[i] !== B[i]) {
      diff++
    }
  }
  
  return diff <= 1
}

Sieve.js

S(50)

function S(n) {
  var A = getArr(n)
  var out = [2]
  for (var i = 2; i < n; i+=2) {
    if (A[i]) {
      out.push(A[i])
      for (var j = i + A[i]; j < n; j = j + A[i]) {
        A[j] = null
      }
    }
  }
  if (n < 2) {
    return []
  }
  return out
}

function getArr(n) {
  var arr = []
  for (var i = 0; i < n; i++) {
    arr[i] = i+1
  }
  return arr
}

SynthesizeExpression.js

var arr = [4,2,3]
var res = R(arr, arr.length, 123)

function R(A, i, T) {
	var v = getValue(A, 0, i)
  if (v == T) {
    return true
  }
  var e = i
  i--
  while (i > 0) {
    var right = getValue(A, i, e)
    var found = R(A, i, T - right)
    if (found) {
      return true
    }
    found = R(A, i, T / right)
    if (found) {
      return true
    }
    i--
  }
  return false
}

function getValue(arr, i, e) {
  var sum = 0
  for (j = i; j < e; j++) {
    sum *= 10
    sum += arr[j]
  }
  return sum
}

UnboundedBinSearch.js

var arr = [0,1,2,3,4,5]
Bin(arr, -1, 0, 1)


function Bin(arr, s, start, end) {
	console.log(start, end)
  if (start > end) {
    return -1
  }
  if (start == end) {
  	if (bounded(arr, start)) {
  		if (arr[start] === s) {
  			return start
  		}
  	}
  	return -1
  }
  var mid = Math.floor((end - start) / 2) + start
  
  if (bounded(arr, mid)) {
    if (arr[mid] === s) {
      return mid
    } else if (arr[mid] > s) {
      return Bin(arr, s, start, mid-1)
    } else {
    	// bounded and mid isn't the right value, shift one
      mid += 1
      return Bin(arr, s, mid, Math.floor((end-mid)/2) + mid)
    }
  } else {
  	// unbounded, so dont shift
    return Bin(arr, s, start, Math.floor((end-mid)/2) + mid)
  }
}

function bounded(arr, idx) {
  return idx < arr.length
}

WaterBlocks.js

var blocks = [0,0,1,3,1,0,1,4,2,3]
Water(blocks)

function Water(A) {
    var start = 0
    var i = 1
    var t = 0
    var volume = 0
    while (i < A.length) {
        t = getTallestIdx(A, start) // if tallest is 0 return the last instance of it
        volume += getVolumeForRange(A, start, t)
        start = t
        i = start + 1
    }
    return volume
}

function getTallestIdx(A, start) {
    var s = A[start]
    var i = start + 1
    var tallest = 0
    var t = i
    while (i < A.length) {
        if (A[i] >= tallest) {
            tallest = A[i]
            t = i
        }
        if (tallest > A[start]) {
            break
        }
        i++
    }
    return t
}

function getVolumeForRange(A, start, t) {
    var h = Math.min(A[start], A[t])
    start++
    var volume = 0
    while (start < t) {
        volume += h - A[start]
        start++
    }
    return volume
}