# K-way Merge

In this blog post, I will be giving a brief introduction about another data structure that is very important for technical interviews.This data structure is called K-way Merge. This pattern is very useful to solve problems that involve a sets of sorted arrays. Whenever, we are given K sorted arrays, we can use a Heap to efficiently perform a sorted traversal of all elements of all arrays.

We can push the smallest element of each sorted array in a Min Heap to get the overall minimum. While inserting elements to the Min Heap, we keep track of which array the element came from.

The K-way Merge pattern looks like this;

1. We can push the smallest (first) element of each sorted array in a Min Heap to get the overall minimum.

For this pattern,

Time Complexity = O(N log K) where N is the total number of elements in all the K input arrays.

Space Complexity = O(K)

Ways to identify this pattern:

• For this kind of pattern, the problem will feature sorted arrays, lists, or a matrix

References:

--

--

## More from anil gurung

Student at Flatiron School