Lowest Common Ancestor (LCA) Problem | Eulerian path method

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

КОМЕНТАРІ • 45

  • @codecode855
    @codecode855 Рік тому +2

    we can use segmented tree instead of sparse table for RMQ. my solution got accepted !

  • @vishaltk3013
    @vishaltk3013 3 роки тому +24

    This is damn good. I felt guilty for consuming this content for free and purchased the Udemy course. this may be one of the reasons why we see lesser views for videos as this course progresses further.

  • @alkhiljohn3813
    @alkhiljohn3813 2 роки тому

    So glad to know this guy has a soul and cares about investing time into teaching random people on the internet. I wish I could pay him back

  • @olehholovko1341
    @olehholovko1341 2 роки тому +10

    Thanks, your videos are great! I will definitely explore more soon.

  • @PrashantNigam
    @PrashantNigam 3 роки тому +7

    Practice problems for this concept:
    * leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree
    * leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-ii (LC Premium)
    * leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iii (LC Premium)
    * leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iv (LC Premium)
    * leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree
    * leetcode.com/problems/kth-ancestor-of-a-tree-node

  • @tashirojima
    @tashirojima 4 роки тому +2

    Such an elegant algorithm! Thank you

  • @Blure
    @Blure 4 роки тому +8

    Hello William! Thanks a lot for sharing your knowledge. Could you consider making a video about space-partitioning data structures, such as K-D tree, Quadtree and R-tree?

  • @matata.rishikesh
    @matata.rishikesh 3 роки тому

    The music at the start is also very good

  • @ialpha6431
    @ialpha6431 4 роки тому +4

    This is GOOOOOOOOD ! Very well explained. Now I know one more method to calculate LCA. Since, I am not currently familiar with Sparse table I guess any DS good in doing range queries (Segment Tree, BIT etc) can do the trick.

    • @WilliamFiset-videos
      @WilliamFiset-videos  4 роки тому +5

      Thank you Saurav 🙏. You're correct, you can swap out the sparse table for any other data structure that can do a RMQ

    • @madhukiranattivilli2321
      @madhukiranattivilli2321 3 роки тому +1

      But LCA can be computed in O(1) time only w/ Sparse Table. Segment Tree does in O(log2(n))

  • @HienNguyenTechIO
    @HienNguyenTechIO 3 роки тому

    Please make more videos. You channel is very well explained.

  • @mohammadyahya78
    @mohammadyahya78 2 роки тому

    Thank you. Still not sure why you visited node twice 14:50 please?

  • @nguyentuan6108
    @nguyentuan6108 2 роки тому

    bro deserves a 10

  • @Ghost0fDeath1
    @Ghost0fDeath1 4 роки тому +1

    Ty I did my project for uni with this

  • @Aashishkumar-dg4op
    @Aashishkumar-dg4op 4 роки тому +1

    Thanks a lot for sharing your knowledge.could you make videos on centroid decomposition.

  • @akshatsaxena5156
    @akshatsaxena5156 3 роки тому

    Your content and explaination is really good. But please do something to improve the sound quality, its too low and not audible sometimes.I am facing this issue in all your videos.

  • @Zoro40612
    @Zoro40612 4 роки тому

    Hello William. Why use a sparse table to lookup the minimum of a range in depth array? It takes O(nlogn) to construct it. We can get the minimum value of a range from depth array with a simple for loop in O(n).

    • @WilliamFiset-videos
      @WilliamFiset-videos  4 роки тому +4

      What about if you want to do multiple LCA queries? I would prefer to build the sparse table once and have each lookup be O(1) than have to pay O(n) for each query. The payoff point is reached once you've done log(n) queries which is very small.

    • @Zoro40612
      @Zoro40612 4 роки тому

      WilliamFiset Cool. Thanks for the videos! 🤟🏻

    • @protyaybanerjee5051
      @protyaybanerjee5051 3 роки тому

      @@WilliamFiset-videos So, essentially we have O(1) amortized lookup cost.

  • @swethapattabhi2916
    @swethapattabhi2916 3 роки тому

    Amazing explanation.Thanks a ton!

  • @mnhr7494
    @mnhr7494 3 роки тому

    This was awesome!!!

  • @BerArchegas
    @BerArchegas 3 роки тому

    Great channel

  • @hwgh
    @hwgh 4 роки тому

    I'm not sure I get why we need an Eulerian tour here. If we used a N sized array instead of 2N-1, and visited the three in-order always saving the pointer to the node and the depth. We would end up with an in-order array of tuples (nodes,weights) correct? In the video example we would have [ptr:3 dpt:2,
    ptr:1 dpt:1, ptr:0 dpt:0, ptr:6 dpt:3, ptr:4 dpt:2, ptr:2 dpt:1, ptr:5 dpt:2, ].
    Won't the property of the common ancestor being the one with the lowest depth that is between the two nodes still hold? It seems to be the case to me. What am I missing? Is it related to supporting non N-ary trees?
    Thanks for the great content!

    • @WilliamFiset-videos
      @WilliamFiset-videos  4 роки тому +1

      I don't think storing only N information is sufficent for n-ary trees? Suppose we had a very flat tree like:
      0
      / / / / | \ \ \ \
      1 2 3 4 5 6 7 8 9
      Can you explain how you would define the in-order traversal to query the lowest common ancestor of say node 2 and node 4?
      The Eulerian tour ensures that 0 appears between 2 and 4 in the tour, but I'm not sure this is true of the inorder traversal?

    • @hwgh
      @hwgh 4 роки тому +1

      ​@@WilliamFiset-videos I see. It really does make it work for N-ary trees. I think what happens is that the first visit (the one that happens before the "for") isn't really necessary unless the current node has no children. If we don't do it, all the nodes that have children will still work. The visit in the last iteration of the for doesn't seem to be necessary as well.
      So if we changed dfs for this:
      if node==null
      return
      if node.children.isEmpty
      visit(node,node_depth)
      for( child in node.children )
      dfs( child, node_depth+1)
      if (not child.isLastChild) or child.isOnlyChild
      visit(node,node_depth)
      This code would still insert the parent in between every child and it would work. ( Unless my reasoning is wrong somewhere ).
      Then for a binary tree this would behave exactly like a in-order search and this is the reason why in-order search works for a binary tree.
      And then for N-ary trees every iteration (but the last) will be visiting the current node again thus inserting the parent in between the children every time. I think this is it. Right?
      Thanks again. Your channel and your explanations are great!

  • @bhimeshchauhan3081
    @bhimeshchauhan3081 3 роки тому

    Can we not do Level order traversal and then use the formula for the respective nodes to find the LCA until we reach a common number in the list or we reach the root which would be the first item in the list. The complexity should remain the same.

  • @prasannathapa1024
    @prasannathapa1024 3 роки тому

    This is golddddd

  • @manushakya7384
    @manushakya7384 4 роки тому

    Thank You

  • @nhan99dn
    @nhan99dn 3 роки тому

    goat

  • @rushilpatel7671
    @rushilpatel7671 4 роки тому

    awesome !!

  • @935k3
    @935k3 4 роки тому

    So after watching the sparse table videos following this one, I'm trying to tackle an LCA problem on leetcode. The sparse table I've built simply returns the depth of the LCA since the table is based on the depth array. Going by the code in this video, it seems that the sparse table returns an index to plug into the nodes array. Not sure how to move forward from here...

    • @935k3
      @935k3 4 роки тому

      Doh, just realized I glossed over the index table within the sparse table! 🤦

  • @adhishmalviya2408
    @adhishmalviya2408 4 роки тому +4

    138 Likes and 0 Dislikes !!

  • @Rakibul-Hasan-Mahin
    @Rakibul-Hasan-Mahin 3 роки тому

    anyone solved this in python??
    if yes can you kindly share?

  • @dongliang8837
    @dongliang8837 Рік тому

    why is the volume so low. I have my computer on max volume and i can barely hear