Minimum Increment to Make Array Unique | Sorting | Counting Sort | Leetcode 945 | codestorywithMIK
Вставка
- Опубліковано 26 сер 2024
- Whatsapp Community Link : www.whatsapp.c...
This is the 34th Video of our Playlist "Greedy Technique : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve a good practice greedy sorting Problem : Minimum Increment to Make Array Unique | Sorting | Counting Sort | Leetcode 945 | codestorywithMIK
We will specifically see why a normal Greedy approach will fail and why we go with the Backtracking Approach for this problem.
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Minimum Increment to Make Array Unique | Sorting | Counting Sort | Leetcode 945 | codestorywithMIK
Company Tags : will soon update
My solutions on Github(C++ & JAVA) : github.com/MAZ...
Leetcode Link : leetcode.com/p...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My Recursion Concepts Playlist : • Introduction | Recursi...
My GitHub Repo for interview preparation : github.com/MAZ...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
Approach 1: Using Sorting
Time Complexity: O(nlogn)
Space Complexity: O(1)
Steps:
Sort the array nums.
Initialize a variable moves to keep track of the number of increments.
Iterate through the sorted array starting from the second element.
For each element, if it is not greater than the previous element, increment it to make it unique and update moves with the number of increments made.
Return the total number of moves.
Pros:
Simple and easy to understand.
Efficient for small to moderately sized arrays.
Cons:
Requires sorting the array, which may not be optimal for very large arrays.
Approach 2: Using Counting Sort
Time Complexity: O(n+maxVal)
Space Complexity: O(n+maxVal)
Steps:
Find the maximum value in the array to determine the size of the counting array.
Initialize a counting array count of size n+maxVal.
Populate the count array with the occurrences of each value in nums.
Iterate through the count array to ensure all values are unique:
If the count of any value is more than 1, move the excess to the next value and update moves accordingly.
Return the total number of moves.
✨ Timelines✨
00:00 - Introduction
#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 #newyear2024
00:01 Minimum Increment to Make Array Unique
02:01 Use sorting to minimize increments and make array unique
05:56 Increase minimum to make elements unique
07:51 Using sorting to minimize duplicate elements for array uniqueness
12:11 Explaining frequency increment and adding extra one for unique array
14:02 Increment the array elements to make them unique
17:54 Explaining the process of making array elements unique using counting sort method.
19:33 Understanding the frequency and adjustments for array uniqueness
22:47 Understanding the frequency of array elements for incrementing
24:23 Updating array elements to make them unique.
28:01 Optimal approach to solve Leetcode 945 using counting sort
Apke samjhane ka tarika itna acha hai ki apke aik testcase ke explain krte hi logic click ho gya.
Bhai app coding ke GOD ho.
following the channel from 5k followers, now your content have massive impact. if I can solve a problem then also still come here to learn different approaches
You are the GOAT of DSA explanation
No doubt
hashmap approach was nice mik bhaiya
but it gave tle
you are a great teacher. your calmness while teaching is worth appreciating
My initial thought process was of using Next Greater to Left & Next Greater to Right concepts, & did dry run as per below written code for the test cases, [1,2,2], [3,2,1,2,1,7] & [4,4,4,4,4]. According to the dry run, I got the correct answers, but when I run the test cases on leetcode, I get correct output for [1,2,2], but for [3,2,1,2,1,7] & [4,4,4,4,4], it shows output of 4, which is wrong. My dry run (as per the same code) yielded correct answer, but on running on platform, it fails. Can anyone help me address this issue ? The code is :
class Solution {
private:
vector NGR(vector& arr, int n){
stack st;
vector result(n, -1);
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() && st.top()
Solved this on my own with the first approach. But the second approach was great. Thanks for that !
i did it without modifying the data values
class Solution {
public:
int minIncrementForUnique(vector& nums) {
int mini = -1;
sort(nums.begin(),nums.end());
int n = nums.size();
int ans = 0;
for(int i = 0;i
hats off to your consistency
sir please make more videos on other topics like concepts of bit manipulation, and a video of shortest path in graphs all variation. leetcode daily are very basic nowadays.
waiting for thiss videoo whole day,thankyouu!!
Love the way you explain
2nd wala approach mast tha. thank you.
Thanks a lot. I was able to solve using sorting. But wanted to understand counting sort approach. It was tricky but understood finally
I had a doubt but while typing my doubt in the comment section, I got the answer myself😅
😂
I was able to solve this on my own. Counting sort wala approach mast tha
can you bring the course on dsa the way you expalin ht cocept is amzazing i have seen your recursion,bit manupliation,binary search playlist
Second approach to khud se bn gyi seekhra hu aapse
#define ll long long
class Solution{
public:
int minIncrementForUnique(vector& nums) {
sort(nums.begin(), nums.end());
const ll MAX = 1e7;
bitset bn;
signed int c = 0;
for(size_t i = 0; i < nums.size(); i++){
while(bn[nums[i]]){
nums[i]++;
c++;
}
bn.set(nums[i]);
}
return c;
}
};
this is also woking
Second approach op!
I really like your explanation. can you please share video for this problem 642. Design Search Autocomplete System
Sir plz add ipad notes also for every video. I have been taking screenshot for revision
mik bhaiya you are great
Mik bhai mere dimag mein pehele aaya tha ki array ko sort karenge, Usk baad map mein frequency store Kar lenge, fir array ko traverse karunga, aur ek ek number ka frequency check Karunga, agar frequency > 1 hua, to usko ek temp mein store karke increment karunga tab tak jab tak wo element map mein present na ho, aur Jo element aayega, usko us index mein dal denge
i thought the same but this solution is not optimised it will take O(n2)
@soumyamakkar4677 yes
Maine bhi same try kiya but TLE aaya. Vo n2 jaa raha hai
Same 😢
Thankyouuuuuuuuuuu!
plz make more videos on dp plz
Bhaiya *longest valid parantheses* par video vanaiye please...
Thank you!
I had a doubt! Why did we prefer array over a map? if we see space complexity, both will be O(N) then why array?
Very helpful
Amazing!
arey bhai mauj
I was able to get the 2nd solution own my own but when I coded in java, I was getting concurrentModificaiton error as while iterating the we are modifying the map so getting error, I also thought of counting sort but checking 10^5 size that is why did not try for it
sir , I encountered a similar problem in which cost was also given to increment a number and we need to make all elements unique in min cost.
I tried this but couldn't do in less than O(n^2). can you please give any idea?
few doubts, please answer
1. HashMap approach, i had tried doing something similar int the morning, I was facing conurruent update issue, as I was reading the current value of the map and updating element, but there is one iteraor approach for this which I will try now
2. in the last loop, we are running the loop till < count.length , meaning it will go till the the last length, and accessing the i+1 index, there can't be any scenario where this might cause issues ?
Please use white theme of leetcode, visibility of code in the black theme is less .
nope, increase quality
why can't we take arraylist instead of array to handle the size of counting sort array?
upload the solution of lc contest also if possible
in second approach can we use map?
nice
hey, so we are initialising the size of the array based on the size of nums. but aisa ho ki agar hamara array sirf 10 places ka ho and uss mein elements hai wo 15 16 ho to uss mein hashing mein bhi problem aayegi and buffer overflwo bhi to ho sakta
look carefully, we are initialising size of array as (nums.size() + maxElement)
instead of using vector for storing frequency , i am using unordered map, but i am getting wrong answer
class Solution {
public:
int minIncrementForUnique(vector& nums) {
unordered_map mp;
for(auto i : nums)
{
mp[i]++;
}
int ans=0;
for(auto &[x,y]: mp)
{
if(y>1)
{
int extra= y-1;
mp[x]=1;
ans+=extra;
mp[x+1]=extra;
}
}
return ans;
}
};
dono approach socha tha lekin first wala code kr paya second wala nhi
I solved it using set
It is giving TLE😢
pls pin:
save space in last approach to only using mxelement space-
how?
let say we got 3 freq at max element, the what mik is doing?
taking 2 of 3 freq and move it to next element.
then take 1 out of 2 freq and move it to next element.
but isn't it like sequence 2-1 sum of first n numbers
so we just need the extra freq at the max element and apply moves + sum_of (last_element_freq-1 to 1).
my code- ( see last 2 lines )
class Solution {
public:
int minIncrementForUnique(vector& nums) {
sort(nums.begin(),nums.end());
int mxelement=*max_element(nums.begin(),nums.end());
vector freq(mxelement+1,0);
for(int i=0;i
Please reply mik bhai
I know it is very bad approach, but I want to try, I want to build logic like you, but not clicked, can you help me? How to build logic like you
practice and practice and practice
@@EB-ot8uucan you also practice the solved problems
public int minIncrementForUnique(int[]nums){
int max=0,n=nums.length;
for(int num:nums)
max=Math.max(max,num);
int[]freq=new int[max+n];
for(int ele:nums)
freq[ele]++;
int ans=0;
for(int i=0;i
Bhaiya maine ek sol kiya hai usme memoisation me prob aari hai koi help nahi karra can you help…
Leetcode 3177
class Solution {
public:
int dp[5010][55][5010];
int f(int i,vector&a,int k,int lst){
if(i==a.size())return 0;
if(dp[i][k][lst+5]!=-1)
return dp[i][k][lst+5];
int ans=-1e5;
if(lst == -1 || a[lst]== a[i]){
ans =max(ans, 1 + f(i+1,a,k,i));
}
else{
if(k){
ans =max(ans, 1+f(i+1,a,k-1,i));
}
}
ans =max(ans,f(i+1,a,k,lst));
return dp[i][k][lst+5]=ans;
}
int maximumLength(vector& a, int k) {
memset(dp,-1,sizeof dp);
return f(0,a,k,-1);
}
};
Can somebody share the map approach code in java?
public static int minIncrementForUnique2(int[] nums) {
TreeMap map = new TreeMap();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i])) {
map.put(nums[i], map.get(nums[i]) + 1);
} else {
map.put(nums[i], 1);
}
}
//at this line the map is giving error as the map is dynamically increased
for (Map.Entry entry : map.entrySet()) {
int curr = entry.getKey();
Integer freq = map.get(curr);
if (freq > 1) {
map.put(curr + 1, map.getOrDefault(curr + 1, 0) + freq - 1);
map.put(curr, 1);
}
}
return map.size();
}
are you gujrati ?
muje bhi aesa hi laga ki vo sayad gujarati ho sakte he jab unhone " aaju baju " bola 😄
No I am not Gujrati. But I love the place and accent ❤️❤️❤️
I solved it using vector