MERGE K SORTED LISTS | LEETCODE 23 | PYTHON OPTIMAL SOLUTIO
Vložit
- čas přidán 26. 07. 2024
- Problem Link: leetcode.com/problems/merge-k...
Discord Link: / discord
In this video we are solving a popular Amazon and Facebook interview question dealing with linked lists: Merge K Sorted Lists (Leetcode # 23).
This question is pretty easy to solve on its own but there are optimizations that the interviewer will be looking for that make things a little bit trickier. Luckily it's not that complicated and we can easily solve it!
TIMESTAMPS:
00:00 Intro
00:16 Question Prompt
00:38 Basic Example
01:45 Naive Solution
03:00 Optimal Solution
06:36 Solution Diagram & Intuition
10:35 Coding
18:12 Time/Space Complexity
19:00 Outro - Věda a technologie
Thanks! Great Explanation.
Just one observation: Recursive calls always consume (stack) space, I think if you replace the merge(self, l1, l2) with iterative version, that would be actually constant space.
Never seen such crisp and simple approach to solve this problem in any other channel. So addicted to problem solving method. Thanks
Thanks for the kind words and welcome to the channel
Thanks a lot for a clear and concise optimal solution. I love how straight to the point you are!
Thanks for another great explanation, you always make complex solutions and approaches so easy to understand.
Quick heads up, the merge function you defined is recursive, so your space complexity is O(n + m) due to recursive stack frames.
The first call to merge does not return until the ends of both l1 and l2 have been reached, so n+m stack frames consume O(n+m) space.
To maintain O(1) space complexity, we should iteratively merge the linked lists.
Thank you for your video, it really helped me understand the problem and the solution for it
It's probably was my first hard problem I managed to solve myself :) 🥳🥳🥳
Amazing! Progress feels great doesn't it?
@@crackfaang it does feel sooooo good! :)