Arrays can be either in ascending or descending order. The merged array must preserve the order of the input arrays.
Using Binary Heap - O(nklog(k)) time
/*
Using Binary Heap (Optimized)
Time Complexity - O(nklog(k))
- Heap size will be k. So Heapifying is O(log(k))
- We're going to be heapifying n * k elements. Therefore, T(n) = O(nklog(k))
Space Complexity - O(nk) + O(k) from the heap.
*/
function mergeArrays(arrays) {
const merged = [],
increasingOrder = isIncreasingOrder(arrays)
// [0]
const heap = increasingOrder ? new MinBinaryHeap() : new MaxBinaryHeap()
// [1]
arrays.forEach((arr, i) => {
heap.insert(new HeapNode(i, 0, arr[0]))
})
heap.heapify()
if (increasingOrder) {
// [2]
while (heap.top.value !== Infinity) {
getAndInsertNextVal(arrays, heap, merged, Infinity)
}
} else {
while (heap.top.value !== -Infinity) {
getAndInsertNextVal(arrays, heap, merged, -Infinity)
}
}
return merged
}
/*
Notes:
[0] Create min or max heap based on order
[1] - Insert first element of all arrays into heap.
- Each heap item will be an instance of HeapNode which will keep track of
the arrIndex, elementIndex & value.
[2] - Keep getting heap top(min) & pushing it into the merged array.
- If the min value is Infinity, we've reached the end of all arrays
*/
/*
getAndInsertNextVal:
- Function to get the top(min or max val), push top val into merged
& insert next array value into heap
- instead of extracting & inserting, we're going to swap the new value with the top value.
So we don't have to re-heapify twice for extraction & insertion
- We'll use the arrIndex, elementIndex from the heap top to get the next item to insert
- If we're at the end of the array insert Infinity(min heap or increasing order) or -Infinity
*/
function getAndInsertNextVal(arrays, heap, merged, infinity) {
const n = arrays[0].length
let top = heap.top
merged.push(top.value)
const arrIndex = top.arrIndex,
elementIndex = top.elementIndex + 1,
value = elementIndex >= n ? infinity : arrays[arrIndex][elementIndex]
heap.swapTop(new HeapNode(arrIndex, elementIndex, value))
heap.sinkDown(0)
}
// HeapNode will keep track of the array index, the element index & the value
class HeapNode {
constructor(arrIndex, elementIndex, value) {
this.arrIndex = arrIndex
this.elementIndex = elementIndex
this.value = value
}
}
// Modified Binary Heaps
// Unmodified Binary Heap implementation here --> https://blog.mrinalini.dev/posts/binary-heap/
class BinaryHeap {
constructor() {
this.heapArr = []
}
// Getters
get size() {
return this.heapArr.length
}
get top() {
return this.heapArr[0]
}
// Class methods
insert(node) {
this.heapArr[this.size] = node
}
swapTop(newNode) {
this.heapArr[0] = newNode
}
heapify() {
const lastIndex = this.size - 1
for (let i = lastIndex; i >= 0; i--) {
this.sinkDown(i)
}
}
// sinkDown will be different for max & min heap
sinkDown(p) {}
}
// Min Binary Heap for increasing sort order
class MinBinaryHeap extends BinaryHeap {
constructor() {
super()
}
sinkDown(p) {
const element = this.heapArr[p].value,
lastIndex = this.heapArr.length - 1
while (p < lastIndex) {
const r = 2 * p + 2,
l = r - 1,
left = this.heapArr[l] && this.heapArr[l].value,
right = this.heapArr[r] && this.heapArr[r].value
let swapIndex = null,
min = element
if (l <= lastIndex && left < min) {
swapIndex = l
min = left
}
if (r <= lastIndex && right < min) {
swapIndex = r
}
if (swapIndex == null) break
swap(this.heapArr, p, swapIndex)
p = swapIndex
}
}
}
// Max Binary Heap for decreasing sort order
class MaxBinaryHeap extends BinaryHeap {
constructor() {
super()
}
sinkDown(p) {
const element = this.heapArr[p].value,
lastIndex = this.heapArr.length - 1
while (p < lastIndex) {
const r = 2 * p + 2,
l = r - 1,
left = this.heapArr[l] && this.heapArr[l].value,
right = this.heapArr[r] && this.heapArr[r].value
let swapIndex = null,
max = element
if (l <= lastIndex && left > max) {
swapIndex = l
max = left
}
if (r <= lastIndex && right > max) {
swapIndex = r
}
if (swapIndex == null) break
swap(this.heapArr, p, swapIndex)
p = swapIndex
}
}
}
/*
isIncreasingOrder - Function to get the sort order of the arrays
*/
function isIncreasingOrder(arrays) {
let i = 0,
k = arrays.length
while (i < k) {
const arr = arrays[i],
len = arr.length
for (let j = 1; j < len; j++) {
const diff = arr[j] - arr[j - 1]
if (diff > 0) return true
else if (diff < 0) return false
else continue
}
i++
}
return false
}
function swap(arr, i, j) {
const temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}The next three strategies will be using some variation of merge sort.
Common Helpers
isIncreasingOrder and merge functions will be same for the next three strategies. So I'm just going to write it once.
/*
merge
- Same as merge from merge sort but NOT in place and need to consider if
the values are in ascending order or descending.
*/
function merge(arr1, arr2, increasingOrder) {
const len1 = arr1.length,
len2 = arr2.length,
merged = []
let i = 0,
j = 0
function mergeSortedIncreasing() {
while (i < len1 && j < len2) {
if (arr1[i] <= arr2[j]) {
merged.push(arr1[i++])
} else {
merged.push(arr2[j++])
}
}
}
function mergeSortedDecreasing() {
while (i < len1 && j < len2) {
if (arr1[i] >= arr2[j]) {
merged.push(arr1[i++])
} else {
merged.push(arr2[j++])
}
}
}
increasingOrder ? mergeSortedIncreasing() : mergeSortedDecreasing()
while (i < len1) merged.push(arr1[i++])
while (j < len2) merged.push(arr2[j++])
return merged
}
// --------------------------------------------------------------
/*
isIncreasingOrder
- Function to get the sort order of the arrays
- Can't just check the first two values of the first array cause they might be repeated values
- So keep checking until two values are different & return true or false
*/
function isIncreasingOrder(arrays) {
let i = 0,
k = arrays.length
while (i < k) {
const arr = arrays[i],
len = arr.length
for (let j = 1; j < len; j++) {
const diff = arr[j] - arr[j - 1]
if (diff > 0) return true
else if (diff < 0) return false
else continue
}
i++
}
return false
}Recursive Merge Sort - O(nklog(k)) time
We'll use merge sort to divide and recurse to the bottom until there is only array left. Each successive merge call will merge and return the merged array that will double in size until it gets to n*k size.
/*
Time Complexity - O(nklog(k))
Space Complexity - O(nk)
*/
function mergeArrays(arrays) {
const increasingOrder = isIncreasingOrder(arrays)
return mergeSort(arrays, increasingOrder)
}
// --------------------------------------------------------------
function mergeSort(arr, increasingOrder) {
const len = arr.length
if (len <= 1) {
return arr[0]
}
const mid = Math.floor(len / 2),
left = mergeSort(arr.slice(0, mid), increasingOrder),
right = mergeSort(arr.slice(mid), increasingOrder)
return merge(left, right, increasingOrder)
}Using Iterative or "Bottom Up" Merge Sort - O(nklog(k)) time
/*
Space Complexity - < O(k*n x log(n)). Because the actual array is being overwritten.
So at each level, it's kn - n * number of merged arrays
Time Complexity — O( kn x log(k)), where n is length of each array and k is the total number of arrays
*/
function mergeArrays(arr) {
let total = arr.length,
interval = 1
const sortOrder = isIncreasingOrder(arr)
while (interval < total) {
for (let i = 0; i < total - interval; i += interval * 2) {
arr[i] = merge(arr[i], arr[i + interval], sortOrder)
}
interval *= 2
}
return arr[0]
}
Calculating Time Complexity for Solution using Iterative Merge Sort
Calculating Space Complexity for Solution using Iterative Merge Sort
Brute Force Attempt - O(nk^2) time
This was my first attempt.
/*
First intuition
- Iterate through arrays and merge one array with the current merged(result) array
Time Complexity — O(nk^2), where n is length of each array and k is the total number of arrays
Space Complexity - O(n*k)
Array of k arrays of length n
[ [ n ] [ n ] [ n ] .... [ n ]]
1 2 3 ... k
| iteration | work done at iteration |
| --------- | ---------------------- |
| 1 | 0 + n |
| 2 | n + n |
| 3 | 2n + n |
| ... | ... |
| k | (k-1) + n |
Total work done = n + 2n + 3n + .... + kn
T(n) = n * (1 + 2 + ..... + k)
https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF
kth partial sum of the series from 1 to k is:
k(k + 1)/2
Therefore, T(n) = nk^2
*/
function mergeArrays(arrays) {
const k = arrays.length,
increasingOrder = isIncreasingOrder(arrays)
let merged = []
for (let i = 0; i < k; i++) {
merged = merge(arrays[i], merged, increasingOrder)
}
return merged
}Tests:
let arr0 = [
[-10, -8, -6, -4, -2],
[-9, -7, -5, -4, -3],
[-1, 1, 3, 5, 7],
[0, 2, 4, 6, 8],
]
let arr1 = [
[5, 6, 8, 16],
[3, 7, 12, 13],
[1, 10, 11, 15],
[2, 4, 9, 14],
]
let arr2 = [
[200, 50, 18, 1],
[180, 45, 15, 9],
[30, 17, 8, 5],
[190, 40, 12, 7],
]
console.log(mergeArrays(arr0))
console.log(mergeArrays(arr1))
console.log(mergeArrays(arr2))