#solution involving minHeap 
#Strategy: 
#1) Take out the smallest number from the heap, and
#2) Insert the larger number into the heap.
#3) repeat 
#This will ensure that we always have ‘K’ largest numbers in the heap. The most efficient way to repeatedly find the smallest number among a set of numbers will be to use a min-heap.


#Big O n log k. Space: O (k) 

from heapq import *
#this is a heap library. look at relevant functions: https://docs.python.org/3/library/heapq.html 


def find_k_largest_numbers(nums, k):
  minHeap = []
  # put first 'K' numbers in the min heap
  for i in range(k):
    heappush(minHeap, nums[i])

  # go through the remaining numbers of the array, if the number from the array is bigger than the
  # top(smallest) number of the min-heap, remove the top number from heap and add the number from array
  for i in range(k, len(nums)):
    if nums[i] > minHeap[0]:
    #heapop removes smallest element in heap 
      heappop(minHeap)
      heappush(minHeap, nums[i])

  # the heap has the top 'K' numbers
  return minHeap


#brute force approach has big O of n log N 
def find_k_largest_numbers(nums, k):
  result = []
  
  nums.sort() 
  nums_length_index = len(nums) - 1 - k 

  for i in range(nums_length_index + 1, len(nums)): 
    result.append(nums[i]) 
  
  return result

find_k_largest_numbers([3, 1, 5, 12, 2, 12], 3) # will result in [5, 12, 12] 


#if you dont want duplicates you can do the following: 
def find_k_largest_numbers(nums, k):
  result = []
  
  nums.sort() 
  nums_set = set(nums)
  nums_length_index = len(nums_set) - 1 - k 

  for i in range(nums_length_index + 1, len(nums_set)): 
    result.append(nums[i]) 
  
  return result

class Tree(object):
  def __init__(self, x, left=None, right=None):
    self.value = x
    self.left = left
    self.right = right 

x = Tree(1, Tree(0, Tree(1), Tree(3)), Tree(4))


def solution(t): 
    if not t: 
        return 0 
    
    stack = [(t, 0)]
    branchesSum = 0 
    
    while stack: 
        node, v = stack.pop() 
        if node.left or node.right:
        #depth first search 
        # the v is a little confusing to understand but easier to see in python tutor 
        # it goes from 1 to 10 to 100 etc. based on the height of the branch 
        # can probably do something like str() and converting back to int() as well 
            if node.left: 
                stack.append((node.left, node.value + v * 10)) 
            if node.right: 
                stack.append((node.right, node.value + v * 10)) 
        else: 
            branchesSum += node.value + v * 10 
    return branchesSum 

#
# Binary trees are already defined with this interface:
# class Tree(object):
#   def __init__(self, x):
#     self.value = x
#     self.left = None
#     self.right = None
import math 
def solution(t):
    if t is None: return [] 
    
    stack = [t] 
    result = []
    
    while len(stack) > 0: 
        result.append(max(tree.value for tree in stack)) 
        next_row = [tree.left for tree in stack if tree.left] + [tree.right for tree in stack if tree.right]
        stack = next_row 
    return result 


 #1. Add max value of ‘stack’ to result. 2. Create a new list of all next values for each value in stack. 3. redefine stack to this newly made list. 4. repeat 


#alternate solution 
def solution(t):
    largestValues = []
    q = []
    height = 0
    if t:
        q.append([t, height])
        while q:
            item = q.pop()
            node = item[0]
            currentHeight = item[1]
            if node.left:
                q.insert(0, [node.left, currentHeight + 1] )
            if node.right:
                q.insert(0, [node.right, currentHeight + 1])
            checkLargest(node.value, currentHeight, largestValues)
            
    return largestValues
    
        
def checkLargest(value, height, largestValues):
    if height == len(largestValues):
        largestValues.append(value)
    else:
        if largestValues[height] < value:
            largestValues[height] = value

class Solution{
    
    // Function to find largest and second largest element in the array
    public static ArrayList<Integer> largestAndSecondLargest(int sizeOfArray, int arr[])
       {
           //code here.
           int largest=-1;
           int sec_largest=-1;
           for(int i=0;i<sizeOfArray;i++)
           {
               largest = Math.max(largest,arr[i]);
           }
           for(int i=0;i<sizeOfArray;i++)
           {
               if(arr[i]<largest)
               {
                   sec_largest= Math.max(sec_largest,arr[i]);
               }
           }
           ArrayList<Integer> al = new ArrayList<Integer>(2);
           al.add(largest);
           al.add(sec_largest);
           return al;
       }
    }
}

/**
 * Returns a random number between min (inclusive) and max (exclusive)
 */
function getRandomArbitrary(min, max) {
    return Math.random() * (max - min) + min;
}

/**
 * Returns a random integer between min (inclusive) and max (inclusive).
 * The value is no lower than min (or the next integer greater than min
 * if min isn't an integer) and no greater than max (or the next integer
 * lower than max if max isn't an integer).
 * Using Math.round() will give you a non-uniform distribution!
 */
function getRandomInt(min, max) {
    min = Math.ceil(min);
    max = Math.floor(max);
    return Math.floor(Math.random() * (max - min + 1)) + min;
}