Relative Sort Array | Counting Sort | Using Lambda | Leetcode 1122 | codestorywithMIK
Вставка
- Опубліковано 12 вер 2024
- Whatsapp Community Link : www.whatsapp.c...
This is the 42nd Video of our Playlist "Leetcode Easy : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve a good practice Array problem : Relative Sort Array | Counting Sort | Using Lambda | Leetcode 1122 | codestorywithMIK
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 : Relative Sort Array | Counting Sort | Using Lambda | Leetcode 1122 | codestorywithMIK
Company Tags : will update soon
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 Counting Sort
Time Complexity: O(n log n)
Space Complexity: O(n)
In this approach, we use a map (or TreeMap in Java) to count the occurrences of each element in arr1. The elements in arr2 are then placed in arr1 according to their counts, maintaining the relative order specified by arr2. After that, the remaining elements (those not in arr2) are added to arr1 in ascending order. This approach leverages the counting sort mechanism but also requires sorting the elements not in arr2, leading to the O(n log n) complexity.
Approach 2: Using Lambda for Custom Sorting
Time Complexity: O(n log n)
Space Complexity: O(n)
In this approach, an unordered_map (or HashMap in Java) is used to store the indices of elements in arr2. For elements not in arr2, a large value (1e9) is assigned to ensure they are sorted to the end. A lambda function (or comparator in Java) is defined to sort arr1 based on the indices stored in the map. If two elements have the same index, they are sorted by their natural order. The sorting operation uses the custom comparator, which maintains the relative order of elements in arr2 and sorts the rest in ascending order
✨ 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
please make a videos on this Qn bhaiya🙏
3181. Maximum Total Reward Using Operations II
last LC contest ke DP optimisation ke hai
replace map with vector to be cool
Great explanation mik bhaiya❤❤
Instead of using a hashmap can't we just use an array as the constraints are less (1000 only). I tried this and it works. Also i think the TC decreases to O(N)? Btw Lambda approach was clean!!
class Solution {
public int[] relativeSortArray(int[] arr1, int[] arr2) {
int res[] = new int[1001];
for(int i : arr1)
res[i]++;
int j = 0;
for(int i = 0; i < arr2.length; i++){
while(res[arr2[i]]--> 0){
arr1[j] = arr2[i];
j++;
}
}
for(int i = 0; i < 1001; i++){
while(res[i]--> 0){
arr1[j] = res[i];
j++;
}
}
return arr1;
}
}
Thanks a lot bhaiya ❤❤ Congrats for 51k subs 🥳🥳
Nice Concept !
Great Explanation !!
Also sir please cover leetcode 30. Substring with Concatenation of All Words
Can you do reverse nodes in k group
Its a hard question. The logic is easy but coding that it confusing
class Solution {
public:
vector relativeSortArray(vector& arr1, vector& arr2) {
vector ans;
map mp;
for(int n : arr1) mp[n]++;
for(int i = 0;i < arr2.size(); i++){
int k = mp[arr2[i]];
while(k--){
ans.push_back(arr2[i]);
}
mp.erase(arr2[i]);
}
if(ans.size() == arr1.size()) return ans;
for(auto it : mp){
int k = it.second;
while(k--){
ans.push_back(it.first);
}
}
return ans;
}
};❤❤
bhaiya please do bi-weekly contest 132. 3176. Find the Maximum Length of a Good Subsequence I.
Assalam u Alaikum, what about those constraints which are given like arr1
Lambda and comparator are same ???
Yes!
@@newglobal7271 Thanks!
i thought lambda function means function defines inside a function
Yes
@@user-ub2is4rs4x thanks 👍
Thanks
// Constant Space & Linear Time solution
// Java Solution:
// Count Sort in Java
class Solution {
public int[] relativeSortArray(int[] arr1, int[] arr2) {
int[] freq = new int[1001];
int index = 0;
for(int num : arr1){
freq[num]++;
}
for(int num : arr2){
while(freq[num] > 0){
arr1[index] = num;
freq[num]--;
index++;
}
}
for(int i=0; i 0){
arr1[index] = i;
index++;
freq[i]--;
}
}
return arr1;
}
}
nice....
sir i solved this question like this:
class Solution {
public:
vector relativeSortArray(vector& arr1, vector& arr2) {
int n = arr1.size();
int m = arr2.size();
int i = 0, j = 0;
while (i < n && j < m) {
int k = i + 1;
if (arr1[i] == arr2[j]) {
i++;
k++;
}
while (k < n) {
if (arr1[k] == arr2[j]) {
swap(arr1[i], arr1[k]);
i++;
}
k++;
}
j++;
}
sort(arr1.begin() + i, arr1.end());
return arr1;
}
};
Brother brute force smj me aata hai but code karne me kvi kvi problem ho taa hai .. wo code kar ke btaa do ge
Thanks.
Since arr[i] constraint is very low from 0 to 1000, we can use count sort without map very efficiently and can come with 0(n) solution.
class Solution {
public int[] relativeSortArray(int[] arr1, int[] arr2) {
int[] count = new int[1001];
for(int num : arr1){
count[num]++;
}
int[] op = new int[arr1.length];
int i = 0;
for(int num : arr2){
while(count[num] > 0){
op[i++] = num;
count[num]--;
}
}
int countIdx = 0;
while(countIdx < 1001){
while(count[countIdx] > 0){
op[i++] = countIdx;
count[countIdx]--;
}
countIdx++;
}
return op;
}
}
solved on my own yet came to watch!
bhaiya ye lamda ke upar koi video hai to bahj do,
aur aap
sort(num.begin(),num.end()) ki jagha sort(begin(num),end(num))
likte ho, ky farak hai??
Dono same hai
lambda aur custom comparator same hai
You can refer to his C++ STL playlist. I think maine usi playlist me dekha tha lambda
Great video 👌🏻
thanks a lot
isn't lambda approach more slower or is that leetcode issue ?
1. we can write 1e9 in java too, we just have to typecast from double to int --- int largeIndex=(int)1e9;
2. we can even 1001 as index as that's the max limit
3. we don't need to use extra space using arrayList , just a simple array with an index counter works fine
btw
minor typo in your github file
for java code also ur comment says c++
/******************************************************************************** C++ ********
saw that in past videos also :D
MIK Bhaiya please Solve Contest 401-> Ques 4 ->LC-3181 it's on Dp using Bitset !
Noiceee
Lambda is cool
class Compare {
public:
Compare(unordered_map &mpp) : mpp(mpp) {} //constructor
bool operator()(int before, int after) {
if(mpp.find(before)!=mpp.end() && mpp.find(after)!=mpp.end()){
return mpp[before]
Sir isme normal comparator sort kyu use nahi kar sakte?
Yes it can be used
Please bring solution for 3175. Find The First Player to win K Games in a Row MIK Bhai!!!
Binary search be the third way 🤠
Bhaiya please LC-32....
Please bhaiya
Bhaiya Leetcode-32 karwa do bhaiya
public int[]relativeSortArray (int[]arr1,int[]arr2){
int[]cnt=new int[1001];
for(int i:arr1)
cnt[i]++;
int[]ans=new int[arr1.length];
int i=0;
for(int num:arr2)
while(cnt[num]>0){
ans[i++]=num;
cnt[num]--;
}
for(int j=0;j0){
ans[i++]=j;
cnt[j]--;
}
return ans;
}
This is count sort without lambada expression due to arr1.length in 1000; 🎉❤
bhaiya please make a video on bi-weekly contest 132. 3176. Find the Maximum Length of a Good Subsequence II. Please react or reply if you have read this comment bhaiya
Java Comparators are pretty bad.
"The method sort(int[]) in the type Arrays is not applicable for the arguments"
:)
public int[] relativeSortArray(int[] arr1, int[] arr2) {
HashMap map = new HashMap();
for(int i=0; i {
if (map.containsKey(a) && map.containsKey(b)) {
return Integer.compare(map.get(a), map.get(b));
} else if (map.containsKey(a)) {
return -1;
} else if (map.containsKey(b)) {
return 1;
} else {
return Integer.compare(a, b);
}
});
}