evidanary

# Topological sort
Do a DFS and push items in a queue as you traverse the leaf nodes adding deepest element first
Queue will hold sorted output (for dependency management)
graph = {0 => [1], 1 => [2,3], 2 => [3], 3 => []}
def topo_sort(graph)
	seen = Set.new
	queue = []
	graph.each do |node, v|
	  dfs_helper(graph, node, seen, visited)
	end

evidanary

#Combinations
# Time complexity: N^K where k = target
# Space complexity: K * N^2
def nchoosek(numbers, target, partial=[])

  if partial.size == target
    puts "#{partial}"
    return
  end
  (0...numbers.length).each do |i|

evidanary

# Unique Permutation of all elements in an array
# Do something like if(i > 0 && nums[i] == nums[i - 1] && use[i - 1]) continue;
# See solution #https://discuss.leetcode.com/topic/31445/really-easy-java-solution-much-easier-than-the-solutions-with-very-high-vote
# Space: O(N), Time: N^N
def unique_permute(str)
    chars = str.chars
    chars = chars.sort
    res = []
    used = (0...arr.size).map { |i| false}
    perm_helper(chars, [], used, res)

evidanary

# Check if a binary tree is valid
class Solution
    def initialize()
        @prev = nil
    end
    def is_valid_bst(root)
        return true if root.nil?
        left = is_valid_bst(root.left) 
	    return false if (@prev && (@prev >= root.val ))
	    

evidanary

# check if there is three integers which sum up to the targeted sum
# fix k from 0...size-2 and then run sum of 2 numbers equal to target (see above)
def target_sum(arr, target)
  arr.sort!
  size = arr.size
  i, j = 0, size-1
  count = 0
  (0...size-2).each do |k|
    i=k+1
    j=size-1  

evidanary

# check if there is two integers which sum up to the targeted sum
def two_sum(arr, target)
  arr.sort!
  size = arr.size
  i, j = 0, size-1
  count = 0
  while(i<j) do
    sum = arr[i] + arr[j]
    if sum == target
    	count += 1

evidanary

# returns depth and node at the maximum depth
def max_depth(node)
  return [0, node] if node.nil?
  left = max_depth(node.left) + 1
  right = max_depth(node.right) + 1
  left[0] > right[0] ? left : right
ends

evidanary

def common_anc(root, p, q)
  return root if (root.nil? || p == root.val || q == root.val)
  left = common_anc(root.left, p, q)
  right = common_anc(root.right, p, q)
  left && right ? root : left || right
end

common_anc(head, 4, 5)

evidanary

# find if a tree is balanced
# i.e. no two nodes are more than 1 level away from root
# i.e. maxdepth - mindepth <= 1
def max_depth(root)
  return 0 if root.nil?
  return 1 + [max_depth(root.left) , max_depth(root.right)].max
end

def min_depth(root)
  return 0 if root.nil?

evidanary

#################TREES############
# The TreeNode Class
class Node
  attr_accessor :left, :right, :val
  def initialize(val)
    @val = val
    @left = nil
    @right = nil
  end
end