Theoery

This pattern helps us solve problems that involve a list of sorted arrays.

Whenever we are given ‘K’ sorted arrays, we can use a Heap to efficiently perform a sorted traversal of all the elements of all arrays. We can push the smallest (first) 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. We can, then, remove the top element from the heap to get the smallest element and push the next element from the same array, to which this smallest element belonged, to the heap. We can repeat this process to make a sorted traversal of all elements.

Questions

Given an array of ‘K’ sorted LinkedLists, merge them into one sorted list.

Example 1:

Input: L1=[2, 6, 8], L2=[3, 6, 7], L3=[1, 3, 4]
Output: [1, 2, 3, 3, 4, 6, 6, 7, 8]

Example 2:

Input: L1=[5, 8, 9], L2=[1, 7]
Output: [1, 5, 7, 8, 9]

Implementation: MergeKSortedLists

Since, the lists are individually sorted, locally (per list), the top element would be the minimum per list. We follow the logic in the theory section.

Time complexity

O(nlogk), where n is the total number of elements in k lists.

Space complexity

O(k), because at any time there are at-most k elements from k lists in the min heap.

Given ‘M’ sorted arrays, find the K’th smallest number among all the arrays.

Example 1:

Input: L1=[2, 6, 8], L2=[3, 6, 7], L3=[1, 3, 4], K=5
Output: 4
Explanation: The 5th smallest number among all the arrays is 4, this can be verified from 
the merged list of all the arrays: [1, 2, 3, 3, 4, 6, 6, 7, 8]

Example 2:

Input: L1=[5, 8, 9], L2=[1, 7], K=3
Output: 7
Explanation: The 3rd smallest number among all the arrays is 7.

Implementation: KthSmallestNumber

One option is we can merge all the lists and find the kth smallest element from the merged list. That would give us a time complexity of O(nlogk) and a space complexity of O(n), where n is the total number of elements in m lists.

Another option is, as we are merging, we keep a counter for k and return iff we reach the kth element. Here, we only use O(k) space.

Another consideration is, the inputs are arrays and not lists, so we can't use pointers. Instead, we need to keep track of the indices of the elements used.

Time complexity

O(nlogk)

Space complexity

O(k)

Given an N∗N matrix where each row and column is sorted in ascending order, find the Kth smallest element in the matrix.

Example 1:

Input: Matrix=[
    [2, 6, 8], 
    [3, 7, 10],
    [5, 8, 11]
  ], 
  K=5
Output: 7
Explanation: The 5th smallest number in the matrix is 7.

Implementation: KthSmallestMatrix

Since the rows are sorted and the columns are sorted in ascending order, a O(n^2) solution would be to iterate top-down column-by-column k times.

We can improve the time complexity by converting this problem into the one before, where * Each row is a list * There are N lists. * We need to find the kth smallest element from N lists, each of size N.

The algorithm would be similar to the previous one.

Time complexity

O(nlogn)

Space complexity

O(n)

Given ‘M’ sorted arrays, find the smallest range that includes at least one number from each of the ‘M’ lists.

Example 1:

Input: L1=[1, 5, 8], L2=[4, 12], L3=[7, 8, 10]
Output: [4, 7]
Explanation: The range [4, 7] includes 5 from L1, 4 from L2 and 7 from L3.

Example 2:

Input: L1=[1, 9], L2=[4, 12], L3=[7, 10, 16]
Output: [9, 12]
Explanation: The range [9, 12] includes 9 from L1, 12 from L2 and 10 from L3.

Implementation: SmallestRange

Dry run:

Input: L1=[1, 9], L2=[4, 12], L3=[7, 10, 16]

heap: [1,4,7], max: 7
1 -> range: [1,7]

heap: [4,7,9], max: 9
4 -> range: [4,9]

heap: [7,9,12], max: 12
7 -> range: [5,9], wont replace because 12-7 = 5 and 9-5 = 4, which is smaller

heap: [9,10,12], max: 12
9 -> range: [9,12]

-- stop here because L1 is exhausted --

The logic is: 1. We take a number from each of the list at a time so we got representations from all three lists. 2. Now if we can track the smallest range we see, that would be our solution, provided we only check till we have representations from all lists. 3. To check for the smallest range, we use a min-heap to find the smallest number and keep track of the max number as we insert numbers into the heap.

Time complexity

O(nlogm), where n is the total number of elements in m arrays.

Space complexity

O(m)

Given two sorted arrays in descending order, find ‘K’ pairs with the largest sum where each pair consists of numbers from both the arrays.

Example 1:

Input: L1=[9, 8, 2], L2=[6, 3, 1], K=3
Output: [9, 3], [9, 6], [8, 6] 
Explanation: These 3 pairs have the largest sum. No other pair has a sum larger than any of these.

Example 2:

Input: L1=[5, 2, 1], L2=[2, -1], K=3
Output: [5, 2], [5, -1], [2, 2] 

Implementation: LargestSumPair

Since, there are only 2 arrays, lets do a hack: we create all pair combinations. Then we push the pairs into a maxheap that compares the sum and returns the one with the greater sum.

Since there are only 2 arrays, the time complexity would still be O(nlogn), where n is the total number of elements in both the arrays.

Time complexity

O(nlogn)

Space complexity

O(n)

Return to Index