Day 31 of Studying LeetCode until I Can Solve One on My Own: #1481. Least Number of Unique Integers after K Removals(M/JS)

Intro: I am a former accountant turned software engineer graduated from coding bootcamp. Algorithms and Data Structure is an unavoidable part of interviews for most of the tech companies now. And one of my friends told me that you need to solve a medium leetcode problem under 60 seconds in order to get into the top tech companies.So I thought I'd start learning how to do it while job searching.

Since I have no clue on how to solve any of the problems (even the easy ones), I thought there is no point for me to waste hours and can't get it figured out. Here is my approach:

• Pick a leetcode problem randomly or Online Assessment from targeted companies.
• Study 1-2 solutions from Youtube or LeetCode discussion section. One brute force solution, another one more optimal.
• Write a blog post with detailed explanation and do a verbal walk through to help understand the solutions better.
• Code out the solution in LeetCode without looking at the solutions
• Combat the forgetting curve: Re-do the question for the next three days. And come back regularly to revisit the problem.

---

1481. Least Number of Unique Integers after K Removals
Difficulty: Medium Language: JavaScript

Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.

Example 1:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.

Example 2:

Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: Remove 4, 2 and either one of the two 1s or three 3s.
1 and 3 will be left.

Constraints:

• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 10^9
• 0 <= k <= arr.length

---

Solution:

1. Use a map to count the frequencies of the numbers in the array.
2. Remove the numbers with the smallest count first.

var findLeastNumOfUniqueInts = function(arr, k) {
    let frequency = {}, uiqueInt=0

//Initial a map to count the frequencies of the numbers in the
//array. Also initial "uniqueInt" to keep count of unique integers. 

    for(let i = 0;i < arr.length;i++){

//Loop (note 1) through each interger in the array

        if(!frequency[arr[i]]){

//If the ith element in the array does NOT exsit in the map

            frequency[arr[i]] = 0

//initial the count for the ith element in the map

            uiqueInt++

//When new element is added in the map, increate the count of the
//unique element.

        }
        frequency[arr[i]]++

//If the ith element exists in the map, increase the frequency of
//that element.

    }

        let sortedFreq = Object.entries(frequency).sort((a,b)=>
{return a[1]-b[1]})

//sort the frequency map created from steps above in ascending
//order

    for(let i = 0;i < sortedFreq.length;i++){

//Loop through the sorted frequency map

        if(k >= sortedFreq[i][1]){

//If k is greater or equal to the frequency of the element

            k=k-sortedFreq[i][1]

//Subtract the frequency of that element from k. That means we
//made k moves to remove all of that element entirely.

            uiqueInt--

//Once removed, reduce the count for unique interger

        }else{
            break;

//if update k is less than frequency than any of the remainding
//element, break out of the loop. That means the element will
//still exist in the array even if we make k moves.

        }
    }
    return uiqueInt

//Return the number of unique interger(s).

};

Time Complexity: O(nlogn)
Space Complexity: O(n)

---

References:
LeetCode Problem Link
LeetCode Discussion: Suyash1798
Note 1: for loop
Blog Cover Image Credit