Least Number of Unique Integers after K Removals | 3 Approaches | Greedy | Leetcode 1481
0Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
This is the 27th Video of our Playlist "Greedy : Popular Interview Problems".
We will try to understand the thought process behind solving such Qns.
Problem Name : Least Number of Unique Integers after K Removals | Leetcode 1481
Company Tags : Amazon
My solutions on Github : https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Greedy/Least%20Number%20of%20Unique%20Integers%20after%20K%20Removals.cpp
Leetcode Link : https://leetcode.com/problems/least-number-of-unique-integers-after-k-removals/
Approach Summary :
Approach-1 (Using Map and Sorting): This approach uses an unordered_map to count the frequency of each element in the input array. Then, it creates a vector of frequencies, sorts it, and iterates through the sorted frequencies while decrementing the removal count. The process continues until the removal count becomes non-positive, and the remaining unique elements are returned.
Approach-2 (Using min-heap): Similar to Approach-1, this approach uses an unordered_map to count element frequencies. However, instead of sorting, it utilizes a min-heap (priority_queue) to keep track of frequencies. It iteratively pops the smallest frequencies from the heap and updates the removal count until it becomes non-positive, then returns the size of the heap.
Approach-3 (Using Counting Sort): This approach counts the frequency of each element and uses counting sort to create an array (freqCount) representing the count of elements with a specific frequency. It then iterates through the frequencies, calculating the number of unique elements to remove based on the removal count (k). The process continues until the removal count is exhausted, and the remaining unique elements are returned. The counting sort results in a linear time complexity.
My Recursion Concepts Playlist : https://www.youtube.com/watch?v=pfb1Zduesi8&list=PLpIkg8OmuX-IBcXsfITH5ql0Lqci1MYPM
My DP Concepts Playlist : https://youtu.be/7eLMOE1jnls
My Graph Concepts Playlist : https://youtu.be/5JGiZnr6B5w
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Interview_DS_Algo
Subscribe to my channel : https://www.youtube.com/@codestorywithMIK
Instagram : https://www.instagram.com/codestorywithmik/
Facebook : https://www.facebook.com/people/codestorywithmik/100090524295846/
Twitter : https://twitter.com/CSwithMIK
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ Timelines✨
00:00 - Introduction
0:18 - Problem Explanation
5:52 - Approach-1 Intuition
9:10 - Time and Space Complexity of Approach-1
9:58 - Important Note
12:51 - Coding Approach-1
14:50 - Approach-2 Explanation
16:39 - Time and Space Complexity of Approach-2
17:52 - Coding Approach-2
19:41 - Approach-3 Detailed Explanation
39:45 - Coding Approach-3
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #2024 #newyear