Relative Sort Array - Leetcode 1122 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
4:42 - Coding Explanation

leetcode 1122

#neetcode #leetcode #python

[jotrades]

Bro went from Alpha to Sigma in 4 years, actually the Java comparator solution was quite smart tbh 👌👌👌

[JamesBond-mqpd]

As an Android developer I also switched from Kotlin to Python

[julianelmasry]

cant we use count sort for this problem similar to yesterday to maintain O(n) TC?

[daniellarson]

You can also make the space complexity O(m) by making a hashmap with arr2's indices and then sorting arr1 in place with a lambda (hm[n] if n in hm else len(arr2) + n). Still nlogn time complexity though.

[md_pedia]

y don't u use the extend method to append a resulting list and keep using 2 for loops? is it related to a TC issue or smth?

[ashanksaini]

I see how your java code was incredible faster than python ...lol

[varunpalsingh]

Hey Neet can you post a video solution on this problem "987. Vertical Order Traversal of a Binary Tree", Thanks in advance 🙂

[sri_harsha_dv]

my solution:
counter = {}
for n in arr1:
counter[n] = counter.get(n, 0)+1
matching, distinct = [], []
for n in arr2:
matching += [n]*counter[n]
counter[n] = 0
for n in counter:
distinct += [n]*counter[n]
return matching+sorted(distinct)

[JerickMamuric]

My solution using count sort.

result = []
max_number = max(arr1)
count = [0] * (max_number + 1)

for n in arr1:
count [n] += 1

for n in arr2:
result = result + [n for _ in range(count [n])]

for i, n in enumerate(count ):
if i not in arr2 and n > 0:
result = result + [i for _ in range(n)]

return result

[qulinxao]

class Solution:
def relativeSortArray(self, a: List[int], b: List[int]) -> List[int]:
l=len(b:={v:i for i, v in enumerate(b)})
return sorted(a, key=lambda x:([b[x]] if x in b else [l, x]))

[metarus]

thank you Navdeep .... pls keep 'em coming

[vnnyboy]

Count sort : O(n) time

class Solution:
def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
arr = [0]*1001

for a in arr1:
arr[a]+=1

res=[]

for a in arr2:
while arr[a]:
res.append(a)
arr[a]-=1
for a in range(len(arr)):
while arr[a]:
res.append(a)
arr[a]-=1

return res

[thunderstorm-dc]

Quick question, if this question is given in a real interview, will a self defined compare function be a bad answer?

eg
from functools import cmp_to_key
class Solution:
def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
order = {}
for i in range(len(arr2)):
order[arr2[i]] = i

def cmp(a, b):
if a in order and b in order:
return order[a] - order[b]
elif a in order and b not in order:
return -1
elif a not in order and b in order:
return 1
else:
return a - b

arr1.sort(key = cmp_to_key(cmp))
return arr1

[jhanavikumari]

i m so happy i did the exact approach 😝

[qulinxao]

class Solution:
def relativeSortArray(self, a: List[int], b: List[int]) -> List[int]:
l=len(b:={v:(i, ) for i, v in enumerate(b)})
return sorted(a, key=lambda x:b.get(x, (l, x)))

[asagiai]

I think that Java is a much more desirable solution or at least way of thinking. If someone is hiring. But both are okay.

[Someoneunknown]

I am also shocked the same way to see my 1 year old code.

[nirmalgurjar]

Since arr[i] constraint is very low from 0 to 1000, we can use count sort 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;
}
}

[SujeetKumar-hhjz]

element of arr2 are distinct, so why to use set there in 2nd line

[greatfate]

bro since you're collecting the counts and range is 0-1000 anyway you coulda did counting sort for the end bit