Day 20 of 30 days of Data Structures and Algorithms and System Design Simplified — Heap/Priority Queue
Welcome back peeps. Hope all’s well. In this post we will cover Backtracking technique as follows —
What and Why Heap/Priority Queue(in 2–3 sentences)?
How does Heap/Priority Queue work?
Important Patterns and Techniques in Heap/Priority Queue Questions
Most Important Questions with Solutions
Tips and Techniques to solve Heap/Priority Queue Questions Fast.
Projects Videos —
All the projects, data structures, SQL, algorithms, system design, Data Science and ML , Data Analytics, Data Engineering, , Implemented Data Science and ML projects, Implemented Data Engineering Projects, Implemented Deep Learning Projects, Implemented Machine Learning Ops Projects, Implemented Time Series Analysis and Forecasting Projects, Implemented Applied Machine Learning Projects, Implemented Tensorflow and Keras Projects, Implemented PyTorch Projects, Implemented Scikit Learn Projects, Implemented Big Data Projects, Implemented Cloud Machine Learning Projects, Implemented Neural Networks Projects, Implemented OpenCV Projects,Complete ML Research Papers Summarized, Implemented Data Analytics projects, Implemented Data Visualization Projects, Implemented Data Mining Projects, Implemented Natural Leaning Processing Projects, MLOps and Deep Learning, Applied Machine Learning with Projects Series, PyTorch with Projects Series, Tensorflow and Keras with Projects Series, Scikit Learn Series with Projects, Time Series Analysis and Forecasting with Projects Series, ML System Design Case Studies Series videos will be published on our youtube channel ( just launched).
Subscribe today!
System Design Case Studies — In Depth
Design Instagram
Design Messenger App
Design Twitter
Design URL Shortener
Design Dropbox
Design Youtube
Design API Rate Limiter
Design Web Crawler
Design Facebook’s Newsfeed
Design Yelp
Design Uber
Design Tinder
Design Tiktok
Design Whatsapp
Most Popular System Design Questions
Mega Compilation : Solved System Design Case studies
Heap/Priority Queue
Importance : High
Note : New Heap/Priority Queue questions with solutions are added every day. So keep checking this post daily.
Let’s dive in!
What is Heap/Priority Queue?
A heap is a data structure which is a binary tree having following properties —
It’s a complete binary tree — each level is completely filled, except the last level. At the last level, the elements are inserted left to right.
Satisfies the heap order property — the element stored in the each node is greater than or equal to the element stored in its children i.e parent’s key is less than children’s key.
Minimum is always at the top.
Examples of Heap/Priority Queue problems —
K closet points to Origin
Cheapest flights within K stops
Find K closest elements
Kth smallest element in the sorted matrix
Kth Largest Element in the Array
Top K Frequent Element
How does Heap/Priority Queue work?
Heaps work by organizing the elements in a binary tree structure, where each node has a value that is greater than or equal to (in a max heap) or less than or equal to (in a min heap) the values of its children. The element with the highest priority is always stored at the root of the heap, and can be efficiently accessed or removed using basic binary tree operations such as insertion, deletion and heapify.
It works as per the heap order property. For Max heap —
- Insert an element at the end of the tree.
- Heapify the tree — the element at the top/root should be max of all the elements present in the binary heap.
Main Binary heap operations —
binaryheap() — To create a new heap
heapify(list of elements) — To build a new heap from a list of elements
insert(element) — add an element to the heap
delete() — Returns the element with min key value and removes the elemnt from the heap
getmin() — Returns an element with minimum key value ( it doesnt remove the element from the heap)
checkEmpty() — To check if the heap is empty or not. Returns true if the heap is empty.
size() — Returns the count of elements in the heap
Important Patterns and Techniques in Heap/Priority Queue Questions
Some important patterns and techniques in heap/priority queue questions include understanding the properties of a heap, such as the shape property and the heap-order property, and being able to implement basic heap operations such as insertion, deletion, and heapify.
Most of the heap questions have following pattern/ask —
K top or frequent elements
K largest element
K min element
Ranks or priority
Frequency of the elements
Kth closest points
K stops and flights
K jobs and CPU time etc
Most Important Questions with Solutions
Note : New Heap/Priority Queue questions with solutions are added every day. So keep checking this post daily.
Golden rule is — Learn by doing/implementing
In this we will see most important Heap/Priority Queue questions.
Kth Largest Element in an Array
Question —
Given an integer array nums and an integer k, return the kth largest element in the array.
Note that it is the kth largest element in the sorted order, not the kth distinct element.
Example :
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5Solution :
Implementation —
def findKthLargest(self, nums: List[int], k: int) -> int:
k=len(nums)-k
def qS(left,right):
pv,p = nums[right], left
for i in range(left,right):
if nums[i] <= pv:
nums[p],nums[i] = nums[i], nums[p]
p +=1
nums[p],nums[right] = nums[right],nums[p]
if p>k: return qS(left,p-1)
elif p<k : return qS(p+1,right)
else: return nums[p]
return qS(0,len(nums)-1)Question Link
Similar Pattern —
Find the Kth Largest Integer in the Array
Find Subsequence of Length K With the Largest Sum
K Highest Ranked Items Within a Price Range
Kth Largest Element in a Stream
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Top K Frequent Elements
Question —
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Example :
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]Solution :
Main Logic/Idea —
The main logic is to keep a count of the frequency of the number in the array into the dictionary. Match the count with k and the answer.
Implementation —
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
countFreq, frequency,ans = {},[[] for i in range(len(nums)+1)],[]
for no in nums:
countFreq[no] = 1+ countFreq.get(no,0)
for key,value in countFreq.items():
frequency[value].append(key)
for i in range(len(frequency)-1,0,-1):
for no in frequency[i]:
ans.append(no)
if len(ans) == k:
return ansQuestion Link
Similar Pattern —
Split Array into Consecutive Subsequences
Sender With Largest Word Count
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Sliding Window Maximum
Question —
You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.
Example :
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]Solution :
Main Logic/Idea —
For the current window, use two pointers left and right ( initialized to start of the array/list) and insert the values in the queue until you find a value greater than previous values. Once you find a value greater than previous values in the queue, start removing them and whatever value is left in the queue put in the output list. Next slide the window by one ( to the size of k)
Implementation —
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
ans, lptr,rptr = [],0,0
qu = collections.deque()
while rptr < len(nums):
while qu and nums[rptr] > nums[qu[-1]]:
qu.pop()
qu.append(rptr)
if qu[0] < lptr:
qu.popleft()
if k <= (rptr + 1):
ans.append(nums[qu[0]])
lptr += 1
rptr += 1
return ansQuestion Link
Similar Pattern —
Longest Substring with At Most Two Distinct Characters
Maximum Number of Robots Within Budget
Full Code Video Explanation ( In progress. Subscribe today for updates) :
Note : New Heap/Priority Queue questions with solutions are added every day. So keep checking this post daily.
Complexity Analysis
Before reading this section of the post, go through complexity analysis post.
For Heap -
Add the element — O(logN)
Get the max element — O(1)
Get the min element — O(1)
Remove the max element — O(logN)
Remove the min element — O(logN)
Tips and Techniques to solve Heap/Priority Queue Questions Fast.
Most important things you should know before solving heap questions are —
- How to create a heap.
- Heapify property ( and how to implement it from the scratch).
- How to reshuffle the elements to satisfy heap order property.
- Know how sliding window works.
- Know how recursion works.
That’s it for now. Day 21 : Intervals technique coming soon !
Let me know if you have questions in the comment section below. Subscribe/ Follow, Like/Clap as it will encourage me to write more in my free time and Stay Tuned!!
Read More —
11 most important System Design Base Concepts
6. Networking, How Browsers work, Content Network Delivery ( CDN)
13. System Design Template — How to solve any System Design Question
Some of the other best Series —
30 days of Data Structures and Algorithms and System Design Simplified
Data Science and Machine Learning Research ( papers) Simplified **
100 days : Your Data Science and Machine Learning Degree Series with projects
Complete Data Visualization and Pre-processing Series with projects
Exceptional Github Repos — Part 1
Exceptional Github Repos — Part 2
Tech Newsletter —
If you are interested, you can join my newsletter through which I send tech interview tips, techniques, patterns, hacks — Software Development, ML, Data Science, Startups and Technology projects to more than 30K readers. You can subscribe to Tech Brew :
For Python Projects —
For complete 60 days of Data Science and ML : Day 1 — Day 60 : Quick Recap of 60 days of Data Science and ML
Follow for more updates. Stay tuned and keep coding!
For other projects, tune to —
Build Machine Learning Pipelines( With Code)
Recurrent Neural Network with Keras
Clustering Geolocation Data in Python using DBSCAN and K-Means
Facial Expression Recognition using Keras
Hyperparameter Tuning with Keras Tuner
Custom Layers in Keras
