Relative Sorting Efficient Code || Program 52 || Competitive Coding || Learning Monkey ||
Relative Sorting Efficient Code
In this class, We discuss Relative Sorting Efficient Code.
Readers can prepare an entire competitive coding course to crack product development companies. Click Here.
The reader should have basic coding skills to work with competitive coding. Click here.
Question:
Given two arrays, arr1 and arr2, of size N and M.
Sort the first array based on the relative position of elements in the first array, the same as the elements' positions in the second array.
Note: If elements are repeated in arr2. Consider the first occurrence position.
Example:
arr1 = [2, 1, 2, 1, 5, 3, 6, 7, 4]
arr2 = [5, 1, 2, 9]
Output: [5, 1, 1, 2, 2, 3, 4, 6, 7]
Time Complexity: O(nlogn)
Space Complexity: O(n)
Logic:
Using hashing, we can do this example in the specified time.
The reader should have the basics of hash table data structure.
The hash table finds the required element in O(1).
We maintain the element and element count in the hash table as key-value pair.
In Python, we use a dictionary to maintain key-value pairs.
Read the elements from arr2.
We append the value to the list if the element is present in the dictionary.
We append the value based on the count present in the hash table.
The step-by-step explanation is provided in the video.
In Python collections, we have a counter class.
The counter class creates the element and its count in the dictionary.
Code:
from collections import Counter
class Solution:
def relativeSort (self,arr1, N, arr2, M):
res = []
f = Counter(arr1)
for e in arr2:
res.extend([e]*f[e])
f[e] = 0
rem = list(sorted(filter(lambda x: f[x] != 0, f.keys())))
for e in rem:
res.extend([e]*f[e])
return res
arr1 = [2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8]
arr2 = [2, 1, 8, 3]
ob = Solution()
z=ob.relativeSort(arr1,11, arr2, 4)
print(z)
Link for playlists:
/ @wisdomerscse
Link for our website: https://learningmonkey.in
Follow us on Facebook @ / learningmonkey
Follow us on Instagram @ / learningmonkey1
Follow us on Twitter @ / _learningmonkey
Mail us @ learningmonkey01@gmail.com
Auf dieser Seite können Sie das Online-Video Relative Sorting Efficient Code || Program 52 || Competitive Coding || Learning Monkey || mit der Dauer online in guter Qualität ansehen, das der Benutzer Wisdomers - Computer Science and Engineering 24 April 2023 hochgeladen hat, den Link mit Freunden und Bekannten teilen, dieses Video wurde auf Youtube bereits 631 Mal angesehen und es wurde von 6 den Zuschauern gefallen. Viel Spaß beim Betrachtenden Zuschauern gefallen!
