Merge K sorted lists | Leetcode #23

This video explains a very important programming interview problem which is to merge K sorted lists.In this problem,we are given K lists in ascending order and we are required to merge all the K lists into a single list in ascending order and return the result.The given K lists can be in the form of array of vectors or linked lists etc.I have explained 5 different approaches to this problem using intuition and examples.The first technique is about merging the lists one by one.The second technique compares all the K candidate elements and selects the minimum.Both the techniques take O(NK) time.The third technique is about joining all the lists and applying merge sort.We can also do it by just copying the values.It takes O(NlogN) time.The fourth technique is based on Divide and Conquer technique which takes O(NlogK) time.The fifth technique is about heap which also takes O(NlogK) time.
The space complexity will be O(1) if we just manipulate pointers and merge the lists IN-PLACE without using any extra space, otherwise if we make a new linked list then that will be OUT OF PLACE algorithm which consumes extra space and so,space complexity in this case will be O(N).

CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)


==========================================PLEASE DONATE=============================
🧡 SUPPORT OUR WORK:   / techdose  
💚 UPI-ID: surya.kahar@ybl
💞JOIN Membership:    / @techdose4u  
==============================================================================
INSTAGRAM :   / surya.pratap.k  

LinkedIn:   / surya-pratap-kahar-47bb01168  

WEBSITE: https://techdose.co.in/

TELEGRAM Channel LINK: https://t.me/codewithTECHDOSE

TELEGRAM Group LINK: https://t.me/joinchat/SRVOIxWR4sRIVv5...
=======================================================================
USEFUL LINKS:
🟠Must do TIPS to ACE Virtual Interview:    • 🔴Must do Tips to ACE your virtual int...  
🟢Best strategy to excel your coding interview:    • 🔴Best strategy to excel your coding i...  
🟡Get your dream job in 1 month:    • 🔴Get your dream job in 1 month | 30 d...  
🔵How to crack dream job in just 2 months:    • How to crack dream job in just 2 months  
🟣7 Days DSA plan: https://techdose.co.in/7-days-dsa-che...



RELATED LINKS:
Power of Heap:    • Power of Heap  Concepts of Heap:    • Concepts of Heap | Understanding heap  Representation of Heap:    • Representation of Heap | Important Co...  Heapify Algorithm:    • Heapify Algorithm | Max Heapify | Min...  Build heap algorithm:    • Build Heap Algorithm | Proof of O(N) ...  Heap Algorithm:    • Heap Algorithms | Extract Max | Incre...  Heapsort Algorithm:    • Heapsort Algorithm | CODE Implementation  Heap Implementation:    • Heap Implementation | Push | Pop | CODE  Top K frequent elements:    • Top K Frequent Elements | Leetcode #3...  Sort a K-sorted array:    • Sort K sorted array | Sort nearly sor...  Sliding window maximum:    • Sliding Window Maximum | Leetcode #239  

CODE LINK: https://techdose.co.in/merge-k-sorted...




#heap #divideandconquer #mergelist