Relative Sort Array | Counting Sort | Using Lambda | Leetcode 1122 | codestorywithMIK
277Whatsapp Community Link : https://www.whatsapp.com/channel/0029...
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
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Intervie...
Leetcode Link : https://leetcode.com/problems/relativ...
My DP Concepts Playlist : • Roadmap for DP | How to Start DP ? | ...
My Graph Concepts Playlist : • Graph Concepts & Qns - 1 : Graph will...
My Recursion Concepts Playlist : • Introduction | Recursion Concepts And...
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Intervie...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
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