Merge K Sorted Lists - Divide and Conquer Approach

🡆Merge Two Lists Video: • Coding Interview Quest...
🎧 Join the community Discord: / discord
💰 Support me on Patreon: / michaelmuinos
🔗Follow me on LinkedIn: / michael-muinos
📂Follow me on Github: github.com/Mic...
Check out my interview prep platform for learning the patterns!
📢 Interview Prep Platform: algoswithmicha...
In this video I go over the popular Leetcode problem Merge K Sorted Lists involving the divide and conquer approach. This solution involves the knowledge of the merge sort algorithm where we must divide our array recursively and merge the lists to sort them at each recursive call. This question is asked at many top tech companies including Amazon, Facebook, Bloomberg, Uber, Adobe, Microsoft, and many more!
At each recursive call, we will compute a midpoint to determine at which point we will split our array. When we split the array into two parts, we will call our recursive function on both the left and right side of the broken array. Our base case is when our start and end index are the same value meaning it is a single linked list. By the end of merging all lists, we should have one final sorted linked list.
The time complexity of the solution will be big O(N * log(K)) where N is the number of nodes we must merge together and K is the number of recursive calls we make to divide the arrays. The space complexity will be big O(log(K)) where K is the number of recursive calls made that fill up our stack space.