Snippets Collections
#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
star

Tue Aug 09 2022 23:23:42 GMT+0000 (Coordinated Universal Time) https://www.educative.io/courses/grokking-the-coding-interview/RM535yM9DW0

#python #heap #top #k #max

Save snippets that work with our extensions

Available in the Chrome Web Store Get Firefox Add-on Get VS Code extension