Find the Winner of the Circular Game | 3 Approaches | Leetcode 1823 | codestorywithMIK
Vložit
- čas přidán 27. 07. 2024
- Whatsapp Community Link : www.whatsapp.com/channel/0029...
This is the 3rd Video of our Playlist "RECURSION : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve a very famous Recursion problem : Find the Winner of the Circular Game | 3 Approaches | Easy Explanations | Leetcode 1823 | 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 : Find the Winner of the Circular Game | 3 Approaches | Easy Explanations | Leetcode 1823 | codestorywithMIK
Company Tags : Goldman Sachs, Amazon
My solutions on Github(C++ & JAVA) : github.com/MAZHARMIK/Intervie...
Leetcode Link : leetcode.com/problems/find-th...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My Recursion Concepts Playlist : • Introduction | Recursi...
My GitHub Repo for interview preparation : github.com/MAZHARMIK/Intervie...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
Approach 1: Brute Force (Simple Simulation)
Time Complexity: O(n^2)
Space Complexity: O(n)
Description: This approach uses a vector/ArrayList to simulate the elimination process. It iteratively calculates the index of the player to be eliminated, removes the player from the list, and continues until only one player remains. The index of the next player to be eliminated is adjusted using modulo arithmetic.
Approach 2: Using Queue for Simulation
Time Complexity: O(n * k)
Space Complexity: O(n)
Description: This method employs a Queue to simulate the game. Players are added to the queue initially. In each iteration, players up to k-1 are moved to the back of the queue, and the k-th player is removed. This process is repeated until only one player remains in the queue.
Approach 3: Using Recursion
Time Complexity: O(n)
Space Complexity: O(1) (but O(n) due to recursion stack)
Description: This recursive approach calculates the index of the winning player directly. It uses a helper function to find the winner index for n-1 players and adjusts this index to reflect the position in the original group of n players. The base case handles the scenario with only one player left, returning index 0.
Each approach offers a different balance of time and space complexity, allowing for flexibility based on the specific constraints and requirements of the problem.
✨ Timelines✨
00:00 - Introduction
05:15 - Approach-1 (Simulation using Array)
14:23 - Approach-2 (Simulation using Queue)
19:40 - Approach-3 (Recursive Approach)
#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
Approach 4 : Using For loop
public int FindTheWinner(int n, int k, int val = 0) {
for(int i =2; i
Aha indeed ❤️❤️❤️
Pinning this comment
this code copy from Editorial solution
@@Shivamsingh-ry6bz bro, does it matter ? learn the technique and move ahead! Certain things come up with practice and that’s how we build intuition. Happy learning!
Queue approach was most cognitive. Recursion I am not able to understand.
1-2 baar dekho, mai finally samajh gaya. kaafi sir dird approach tha
I solved it using circular doubly linkded list
i thought the same, at first, but stack work better
@@kartikforwork please explain how stack is better ?
This problem is from cses problem set. Mik can you please make videos on cses problem set. It consists of many good problems covering both dsa and cp.
Please bhaiya if possible, provide solution to :
HARD: Count the number of subarrays with AND k.
HARD: Construct string with minimum cost.
latest leetcode contest problem
Yes bhaiya plz.
Yes bhaiya plz
I did this using circular linkedlist
Thanks a lot bhaiya ❤️
Why Your Explaination is best ?
what the magic you did everytime ??
Tell me / BTW love from kolkata
Finally understood the o(n) approach.
Awesome 👍🏻
Array and queue simulation 💯
i love recursion man
I tried my best to understand from leetcode official solution for Approach-3 and also referred to other videos. Finally I am here and all my doubts are clear. I now know why +1 is done, why +k is done which was the trickiest part
Hey MIK
in recurion approach , can u tell the theory of why we do idx+k,
wo toh aapne example see explain kar diya ,
like much math lagi hogi to determine ki aisa hi hoga..
usse aur easy hoga samjhne mai...
please tell..
Recursion approach was lit 🫡
Boss last approach ki intuition samajh nahi ayi :(
Neither did I get ki how is it working . I mean intv Mei how will I be able to come up w it?
First comment ❤❤
This problem on LeetCode asks us to solve it in constant space. However, in the recursive approach, we are using a auxiliary stack space of O(n). Shouldn't we count that as extra space?
You can confirm from the interviewer if we can ignore the system stack space. If he agrees, then recursion is the way to go. If he asks to not take system stack space, then convert the recursive approach to iterative.
class Solution {
public:
int solve(int n,int k)
{
int ans=0;
for(int i=1;i
@@visheshpandey9070 I think we should start with i = 2 in for loop, bcz the size is already 1 when we have got our winner i.e. index 0.
My iterative approach ---->
class Solution {
public int findTheWinner(int n, int k) {
int idx = 0;
int size = 2;
while(size
bhaiya i don't get the past where u said we will start indexing from 3 onwards at 23:48
how recursion is treaking this?
pls can anyone explain
this problem is based on josephus problem.
Bhaiya 3213(contest ,405) Karaiye na
HARD: Count the number of subarrays with AND k.
HARD: Construct string with minimum cost
sir, please start leetcode contest solution, question wise, huge request
Yes actually i post contest ones. Just got very occupied since last Month.
Will get back on it ❤️
@@codestorywithMIK yes please eagerly waiting for them especially 4th problems they teach us new things every time and only you can make us understand those clearly
@@codestorywithMIK yes it will give you more reach as it will become a one stop solution.
@@codestorywithMIK Yes bhaiya 4th problem me mostly new concepts hote hai ...only u can explain that in best possible way
HARD: Count the number of subarrays with AND k.
HARD: Construct string with minimum cost
Plese provide solution for yesterdays contest questions! Thanks
Easy tho tha kafi
for the first appraoch, in java code, leetpcode is saying TC is o(N)
can u please check once...
It is a new feature, has it's own set of bugs. TC in O(N^2), you can report the given TC.
i was stuck due to indexing how did u find out idx should be i+k-1;
Take example of k=2 and if u will start from index 0 then you will go 0->1 then you need to delete the 2nd element which is in first index so you will do i+k-1=> 0+2-1=1(index to be deleted)
pls reply bhai aap ek bat sach batana, kya aapko har question khud se krte ho pls reply dena
I am doing leetcode daily from the last month and i was able to do it by myself only few times.
Is it fine to watch the video solutions and then do it , i am feeling like i am getting used to these video tutorials and won't be able to do it myself ever.
Hi Sarthak,
Watch hints/videos/solutions after trying it on your own for max 40-45 minutes.
If you are still stuck, take hints first,
Still not able to solve ? Then watch solution (video or leetcode discuss section)
BUT most importantly, make sure you understand it well and figure out where you missed the approach. Then solve similar problems or solve qns on that topic to strengthen it.
practice is important
@@codestorywithMIK Thank you ! Your videos are really helping me grow.
bhaiya can we use circular linked list implementation for this problem
Yes and it's very easy then all approaches
class Node{
public:
int data;
Node*next;
Node(int val){
this->data=val;
this->next=NULL;
}
};
class Solution {
public:
int findTheWinner(int n, int k) {
Node* head=new Node(1);
Node * temp=head;
for(int i=2;inext=newNode;
temp=newNode;
}
temp->next=head;
int count=0;
temp=head;
while(countdata=temp->next->data;
temp->next=temp->next->next;
count++;
}
return temp->data;
}
};
Definitely 👍🏻
@@thorodinson7259 oh you gave the solution that is really great , I will do a dry run of this solution ☺️
@@codestorywithMIK thanks a lot bhaiya learnt a lot from you and still learning!
Actually you should also store the temp int some pointer and delete that pointer after the whole Operation happens good for memory management
Doubt: Approach 1 me time complexity n2 kaise ??? Uper bhi toh ek loop chl rha h...confused🧐
The above for loop where we populate arr , takes O(n) time.
Now coming to the second for loop, it take O(n^2)
So over all , T.C = O(n + n^2)
Now we usually ignore the smaller terms, so we can write T.C =~ O(n^2)
Hope this helps ❤️
@@codestorywithMIK ignore smaller ye nhi pta tha....thank you😇🤩
I hate google translate! I can't understand the last method...