Make Lexicographically Smallest Array by Swapping Elements | Leetcode 2948

[@freecourseplatformenglish2829]

Seriously it is hard to beat you when its comes to explaining the intution. Thank you

[@techdose4u]

By God’s grace 🙏🏼

[@abhishekshukla5747]

This problem was tough , not easy to get the intution if solving for first time ! But your explainantion made it crystal clear sir

[@techdose4u]

yes

[@az-zm4ji]

WHAT A GREAT DUDE! I was able to come up wth the DSU approach but didnt code it as it looked too diffcult. This appraoch is just genius.

[@techdose4u]

👌🏽

[@BCS-IshtiyakAhmadKhan]

Best way to do this problem is to sort the array in decreasing order and maintain a adjacency list of groups .Now the elements in the adjacency list will also be sorted in decreasing fashion and as you travel in original array find the current element group(using hash)and remove the last element from that group in the adjacency list which will take O(1) time .Here's the code int n = nums.size(); vector v(nums); sort(v.begin(), v.end(), greater()); vector dsu(1); map mp; dsu[0].push_back(v[0]); mp[v[0]] = 0; int curr = 0; for (int i = 1; i < n; i++) { if (v[i - 1] - v[i] > limit) { dsu.emplace_back(); curr++; } dsu[curr].push_back(v[i]); mp[v[i]] = curr; } for (int i = 0; i < n; i++) { nums[i] = dsu[mp[nums[i]]].back(); dsu[mp[nums[i]]].pop_back(); } return nums;

[@heatedmuscle2329]

You are so smart. How are you so smart. I really really want to know. Thanks for providing this insight. Commented, Liked and Subscribed,

[@techdose4u]

👌🏽

[@virajmandlik-it9bj]

Insightful Explanation ....Thanks Sir..💯

[@techdose4u]

Welcome!

[@programming6177]

nice explanation, thank you bro😇

[@techdose4u]

welcome :)

[@BananaButcher]

Excellent explanation as always

[@techdose4u]

Appreciate it 😊

[@bhashitmaheshwari5205]

Just a Suggestion try to give Brute Better and Optimal Sol for Problems might Help us in Interviews,Thank You

[@techdose4u]

already explained selection sort right ?

[@bhashitmaheshwari5205]

@techdose4u yeah sure today you explained it I was talking in general sorry if i offended you in someway.

[@techdose4u]

@bhashitmaheshwari5205 No problem. I generally expect people to know bruteforce as its just simulation of goal :)

[@anantakesharipanda4085]

Instead of using two pointers to build the result vector, I was thinking of creating the result vectors of size nums by initializing it with zeroes, then create a map of groups where each Key will be the group index, and value will be vector of sorted indices from original vector. Then just traverse the sorted copy vector and place each element within same group within the index from the map’s values into the result vector initialised with zero. I know this not so space efficient, but this approach seemed more easy to visualise to me. 😅

[@shivnathkahar8985]

Excellent

[@techdose4u]

Thanks :)

[@nabihsara]

Thanks, and i was waiting you yesterday but you have solved late, I wish you solve every day early and thanks again for your effort and explanation

[@techdose4u]

I never solve the same day. I solve days before and predict the question to come. Yesterday’s prediction dint work out. Hence it was late :(

[@challengemania4447]

​@@techdose4u but how sir.. Do you have any ML algo to predict next question ?

[@rameshgoud2986]

@@challengemania4447 😂😂😂

[@sruthinteja4644]

How to do using unionfind

[@techdose4u]

Maintain multiple sets using disjojnt set array. Please follow my disjoint set video for clarity.

[@vbhv-gupta]

Time complexity of its Brute Force approach will be O(n^3) class Solution: def lexicographicallySmallestArray(self, nums, limit) : copy = None while copy != nums: # -> Loop 1 copy = nums.copy() for i in range(len(nums)): # -> Loop 2 best_idx = i for j in range(i+1,len(nums)): #-> Loop 3 if 0 < nums[i] - nums[j]

[@techdose4u]

yes

[@challengemania4447]

Can we able to do it in O(n^2).. I think we can do as usual comparing one element with each other. Will be this approach is brutefoecr ?

[@rameshgoud2986]

@@challengemania4447 no wont work

[@Ice-2706]

the custom selection sort would not work for every case. ex - [10, 4, 7], limit = 3 although the idea of swappable groups is awesome!

[@techdose4u]

yes it will require an extra loop

[@sailendrachettri8521]

Thank you sir :)

[@techdose4u]

welcome :)

[@UMESAURAVKUMAR]

The selection sort algo will break here: {10,3,5,8,2} , limit = 3 after first iteration: best value for 10 is 8 {8, 3, 5, 10, 2} after second iter: best value for 3 {8, 2,5,10,3} after 3rd iter: best value for 5 is 3 {8,2,3,10,5} after 4th iter: best value for 10 is no one in right {8,2,3,10,5} but the actual answer for this problem is : {2,3,5,8,10}

[@techdose4u]

Yes. One extra loop would be required if elements are in increasing order and we always happen to pick from right.

[@kshitijvarma2566]

This was hard to think of .... 😅

[@techdose4u]

yes

[@kthamim7552]

you are sorting a copy array as normal sort but why sir you are saying,you'r done a lexicographically sorting a copy array bit confusing in that line after finding a logic there is no doubt one is that you are using a normal sorting concept or anyother lexico sorts ?

[@techdose4u]

I dint understand your problem. Can you please mention a little more clearly possibly with example.

[@hhcdghjjgsdrt235]

10, 8 were green rest were yellow the idea clicked

[@techdose4u]

made for you :)