Leetcode: Heaps

Question 1

List of strategies for heap problems

Answer 1

Anything with N largest usually has some sort of heap brute force solution, K largest nums in array has this, but quick select is faster
Heaps are great for algorithms where you need to pop off the min item such as modified dijkstra’s algorithm and path with min effort question

Question 2

Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:

Input: nums = [1], k = 1
Output: [1]

Answer 2

heapq solution time N log(k) where k is the size of the heap, N is the length of array, space would be N for the size of the hashmap, custom solution would be N log(N) bc you do a binary search on each item in the hashmap

1. quickselect, find kth something”: kth smallest, kth largest, kth most frequent, kth less frequent, etc.
2. create list of keys, during quick select map those keys to the hashmap values when sorting
3. know quick select!!! base case is left == right

time: worst case N^2, average is N if you use a random pivot. worst case comes from if each pivot is the largest number
space: N, size of the hashmap, logN for recursion stack if we split in half, worst case that would be N too

from collections import defaultdict
import random
class Solution:
—-def quick_select_solution(self, nums, k):
——–self.frequency_dict = defaultdict(lambda: 0)
——–for x in nums:
————self.frequency_dict[x] += 1
————
——–self.keys = list(self.frequency_dict.keys())
————
——–n = len(self.keys)
——–
——–self.quick_select(0, n - 1, n - k)
——–
——–return self.keys[n-k:]
——–
————
—-def partition(self, left, right, pivot):
——–self.keys[pivot], self.keys[right] = self.keys[right], self.keys[pivot]
——–# Remember that you need to use the RIGHT index NOT PIVOT since you just wapped pivot
——–val = self.frequency_dict[self.keys[right]]
——–low = left
——–for i in range(left, right):
————if self.frequency_dict[self.keys[i]] [less than] val:
—————-self.keys[i], self.keys[low] = self.keys[low], self.keys[i]
—————-low += 1
——–self.keys[low], self.keys[right] = self.keys[right], self.keys[low]
——–
——–return low
—-
—-def quick_select(self, left, right, k):
——–if left == right:
————return
——–
——–pi = random.randint(left, right)
——–pi = self.partition(left, right, pi)
——–
——–if pi == k:
————return
——–elif pi [less than] k:
————return self.quick_select(pi + 1, right, k)
——–else:
————return self.quick_select(left, pi - 1, k)

• —def topKFrequent(self, nums, k: int):
• ——-import heapq
• ——-frequency_dict = defaultdict(lambda: 0)
• ——-for x in nums:
• ———–frequency_dict[x] += 1
• ——-return heapq.nlargest(k, frequency_dict.keys(), frequency_dict.get)
• —def my_custom_solution(self, nums, k):——–
• ——-frequency_dict = defaultdict(lambda: 0)
• ——-for x in nums:
• ———–frequency_dict[x] += 1
• ——-response_key = []
• ——-response_value = []
• ——-for key, value in frequency_dict.items():
• ———–index = self.binary_search(response_value, value)
• ———–response_key.insert(index, key)
• ———–response_value.insert(index, value)
• ——-return response_key[-k:]
• —def binary_search(self, arr, target):
• ——-if len(arr) == 0:
• ———–return 0
• ——-low = 0
• ——-high = len(arr) - 1
• ——-while high [greater than]= low:
• ———–mid = (high + low) // 2
• ———–if target == arr[mid]:
• —————return mid
• ———–elif target [less than] arr[mid]:
• —————high = mid - 1
• ———–else:
• —————low = mid + 1
• ——-return low