Find the Winner of the Circular Game - Leetcode 1823 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑‍💼 LinkedIn: / navdeep-singh-3aaa14161
🐦 Twitter: / neetcode1
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
Problem Link: leetcode.com/problems/find-th...
0:00 - Read the problem
1:00 - Queue Explanation
6:33 - Coding Queue
8:08 - Recursive Explanation
14:10 - Coding Recursive
15:38 - Coding Iterative
leetcode 1823
#neetcode #leetcode #python

[@manishmalepati9675]

I could do the queue, but couldn't think of the recursive solution. I was looking at soo many KZbin videos trying to explain this Josephus problem, but none of them could show the intuition. You are the only one who showed how the recursive logic worked, and how we can take a step from queue logic to the recursive one. Thank you so much!!

[@Billigently]

Sometimes it’s hard to wrap my head around recursive solutions but you explained it so perfect and clear! Thank you!

[@parthkansara552]

Would you ask this in an interview? Till what level of optimization would you expect the candidate to solve?

[@NeetCodeIO]

definitely not, if you do it's unlucky, like 0.1% unlucky. the queue solution is approachable with hints but not the recursive one imo

[@nikhil199029]

Fml. I got determine the winner of Babylon problem if all players play optimally in an interview.

[@patelvrukshal5102]

I was asked this in Splunk OA and I solved it with queue logic. Didn't hear back from them so some people might have solved with the recursive intuition I bet.

[@fraserdab]

u explained the recursive approach fast and properly, just what i needed

[@fancypants6062]

I had no clue why the modulo solutions worked until watching this video, now it makes perfect sense. Thank you.

[@xx1slimeball]

I think u did a great job explaining it! The way that help me understand the subproblems was by visualizing like this " n = 5 k = 2 f(n) = [1, 2, 3, 4, 5] f(n - 1) = [3, 4, 5, 1] f(n - 2) = [5, 1, 3] f(n - 3) = [3, 5] f(n - 4) = [3] " its similar to how you did except, instead of appending the nums, each function call can be viewed as its own list, where each i = 0 is the prev k + 1, thus the relation f(n) = (f(n - 1) + k) % n, can be seen (where f(n) is the index of the correct person in the current list). But jeez, this problem was pretty crazy. It's also cool that we never care about which person that have to leave, bc we know that the basecase person will be safe and we only recover its original index, Great video!!

[@gary1614]

So much clearer now! You did a great job explaining this question. Love your videos!

[@sri_harsha_dv]

I had to watch the 2nd approach twice to understand. It's just the shifting of indices is new to me and I was concentrating solely on that rather than overall solution. Sidenote: This might be obvious to some or completely irrelevant to others. I was wondering what might be the usecase for this crazy solution. There might be a better one (let me know if there is), but to my surprise I found it in "hide and seek" game. There are many ways to determine who is the seeker. One of those is by counting using set of phrases (this will differ most likely, but we used "inky pinky ponky" if that rings a bell to few of you). So there is a solution for that mini-game. After finding out the usecase, I checked the title of the problem and thought this might be reference for the problem.

[@MP-ny3ep]

Thank you so much ! All 3 explanations were great

[@julianelmasry9556]

was not able to have the queue neuron fire today. I was having trouble trying to represent the problem

[@greatfate]

you did a good job explaining last approach broski

[@YashGupta-ty2hn]

A Very simple code in python class Solution: def findTheWinner(self, n: int, k: int) -> int: queue = deque(list(range(1, n + 1))) while len(queue) > 1: queue.rotate(-k) queue.pop() return queue[0]

[@opuchakraborty]

You did good while explaining the recursive and bottom up approach, but it's still difficult to wrap my head into the solution. I could do the Queue though.

[@zetianjin5414]

very good explanation

[@Munchen888]

Am I understand right that in recursion we create an arr= list(range(1, n + 1)) and in function we pop k - 1 and solve subproblem (arr). When the length of arr is 1 return arr[0]?

[@dhaanaanjaay]

simply Genius

[@tirasjeffrey2002]

coming with A solution is good, but blud has 2 3 solutions up his sleeve, straight up monster

[@shubhamkhatter2196]

NGL, i code my solutions in C++ just bcoz i started that way, even though i am fluent with python as well. but when i first saw deque approach i was kind disheartened to see that, coz in the solutions board, everyone was using that recursive approach, and i thought that you were using different approach, so i started for looking at other videos, and they were really not doing a good job at explaining it, and when i thought that it doesnt matter if your solution is not the one i was looking for, but atleast i am able to understand its intuition well, you came up with the recursive approach later in the video, so what i am trying to say is, you explained it well. TLDR: you explained it well and next time just tell at the start of video that you have more than one solution, ik you always do that, but i am not used to it T_T. thanks btw.

[@B-NikhilRichhariya]

It was great !

[@shub2726]

26 seconds ago is amazing

[@corrogist692]

for the iterative one you can start from 2 since everything %1 is 0 (of course, doesn't really matter the time consumed is insignificant)

[@hhh555jjj]

Thank you so much! This one is greatly helpful! I have been thinking "why gpt said adding k is for adjustment??" for 2 days and got nothing done😂

[@venkateshnaidu2133]

I did this iteratively (using array) and then optimized it using queue. (Looking at the constraints, I knew these would pass) Could not at all come up with the recursive approach.

[@DeathSugar]

Tried to code up wikipedia's general formula and it looks like invalid

[@reggiehurley1479]

i think the iterative version is a bit more inuitive than the recursive one

[@TWEEDOriginal]

Linked list solution JS var findTheWinner = function (n, k) { function ListNode(val, next) { this.val = (val === undefined ? 0 : val) this.next = (next === undefined ? null : next) } let head = new ListNode(1) let prev = head for (let i = 2; i

[@GunnerJayx]

Why not just use a linked list?

[@yogeshchauhan9401]

Simulation is easy to come up with but recursive is 🔥🔥

[@pastori2672]

einstein wouldnt waste a millisecond of his life solving leetcode sadly 😭

[@NeetCodeIO]

you never know, he loved day dreaming and solving hard problems by running thought experiments in his head

[@bhavyajainnd]

Even the hints just tell you to simulate maaaan 😭 what is this question?

[@pat777b]

I suspect there is a clever O(1) time and O(1) space solution. I haven't figured out such a solution yet but my gut tells me there might be one.

[@ahlamabugosh9596]

there is kzbin.info/www/bejne/q3TWdWaQfN-Anac

[@saruhasan9145]

There is

[@fabricio5p]

there is for fixed size values of k: en.wikipedia.org/wiki/Josephus_problem

[@EduarteBDO]

just for k = 2 and k = 3, people discovered.

[@SanoyBoby]

class Solution: def findTheWinner(self, n: int, k: int) -> int: s=0 total=n*(n+1)//2 l=list(range(1,n+1)) i=0 while len(l)!=1: if i+k-1>=n: i=((i+k-1)%n) else: i+=k-1 print(l,i) s+=l.pop(i) n-=1 return total-s no queue,simple list

[@irfansari_]

Still space: O(n)

[@saruhasan9145]

My code i took me 2 hours to come up with class Solution: def findTheWinner(self, n: int, k: int) -> int: players = [i for i in range(1, n + 1)] length = len(players) i = 0 while length != 1: i = (i + k - 1) % length players.pop(i) length -= 1 return players[0]