Make Lexicographically Smallest Array by Swapping Elements - Leetcode 2948 - Python

0:00 - Read the problem
3:09 - Examples
8:58 - Dry Run
13:44 - Coding Explanation

leetcode 2948

#neetcode #leetcode #python

[akopayplays]

How? just how? how can someone make explanation of something like this so easy? I am just gratefull to find this channel...

[travian]

The idea of finding and sort of "separately" sorting each group was key, thank you. Even knowing that i ended up coding something really inefficient jajaj.

[business_central]

feel bad I couldn't get the right intuition, but we getting there

[trsdesrn]

my bro releasing the daily video ten minutes after it came out is crazy...

[swastiktiwari]

Since in iteration "for n in sorted(nums)", sorted(sums) is sorted, so abs(n-groups[-1][-1]) = n - groups[-1][-1] (i.e., taking abs is NOT NEEDED)

[lacsman]

This is legendary! I had a 44 line code and was getting TLE.

[shreyasp]

This is on another level. definitely consistency is a key.

[lokeshwar]

You are awesome man, never thought it could be solved without knowing dsu-make, find, union

[lemons.]

satisfaction you get once you solve this by yourself is damn good, i was able to come up with some what same approach

[sldimaf]

abs() is unnecessary, because the array is sorted

[srreddysiddamreddy]

Java version:

class Solution {
public int[] nums, int limit) {
int[] arr=nums.clone();
int n=nums.length;
Arrays.sort(arr);
List<Queue<Integer>> ql=new ArrayList<>();
Map<Integer, Integer> mp=new HashMap<>();
int last=-1;
for(int i=0;i<n;i++){
if(i==0 ||
Queue<Integer> q=new LinkedList<>();
ql.add(q);
}


mp.put(arr[i], ql.size()-1);
last=arr[i];
}

int[] ans=new int[n];
for(int i=0;i<n;i++){
int qn=mp.get(nums[i]);

ans[i]=ql.get(qn).poll();
}
return ans;
}
}

[rishabhgupta]

I read the problem, checked the hints, and immediately looked up a Neetcode video on YouTube. As always, the explanation was fantastic and I am so grateful for it!

That said, I'm curious on what approach were the hints guiding us toward?

[staywithmeforever]

Its like longest increasing numbers where we have to group the values in limit and set the other values in place

[markopolo]

thanks that problem was pretty hard to understand

[JensUwe-]

I had the intuition but had no clue where to go from there

[rhugvedbhojane]

Hi Neet! Thank you for your efforts, I have learnt a lot from you. I just wanted to ask you, I don't know if you made a video like this earlier, but can you make a comprehensive video on how your thought process works when solving a problem like this? Thank you again.

[lethal_bot]

nice approach but i was not able to get this on my own.

[Axel.Blazer]

non deque solution

class Solution:
def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
chunks=[]
hash={}
# form chunks which are sorted in form of abs(chunk[-1]-x)<limit for all new x
# each chunk is sorted reverse
# maintain hashmap of chunks from original index
# pop from respective chunk in original mapping and append to lsa
for ele in reversed(sorted(nums)):
if not chunks or
chunks.append([])
chunks[-1].append(ele)
hash[ele]=len(chunks)-1
print(chunks)
print(hash)
lsa=[]
for ele in nums:
chunk=hash[ele]

return lsa

# nums =
# [1, 7, 28, 19, 10]
# limit =
# 3
# Stdout
# [[28], [19], [10, 7], [1]]
# {28: 0, 19: 1, 10: 2, 7: 2, 1: 3}
# Output
# []
# Expected
# [1, 7, 28, 19, 10]

[rajchavan]

If we are sorting it, do we really need a queue while grouping them? A simple array will also work right?

[naveenreddy]

How about using monotonically decreasing stack with condition for limit check?