filmov
tv
Merge K Sorted Arrays - Min Heap Algorithm ('Merge K Sorted Lists' on LeetCode)
Показать описание
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Write a program that takes as input a set of sorted sequences and computes the union of these sequences as a sorted sequence.
This is basically the question "merge 2 sorted arrays" but now we have k sorted arrays.
Example:
Input
[ [3,5,7], [0,6], [0, 6, 28] ]
Output:
[0, 0, 3, 5, 6, 6, 7, 28]
Approach 1 (Brute Force)
Concatenate all arrays into one large array and sort the large array.
Sorting will always expense us O(n * log(n)) at the least when sorting non-special data that we only know a total ordering property for (then we can use merge sort or quick sort).
This does not use the fact that each array is sorted already which (should) help us on time complexity.
Approach 2
When building our final output array that is the sorted set of all the items we will be placing an item one by one from the original k arrays
What is are the items in each of those k arrays that interest us? The smallest items.
How can we keep track of the smallest item of the k smallest items respective to each array?
A min-heap is optimal.
Since we will hold at max k items in the min-heap we know what we will have at least O(k) time complexity where k is # of sorted arrays we need to maintain the smallest item across.
We will take the smallest item from the min-heap and remember the array it came from so that we can add the next item in that array to the min heap (if it exists).
Example Walkthrough:
Input
[ [3, 5, 7], [0, 6], [0, 6, 28] ]
Our output array will have size 8 [ _, _, _, _, _, _, _, _ ]
Let us step through this:
Initialize: Min Heap: [3, 0, 0]
[ 0, _, _, _, _, _, _, _ ]
Min Heap: [3, 0, 6] (0 came from array 2, we add the next item 6)
[ 0, 0, _, _, _, _, _, _ ]
Min Heap: [3, 6, 6] (0 came from array 3, we add the next item 6)
[ 0, 0, 3, _, _, _, _, _ ]
Min Heap: [5, 6, 6] (3 came from array 1, we add the next item 5)
[ 0, 0, 3, 5, _, _, _, _ ]
Min Heap: [7, 6, 6] (5 came from array 1, we add the next item 7)
[ 0, 0, 3, 5, 6, _, _, _ ]
Min Heap: [7, 6] (6 came from array 2, array 2 is finished)
[ 0, 0, 3, 5, 6, 6, _, _ ]
Min Heap: [7, 28] (6 came from array 3, we add the next item 28)
[ 0, 0, 3, 5, 6, 6, 7, _ ]
Min Heap: [28] (7 came from array 1, array 1 is finished)
[ 0, 0, 3, 5, 6, 6, 7, 28 ]
Min Heap: [] (28 came from array 3, array 3 is finished)
Output
[ 0, 0, 3, 5, 6, 6, 7, 28 ]
Complexities
Time: O( 2(n * log(k))) = O( n * log(k) )
Let n be the total elements across the k sorted arrays we are given.
Extracting and adding to the min heap will both take log(k) time.
For each of the n items, we will do an addition to the heap and removal from the heap (log(k) expense per heap operation).
Hence the times 2. It is dropped. We get O( n * log(k) ).
Space: O( k )
Our heap will need to hold k elements for most of this process and cannot worsen past this.
We are not counting the size of the output array which uses O(n) space since that isn't core to our algorithm.
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 11.1 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Write a program that takes as input a set of sorted sequences and computes the union of these sequences as a sorted sequence.
This is basically the question "merge 2 sorted arrays" but now we have k sorted arrays.
Example:
Input
[ [3,5,7], [0,6], [0, 6, 28] ]
Output:
[0, 0, 3, 5, 6, 6, 7, 28]
Approach 1 (Brute Force)
Concatenate all arrays into one large array and sort the large array.
Sorting will always expense us O(n * log(n)) at the least when sorting non-special data that we only know a total ordering property for (then we can use merge sort or quick sort).
This does not use the fact that each array is sorted already which (should) help us on time complexity.
Approach 2
When building our final output array that is the sorted set of all the items we will be placing an item one by one from the original k arrays
What is are the items in each of those k arrays that interest us? The smallest items.
How can we keep track of the smallest item of the k smallest items respective to each array?
A min-heap is optimal.
Since we will hold at max k items in the min-heap we know what we will have at least O(k) time complexity where k is # of sorted arrays we need to maintain the smallest item across.
We will take the smallest item from the min-heap and remember the array it came from so that we can add the next item in that array to the min heap (if it exists).
Example Walkthrough:
Input
[ [3, 5, 7], [0, 6], [0, 6, 28] ]
Our output array will have size 8 [ _, _, _, _, _, _, _, _ ]
Let us step through this:
Initialize: Min Heap: [3, 0, 0]
[ 0, _, _, _, _, _, _, _ ]
Min Heap: [3, 0, 6] (0 came from array 2, we add the next item 6)
[ 0, 0, _, _, _, _, _, _ ]
Min Heap: [3, 6, 6] (0 came from array 3, we add the next item 6)
[ 0, 0, 3, _, _, _, _, _ ]
Min Heap: [5, 6, 6] (3 came from array 1, we add the next item 5)
[ 0, 0, 3, 5, _, _, _, _ ]
Min Heap: [7, 6, 6] (5 came from array 1, we add the next item 7)
[ 0, 0, 3, 5, 6, _, _, _ ]
Min Heap: [7, 6] (6 came from array 2, array 2 is finished)
[ 0, 0, 3, 5, 6, 6, _, _ ]
Min Heap: [7, 28] (6 came from array 3, we add the next item 28)
[ 0, 0, 3, 5, 6, 6, 7, _ ]
Min Heap: [28] (7 came from array 1, array 1 is finished)
[ 0, 0, 3, 5, 6, 6, 7, 28 ]
Min Heap: [] (28 came from array 3, array 3 is finished)
Output
[ 0, 0, 3, 5, 6, 6, 7, 28 ]
Complexities
Time: O( 2(n * log(k))) = O( n * log(k) )
Let n be the total elements across the k sorted arrays we are given.
Extracting and adding to the min heap will both take log(k) time.
For each of the n items, we will do an addition to the heap and removal from the heap (log(k) expense per heap operation).
Hence the times 2. It is dropped. We get O( n * log(k) ).
Space: O( k )
Our heap will need to hold k elements for most of this process and cannot worsen past this.
We are not counting the size of the output array which uses O(n) space since that isn't core to our algorithm.
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 11.1 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.
0:11:25
Merge K Sorted Arrays - Min Heap Algorithm ('Merge K Sorted Lists' on LeetCode)
0:10:34
Merge K Sorted Lists - Leetcode 23 - Python
0:30:02
L25. Merge K Sorted Lists | Multiple Approaches
0:09:43
Heaps - Merge K sorted Arrays | C++ Placement Course
0:19:39
Merge k Sorted Arrays 🛑 @GeeksforGeeksVideos @facebookapp Interview question solutions Hindi @HelloW...
0:00:47
Merge K Sorted Linked Lists - Leetcode 23
0:50:01
Lecture 76: Heaps in C++ || Interview Questions || Part - 2
0:05:02
Merge K Sorted Lists
0:26:58
Merge k Sorted Lists - (Leetcode - 23) - (Google, Amazon, Microsoft..) : Explanation ➕ Live Coding
0:08:08
Merge k Sorted Lists | Live Coding with Explanation | Leetcode - 23
0:12:01
Merge K Sorted Lists - Divide and Conquer Approach
0:10:07
Merge K Sorted Linked Lists - Leetcode 23 - Heaps (Python)
0:22:21
Merge K sorted lists | Leetcode #23
0:01:00
HARD Faang Interview Question | Merge K Sorted Linked Lists - Leetcode 23
0:26:46
Interview Question: Merge K Sorted Arrays
0:23:42
Merge k sorted arrays | O(NKlog(K))| Priority Queue | Divide and Conquer
0:15:48
Merge k Sorted Lists | LeetCode 23 | C++
0:09:53
Leetcode - Merge k Sorted Lists (Python) (Revisited)
1:28:49
Heap Interview Problem: Merge K Sorted Linked List | Merge K Sorted Arrays
0:19:33
MERGE K SORTED LISTS | LEETCODE 23 | PYTHON OPTIMAL SOLUTIO
0:17:19
Merge K sorted arrays | Very Important problem and hard problem| Love Babbar DSA sheet
0:07:57
12.9 MERGE K SORTED ARRAYS (Heaps and Maps)-Interviewbit #heap#map#interview
0:08:20
Merge k Sorted Lists | Merge k Sorted Lists LeetCode Java | LeetCode - Hard- 23
0:24:39
Merge K Sorted Lists (LeetCode) | Interview Question Explained
Комментарии