Minimum Number of Days to Disconnect Island - Leetcode 1568 - Python

Поділитися
Вставка
  • Опубліковано 16 гру 2024

КОМЕНТАРІ • 67

  • @nileshbhanot2776
    @nileshbhanot2776 4 місяці тому +33

    Thank you so much for posting everyday

  • @yashwanthnadella537
    @yashwanthnadella537 4 місяці тому +66

    Lmao, you should add a new "ego crusher" category in your roadmap

  • @shubhrantyadav1538
    @shubhrantyadav1538 4 місяці тому +18

    Damn this was the chillest explanation I ever saw. "Won't be doing Tarjan's algo cuz I don't feel like it" 🤣🤣🤣. btw I wasn't able to code the solution completely but I am glad I was almost 70% correct.

  • @NeetCodeIO
    @NeetCodeIO  4 місяці тому +69

    if you're only here for tarjan's algorithm.. i'm sorry

    • @tuandino6990
      @tuandino6990 4 місяці тому +1

      Dude whyyy 😢😢😢

    • @ForAeonz
      @ForAeonz 4 місяці тому +9

      I am only here for neetcode

    • @light2666
      @light2666 4 місяці тому +1

      Bro I was trying union find myself , then I ended up failing as well after I found about the 0 , 1 ,2 condition.
      Then I was stuck. But whats with the depressing comment.

    • @kristidharpandit1315
      @kristidharpandit1315 4 місяці тому +2

      Why to code for the last case ? The answer 2 is obvious after checking 0 and 1

    • @123gostly
      @123gostly 4 місяці тому

      You should pin this comment.

  • @NEO-wl9ox
    @NEO-wl9ox 4 місяці тому +3

    Leetcode actually is getting mellisonant and overwhelming these days and it pan out to me that leetcode insidiously trying to jam down all beginner self-taught programmers like me by letting us solve this kind of problems.However, neetcode has helped to get over these obstacles with comprehensive solutions and explanations.

  • @raviyadav2552
    @raviyadav2552 4 місяці тому +16

    Honestly this looks hell simple when you taught.

  • @amol_
    @amol_ 4 місяці тому +2

    Luck is a big factor to crack big companies.
    recently i gave interview for uber for for senior fullstack developer and i was able to solve all problems and system design round was also good.
    but they rejected by saying,
    1. Problem (optimal transaction like)
    feedback: i used int instead of BigInteger
    2. cache design with TTL as expiration:
    feedback: I test the code using Thread.sleep to simulate the time same time i can explain we can have Time object as dependency and mock the same, still they gave same as feedback.
    3. use better name (i used good name and i dont prefer to use a,b i and j as variables).

  • @АльбусДамблодр
    @АльбусДамблодр 4 місяці тому +1

    Solved it by myself after revealing hints on leetcode! Thank you neetcode for your videos!

  • @riddle-me-ruben
    @riddle-me-ruben 4 місяці тому

    Thank you for the reassurance. It seems logical for companies to ask reasonable problems that demonstrate problem solving skills as opposed to the rarer, more advanced academic problems.

  • @ACE-qh5de
    @ACE-qh5de 4 місяці тому +6

    It did humble me , correct category - Ego Crusher

  • @ZaneMouakket
    @ZaneMouakket 4 місяці тому

    My solution was noticing there are 3 ways an island can be split:
    1) Go through all the land and see if there are any land tiles to where filling them with water split the islands
    2) Find the piece of land with the most water (or edge) around it and surround the rest with water.
    3) Fill all the land with water
    Part A: If it's already split return 0
    Part B: If method 1 splits the islands, then return 1
    Part C: If doing method 2 doesn't just leave one piece of land left, return method 2,
    Part D: If doing method 2 does leave just one piece of land left, do method 3
    NeetCode was saying that you have to make the realization that the maximum answer is 2, but I was able to arrive at this solution without that realization.
    After looking at the editorial I noticed if you ever get to part C or D the answer will always be 2 and so this method can be greatly simplified, but this method is able to work without making the realization that the maximum answer is 2.

  • @rajrajesh1669
    @rajrajesh1669 4 місяці тому

    4:38 thanks for the proof. Now, I'm satisfied.

  • @shivam-codes
    @shivam-codes 4 місяці тому +1

    step 1 : find SCC (strongly connecrted component) , if SCC == 0 || SCC > 1 : return 0;
    step2 : find bridges in graph , if we have a bridge : return 1;
    step3 : else return 2;

  • @corrogist692
    @corrogist692 4 місяці тому

    actually we can keep track of the min connected sides of the 1s while iterating the grid and run the dfs. if its 1, then remove 1, if its 2 then remove 2.

  • @ishaankapoor933
    @ishaankapoor933 4 місяці тому

    hey, a small correction. Segment trees are fairly common in coding rounds of big tech companies like google, rubrik and sprinklr. (Atleast here in India, they ask all sorts of questions to fresh college grads.)

  • @arpitpaliwal6484
    @arpitpaliwal6484 4 місяці тому +1

    Thank you for the daily solution

  • @finemechanic
    @finemechanic 4 місяці тому

    You don't actually need to count number of islands. You just need to check if any land exists and, if it is, check that the island area is equal to the total land area. So, only one BFS per iteration is needed.

  • @AdityaKumar-wq3nb
    @AdityaKumar-wq3nb 4 місяці тому +2

    i solve this on my own 🔥🔥

  • @gowtham_codes
    @gowtham_codes 4 місяці тому

    Last few minutes was too nostalgic. It felt like when my Math teacher used to come to class but not take lecture😂
    Jokes apart thank you man.

  • @MP-ny3ep
    @MP-ny3ep 4 місяці тому

    Beautiful explanation. Thank you.

  • @ChethanV-w8l
    @ChethanV-w8l 4 місяці тому

    Thanks for uploading daily.

  • @madhavgupta2002
    @madhavgupta2002 4 місяці тому +2

    15:00
    my soul is crushed

  • @pastori2672
    @pastori2672 4 місяці тому +2

    14:27 bro almost got demonetized 💀

  • @adrianlistkiewicz9449
    @adrianlistkiewicz9449 4 місяці тому +1

    DFS for victory :))

  • @sirk3v
    @sirk3v 4 місяці тому

    ego crushed, you make it so easy though, the elimination intuition made it easier, thanks alot

  • @vishwaroop1431
    @vishwaroop1431 4 місяці тому +1

    i have a que, like what if i am not able to solve the que.
    what should i do l read the editorial first and then come to watch the video or vice versa ?

  • @proudbox5091
    @proudbox5091 3 місяці тому

    see the things is the hiring scene really depends on country and competition , obviously the needs and the questions asked are of varied difficulty , also luck is obviously a factor

  • @aashishbathe
    @aashishbathe 4 місяці тому +2

    The hints do mention maximum of 2 removals. It was easy enough to figure out, however the edge cases for the 1 removal were crazyyy

    • @NeetCodeIO
      @NeetCodeIO  4 місяці тому +14

      damn I forgot they even had hints

  • @RishabhSharma-p9o
    @RishabhSharma-p9o 4 місяці тому

    yeah , i have tried the brute force , it was really painful.

  • @parthasarathysubburaj3146
    @parthasarathysubburaj3146 4 місяці тому

    Hi @NeetCodeIO, I just have one doubt...we are calling DFS only on nodes that are not in the visited set, so probably we can get rid of that condition inside the base case inside the DFS function? or we could remove the same check before calling DFS and let it get handled inside the DFS base case?

  • @brij4887
    @brij4887 4 місяці тому

    Thank you so much

  • @juanmacias5922
    @juanmacias5922 4 місяці тому

    "I fear not the man who has practiced 10,000 kicks once, but I fear the man who has practiced one kick 10,000 times."
    Bruce Lee

  • @Ice-2706
    @Ice-2706 4 місяці тому

    the TC could go nm^3 incase of the remove 2 case, because there are nC2 choices of pairs to be removed

    • @Ice-2706
      @Ice-2706 4 місяці тому

      anyways, we could be smart about choosing the pairs, basically we can neglect pairs which are far off that would never cause a disconnect, and only consider pairs in near proximity (in 8 directions), which would boil down the number of pairs to be linearly proportional to the number of 1 cells, hence nm^2 would prevail.
      But @NeetCode, since you are mentioning brute force, you should also mention the point made above.

    • @Codisrocks
      @Codisrocks 4 місяці тому

      No need to check pairs.

  • @ddinchevchannel
    @ddinchevchannel 4 місяці тому

    Boom boom. Lov' it! 😂🔥

  • @WebSleek
    @WebSleek 4 місяці тому

    u look good with face cam while explaining pls do use it
    thank you...❣

  • @chinmoydebnath353
    @chinmoydebnath353 4 місяці тому

    been doing leetcode for years, at this point I have even forgotten why? doesn't matter how much you practice in high stressed interview situations you are never coming up with such absurd solutions.

  • @salim444
    @salim444 4 місяці тому

    shouldn't counting the degree also work? the only counter example I can think of is the consecutive ones which is also given.
    Let me elaborate: 1. count islands and if it isn't one island then return the zero. 2. pass over the grid and store the degree of each not and its position 3. if there is only two nodes with degree one then return 2 (the example given) 4. if there is nodes with degree 1 then return 1 5. all nodes of degree 2 and up so return 2. I think this is in order of N*M and takes N*M space

    • @nihalbhandary162
      @nihalbhandary162 4 місяці тому

      Imagine a grd like this [ [1,0,1],[1,1,1],[1,0,1]. The min degree of all nodes is 2. If you were to return i.e 2 cells to delete. It would be wrong. You just have to delete the middle 1 in second row. The deletion of one cell will create two islands.
      I actually coded thinking with the same approach as you. But this node ( aka articulation point in Tarjan's algo) is thr weaklink.

  • @sanskarsinghiit
    @sanskarsinghiit 4 місяці тому

    0:01:00 was that a brain boom, :P

  • @samobot
    @samobot 4 місяці тому

    This was an absolute ego crusher for me too, jesus. I eventually got it, but at what cost?

  • @borisbeginin
    @borisbeginin 4 місяці тому

    I did it using graph today 🤔

  • @gavinebenezer1670
    @gavinebenezer1670 4 місяці тому +1

    🐐

  • @rambabupatidar3092
    @rambabupatidar3092 4 місяці тому

    I was getting runtime error just for not putting directions array outside the dfs function. Else I did it by myself.

  • @kunalthakur5162
    @kunalthakur5162 4 місяці тому

    Line 14 indentation error

  • @arjunc1482
    @arjunc1482 4 місяці тому

    Is this anyway related to finding the Articulation point/finding bridge in graph or something like that

  • @koushikchatterjee4577
    @koushikchatterjee4577 4 місяці тому

    Ewwuu, like for case of 0 deletion evaluate, for case of 1 deletion brut force, because if that fails for case 2 deletion we don't need brut force because if not 0 and not 1 then 2 can be the max so we don't need brut force in combination for 2 and more onwards, but you were not able to evaluate in the case of 1 deletion, ain't this true?

  • @Livelaster
    @Livelaster 4 місяці тому

    I cant follow at all rip

  • @jamestwosheep
    @jamestwosheep 4 місяці тому

    Man oh man, that sigh at the start - I really felt that. I spent so long trying to get something close to O(m·n) and even with the hints and some high level explanations in the discussion section, I still eventually gave up and settled on a very similar brute force-ish algorithm as your description here.
    I really appreciate you putting up these videos, it's really nice to know I'm not alone in being humbled.