Relative Sort Array | Counting Sort | Using Lambda | Leetcode 1122 | codestorywithMIK

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

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

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

[suryasaipalthi]

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;
}
}

[rugung]

please make a videos on this Qn bhaiya🙏
3181. Maximum Total Reward Using Operations II
last LC contest ke DP optimisation ke hai

[nirbhaykaushik]

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.

[utkarshsahay]

class Solution {
public:
vector<int> arr1, vector<int>& arr2) {
vector<int> ans;
map<int, int> 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;
}
};❤❤

[MirOsamaAli]

Assalam u Alaikum, what about those constraints which are given like arr1<1000 etc
How are they getting satisfied?

[gauravbanerjee]

Thanks a lot bhaiya ❤❤ Congrats for 51k subs 🥳🥳

[jeehub]

Sir isme normal comparator sort kyu use nahi kar sakte?

[SaranshKasliwal]

MIK Bhaiya please Solve Contest 401-> Ques 4 ->LC-3181 it's on Dp using Bitset !

[nirmalgurjar]

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;
}
}

[nilayjain]

Please bring solution for 3175. Find The First Player to win K Games in a Row MIK Bhai!!!

[bishwashkumarsah]

bhaiya please do bi-weekly contest 132. 3176. Find the Maximum Length of a Good Subsequence I.

[nikhilhaspe]

// 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<1001; i++){
while(freq[i] > 0){
arr1[index] = i;
index++;
freq[i]--;
}
}

return arr1;
}
}

[youracademicfriend-shashwa]

Great Explanation !!

Also sir please cover leetcode 30. Substring with Concatenation of All Words

[kartikforwork]

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??

[mukulkriplani]

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

[vishwashsoni]

sir i solved this question like this:
class Solution {
public:
vector<int> arr1, vector<int>& 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;
}
};

[pokeindia]

Bhaiya please LC-32....
Please bhaiya

[dayashankarlakhotia]

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;j<cnt.length;j++)
while(cnt[j]>0){
ans[i++]=j;
cnt[j]--;
}
return ans;
}
This is count sort without lambada expression due to arr1.length in 1000; 🎉❤

[sinnohperson]

Can you do reverse nodes in k group

Its a hard question. The logic is easy but coding that it confusing

[abhisheksingh-rznj]

class Compare {
public:


Compare(unordered_map<int, int> &mpp) : mpp(mpp) {} //constructor

bool operator()(int before, int after) {
&& mpp.find(after)!=mpp.end()){
return mpp[before]<mpp[after];
}
else && mpp.find(after)==mpp.end()){
return true;
}
else && mpp.find(after)!=mpp.end()){
return false;
}
return before<after;
}
private:
unordered_map<int, int>& mpp;
};

Bhaiya ye hum aise Compare function ki class banakar bhi kar skte hai na ?
Mera code to work kiya hai
but
private:
unordered_map<int, int>& mpp;
ye kyu kiya pta nhi