Maximum Employees to Be Invited to a Meeting - Leetcode 2127 - Python

0:00 - Intro
0:40 - Read the problem
3:13 - Observations
10:45 - Examples
15:24 - Intuition
17:05 - Final Solution
25:03 - Coding Explanation

leetcode 2127

#neetcode #leetcode #python

[ahmedtremo]

you're so good at explaining things, it's not just leetcode problems. you absolutely have a unique skill for teaching. thanks for putting in the time

[RajivLochanPanda]

Thinking on my own, I got the intuition that we need to check for the largest cycle, but I couldn't think of the case where we can fir multiple chains of cycle = 2.

[business_central]

lol from US here, and glad to see the jokes are back hahahaha

[ameyak]

great solution.

key insight about the two cases -
1. a cycle is of course a valid solution. The 2nd case is more trickier to wrap head around.
2. a 2-length cycle can be used to connect to paths ending at the two nodes of the 2-cycle.
(this is not possible with other length cycles, because one person
can only have two neighbors.)
Suppose node A and node B form a two node-cycle. They are each others favorites.
Now the path ending at A p_a and path ending at B p_b can be connected to form a valid solution.

p_a - everyone is sitting next to favorites which ends at A.
A's favorite is B so we continue the seating by placing B next to A.
B's favorite is A so B is satisfied to0.
The other neighbor of B can continue to be the connections coming from p_b.
Thus we are able to connect p_a and p_b thanks to A and B.

[icvetz]

Did you get this on your own or use help? Just curious. Thanks Neetcode.

[sarmohanty]

Took me an hour to solve this problem fml...also 0:30 LOL didn't realize so much of your audience was from India. guess it's because the interviews there are so much more difficult wrt Leetcode. Here in US only quant companies and the Google employee who just got a divorce are gonna ask these typa questions.

[baetz]

I was able to find all the observations and came up with that we need to get max of longest cycle length or sum of 2-cycle chains (I called it bicycles). However, I wasn't able to convert it to a working code. There are some really nice techniques shown here like using inverted graph or cutting of the tail from the big cycle, which I am very grateful for.

[BillyL]

you know it's trouble when u see a video longer than 30 minutes 🥲🥲😔😔

[yhbarve]

Goated! You made this problem for impossible to difficult to manageable to straightforward!

[jamestwosheep]

For such a short problem description, this one was especially diabolical. 😭

[hareee]

8:12 I mean the claim that every testcase would have EXACTLY 1 cycle is kind of misleading....

I would say every portion of the disjoint sets in the testcases each would have their own cycle each, so the count of cycles can be more in a given testcase, for ex: [1, 0, 3, 2] will have 2.

You yourself provided the example @ 8:49 with a separate cycle from the main. I was just following along with the observation.... this could lead someone to believe that this problem is just by trying find the cycle in a testcase, and returning that length, which may be wrong, which should be to find the longest length cycle within the dag.

[Nonsense]

The non-closed circles really threw me off when I tried solving it on my own. Thank you for the video!

[techandmore]

"The hard part of the problem is that it is a hard problem"

~ NeetcodeIO

[RajdeepJadeja]

This might be the longest neetcode video I have ever watched 😅

[GodRishUniverse]

I have a question - I knew that the question wanted the people in cycles and thought that vertices that point to cycle nodes that are part of 2 cycles should be added. So I found Tarjan's algorithm online to find SCCs and then used that but I get an error in a weird test case. Is my thinking flawed somewhere? I havent watched the video yet before I change my thoughts

[SaurabhKumar-wvhq]

You made a minor mistake int the example at 16:54 where there is an edge from 7 to 8 and also from 7 to 6. This is not possible. Just mentioned this if anyone is confused regarding this example. There should be an edge from 8 to 7.

[ManjeetSingh-soyr]

I have solved around 100+ hard problem in leetcode, most of them i was either able to solve myself or by looking at the videos ..this one i did not get even after watching video twice .. it feels like hard among hard problems ..

[FifaHades]

Sometimes i just came for the pre talk🤣 to only know your opinion on the current challenge

[swastiktiwari]

The line "if cur in cur_set" is NOT REQUIRED 
1) Case1: current traversal had a cycle: Then cur will be in cur_set
2) Case 2: current traversal didn't have a cycle, then at the end of "while start!=cur" loop, length will become zero

Example of case 2: 1-->2-->0-->3-->4-->5--->0. The cycle is covered for loop starting at i = 0 when visit is set True for i = 0, 3, 4, 5 ...for next loop starting at i = 1, loop ends with cur = 0, start = 1 and length = 2 ..then "while start!=cur" loop reduces length back to zero

[GajendraSinghSolanki-jz]

What if there is a single component and it has really long chain of nodes(say 10 nodes) before a tiny cycle of length greater than 2(say 3 nodes)? Which one of the two options explained here(34:52) will give the correct answer(10)? I think none of the two options would be able to give a correct answer as option 1 will give us 3 and option two will give us 0, and max of these is 3 but the correct answer is 10.

Shouldn't we also consider the length of chains preceding a cycle?

Ah, I see, now that I have written it, I think I got why chains can't be considered . Because nodes in the chains would eventually require nodes from the cycle :)