Lowest Common Ancestor (LCA) Problem | Eulerian path method

Sdílet
Vložit
  • čas přidán 10. 04. 2020
  • Lowest Common Ancestor problem
    Lowest Common Ancestor source code video:
    • Lowest Common Ancestor...
    Sparse Table Video:
    • Sparse Table Data Stru...
    Source code repository:
    github.com/williamfiset/algor...
    Video slides:
    github.com/williamfiset/algor...
    ===================================
    Practicing for interviews? I have used, and recommend `Cracking the Coding Interview` which got me a job at Google. Link on Amazon: amzn.to/3cvMof5
    A lot of the content on this channel is inspired by the book `Competitive Programming` by Steven Halim which I frequently use as a resource and reference. Link on Amazon: amzn.to/3wC2nix

Komentáře • 45

  • @vishaltk3013
    @vishaltk3013 Před 3 lety +18

    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.

  • @olehholovko1341
    @olehholovko1341 Před rokem +7

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

  • @tashirojima
    @tashirojima Před 3 lety +2

    Such an elegant algorithm! Thank you

  • @Blure
    @Blure Před 4 lety +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?

  • @codecode855
    @codecode855 Před 7 měsíci +1

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

  • @HienNguyenTechIO
    @HienNguyenTechIO Před 3 lety

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

  • @swethapattabhi2916
    @swethapattabhi2916 Před 3 lety

    Amazing explanation.Thanks a ton!

  • @alkhiljohn3813
    @alkhiljohn3813 Před rokem

    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

  • @ialpha6431
    @ialpha6431 Před 4 lety +3

    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  Před 4 lety +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 Před 2 lety +1

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

  • @Aashishkumar-dg4op
    @Aashishkumar-dg4op Před 4 lety +1

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

  • @Ghost0fDeath1
    @Ghost0fDeath1 Před 3 lety +1

    Ty I did my project for uni with this

  • @mnhr7494
    @mnhr7494 Před 2 lety

    This was awesome!!!

  • @bhimeshchauhan3081
    @bhimeshchauhan3081 Před 2 lety

    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.

  • @mohammadyahya78
    @mohammadyahya78 Před 2 lety

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

  • @BerArchegas
    @BerArchegas Před 2 lety

    Great channel

  • @David-uv8kt
    @David-uv8kt Před 4 lety

    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...

    • @David-uv8kt
      @David-uv8kt Před 4 lety

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

  • @manushakya7384
    @manushakya7384 Před 3 lety

    Thank You

  • @matata.rishikesh
    @matata.rishikesh Před 2 lety

    The music at the start is also very good

  • @PrashantNigam
    @PrashantNigam Před 3 lety +5

    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

  • @rushilpatel7671
    @rushilpatel7671 Před 4 lety

    awesome !!

  • @akshatsaxena5156
    @akshatsaxena5156 Před 3 lety

    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 Před 4 lety

    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  Před 4 lety +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 Před 4 lety

      WilliamFiset Cool. Thanks for the videos! 🤟🏻

    • @protyaybanerjee5051
      @protyaybanerjee5051 Před 3 lety

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

  • @hwgh
    @hwgh Před 4 lety

    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  Před 4 lety +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 Před 4 lety +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!

  • @prasannathapa1024
    @prasannathapa1024 Před 3 lety

    This is golddddd

  • @dongliang8837
    @dongliang8837 Před 8 měsíci

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

  • @nguyentuan6108
    @nguyentuan6108 Před rokem

    bro deserves a 10

  • @nhan99dn
    @nhan99dn Před 2 lety

    goat

  • @Rakibul-Hasan-Mahin
    @Rakibul-Hasan-Mahin Před 2 lety

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

  • @adhishmalviya2408
    @adhishmalviya2408 Před 3 lety +4

    138 Likes and 0 Dislikes !!