Merge Two Sorted interval lists

Question

Given three sorted matrixs, merge them into a single sorted result.

Codemia · Accepted Answer

In this problem, we are tasked with merging three sorted matrices (lists of intervals) into a single sorted result. The key pattern that applies here is the **Two Pointers Technique**. This approach is ideal because we can maintain pointers for each of the three input lists and efficiently traverse them while comparing the current elements. Since the input lists are already sorted, we can take advantage of this ordering to merge them in linear time. By using three pointers, one for each matrix, we can easily determine the smallest element among the current elements pointed to by our pointers, thereby maintaining the sorted order in the merged output.

1. **Initialization**: Start by initializing three pointers, one for each of the three sorted lists (let's call them `p1`, `p2`, and `p3`), all set to 0. Also, create an empty list `merged_intervals` to store the merged result.

2. **Traversal**: Use a loop to iterate while any of the pointers are within the bounds of their respective lists. On each iteration:
   - Compare the elements at the current positions of the three pointers.
   - Determine the smallest element among the three. Append this smallest element to `merged_intervals` and increment the corresponding pointer.

3. **Handling Remaining Elements**: After one of the lists is fully traversed, check the remaining lists and append any remaining intervals to `merged_intervals` until all lists are exhausted.

**Example**: Given lists:
- `matrix1 = [[1, 3], [5, 7]]`
- `matrix2 = [[2, 4], [6, 8]]`
- `matrix3 = [[0, 5], [9, 10]]`

The first iteration picks `[0, 5]` from `matrix3`, then the next would pick `[1, 3]` from `matrix1`, and so on, producing a merged output like `[[0, 5], [1, 3], [2, 4], [5, 7], [6, 8], [9, 10]]`.

Here is a Python implementation of the above approach:
```python
def merge_three_sorted_intervals(matrix1, matrix2, matrix3):
    merged_intervals = []
    p1, p2, p3 = 0, 0, 0
    len1, len2, len3 = len(matrix1), len(matrix2), len(matrix3)

while p1 < len1 or p2 < len2 or p3 < len3:
        min_interval = None

# Check if current pointers are valid and find the minimum
        if p1 < len1 and (min_interval is None or matrix1[p1][0] < min_interval[0]):
            min_interval = matrix1[p1]
        if p2 < len2 and (min_interval is None or matrix2[p2][0] < min_interval[0]):
            min_interval = matrix2[p2]
        if p3 < len3 and (min_interval is None or matrix3[p3][0] < min_interval[0]):
            min_interval = matrix3[p3]

# Append the smallest interval found
        merged_intervals.append(min_interval)

# Increment the pointer for the list from which the interval was taken
        if min_interval == matrix1[p1]:
            p1 += 1
        elif min_interval == matrix2[p2]:
            p2 += 1
        else:
            p3 += 1

return merged_intervals
```
This function effectively merges the three sorted matrices into one sorted list of intervals.

The time complexity of this solution is **O(n)**, where `n` is the total number of intervals across all three matrices. This is because each interval is processed exactly once. The space complexity is also **O(n)** for storing the merged intervals. This is optimal given that we need to return the merged intervals, and it directly correlates with the input size.

1. **Empty Input**: If all three matrices are empty, the output should be an empty list. 
   - Input: `([], [], [])` → Output: `[]`

2. **One Matrix Empty**: If one of the matrices is empty while others contain intervals, the output should simply be the merged intervals of the non-empty matrices. 
   - Input: `([[1, 2]], [], [[3, 4]])` → Output: `[[1, 2], [3, 4]]`

3. **Overlapping Intervals**: If the intervals overlap in any of the matrices, the intervals should still be merged correctly, ensuring overlapping intervals are combined in the output. 
   - Input: `([[1, 4]], [[2, 3]], [[5, 6]])` → Output: `[[1, 4], [5, 6]]`

4. **All Intervals Identical**: If all intervals are identical across the matrices, ensure that duplicates are managed and only one instance is included in the result. 
   - Input: `([[1, 2]], [[1, 2]], [[1, 2]])` → Output: `[[1, 2]]`.

Merge Two Sorted interval lists

Optiver

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Optiver Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string