Relative Ranks | 3 Approaches | Leetcode 506 | codestorywithMIK
179Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
This is the 36th Video of our Playlist "Linked List : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve an easy but a good Practice problem : Relative Ranks | 3 Approaches | Leetcode 506 | 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 Ranks | 3 Approaches | Leetcode 506 | codestorywithMIK
Company Tags : Amazon
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Arrays/Leetcode%20Easy/Relative%20Ranks.cpp
Leetcode Link : https://leetcode.com/problems/relative-ranks
My DP Concepts Playlist : https://youtu.be/7eLMOE1jnls
My Graph Concepts Playlist : https://youtu.be/5JGiZnr6B5w
My Recursion Concepts Playlist : https://www.youtube.com/watch?v=pfb1Zduesi8&list=PLpIkg8OmuX-IBcXsfITH5ql0Lqci1MYPM
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Interview_DS_Algo
Instagram : https://www.instagram.com/codestorywithmik/
Facebook : https://www.facebook.com/people/codestorywithmik/100090524295846/
Twitter : https://twitter.com/CSwithMIK
Subscribe to my channel : https://www.youtube.com/@codestorywithMIK
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
These three approaches aim to assign ranks to athletes based on their scores, with slight variations in implementation efficiency.
Approach-1:
Utilizes a map and sorting or vector of pair and sorting.
Time Complexity: O(nlogn) due to sorting.
Space Complexity: O(n) for storing the result and the unordered map.
The approach first creates a map to associate each score with its index.
Then it sorts the scores in descending order.
Assigns ranks based on the sorted order.
Approach-2:
Implements a max heap.
Time Complexity: O(nlogn) due to heap operations.
Space Complexity: O(n) for storing the result and the max-heap.
Constructs a max-heap of pairs of scores and indices.
Iteratively pops elements from the heap, assigning ranks as it goes.
Approach-3:
Also uses a max heap.
Time Complexity: O(n) with an additional loop to traverse scores.
Space Complexity: O(max_score) for the map.
First, finds the maximum score to determine the range of the map.
Then, constructs a map to associate each score with its index.
Iterates through scores from max to min, assigning ranks based on the map.
Each approach achieves the same goal of assigning ranks to athletes based on their scores. Approach-1 and Approach-2 utilize a max heap, while Approach-3 uses a map to optimize space complexity. Approach-3 has the best time complexity among them, linear time, because it avoids sorting.
✨ 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