Merge Two Sorted strings

Question

Given two sorted arrays, merge them into a single sorted result.

Codemia · Accepted Answer

To merge two sorted arrays into a single sorted result, we can utilize the **two pointers** technique. This method is ideal here because both arrays are already sorted, allowing us to efficiently traverse both arrays simultaneously. Each pointer will keep track of the current index in each array, and we can compare the elements at these indices to build the merged result. By always choosing the smaller element from either array to add to our result, we ensure that the merged array remains sorted.

1. Initialize two pointers, `i` and `j`, to 0 for both arrays `arr1` and `arr2` respectively. 
2. Create an empty list `merged` to store the merged result. 
3. While both pointers are within the bounds of their respective arrays:  
   - Compare `arr1[i]` and `arr2[j]`. 
   - If `arr1[i]` is smaller or equal, append it to `merged` and increment `i`. 
   - Otherwise, append `arr2[j]` to `merged` and increment `j`. 
4. If one of the arrays is exhausted before the other, append the remaining elements of the other array to `merged`. 
5. Return `merged` as the final result.

**Example:** For `arr1 = [1, 3, 5]` and `arr2 = [2, 4, 6]`, the process would look like this:
- Compare 1 and 2: Add 1 to merged. (merged = [1]) 
- Compare 3 and 2: Add 2 to merged. (merged = [1, 2]) 
- Compare 3 and 4: Add 3 to merged. (merged = [1, 2, 3]) 
- Compare 5 and 4: Add 4 to merged. (merged = [1, 2, 3, 4]) 
- Add remaining elements 5 and 6 to merged. Final merged = [1, 2, 3, 4, 5, 6].

```python
def merge_sorted_arrays(arr1, arr2):
    i, j = 0, 0
    merged = []

while i < len(arr1) and j < len(arr2):
        if arr1[i] <= arr2[j]:
            merged.append(arr1[i])
            i += 1
        else:
            merged.append(arr2[j])
            j += 1

# Append any remaining elements
    while i < len(arr1):
        merged.append(arr1[i])
        i += 1
    while j < len(arr2):
        merged.append(arr2[j])
        j += 1

return merged
```

**Usage Example:** 
```python
arr1 = [1, 3, 5]
arr2 = [2, 4, 6]
result = merge_sorted_arrays(arr1, arr2)
print(result)  # Output: [1, 2, 3, 4, 5, 6]
```

The time complexity of this algorithm is **O(n + m)**, where `n` is the length of `arr1` and `m` is the length of `arr2`. This is because we traverse each array only once. The space complexity is also **O(n + m)** due to the space required to store the merged array. Given the constraints that the input arrays are sorted and can be of varying lengths, this approach is efficient and optimal.

1. **Both arrays are empty:** `arr1 = []`, `arr2 = []` should return `[]`. 
2. **One array is empty:** For `arr1 = []` and `arr2 = [1, 2, 3]`, the result should be `[1, 2, 3]`. 
3. **Identical elements:** If both arrays contain the same elements, for instance, `arr1 = [1, 1, 1]` and `arr2 = [1, 1]`, the result should be `[1, 1, 1, 1, 1]`. 
4. **Arrays of different lengths:** Ensure proper merging when one array is significantly longer than the other, e.g., `arr1 = [1, 2, 3]` and `arr2 = [4]` should yield `[1, 2, 3, 4]`.

Merge Two Sorted strings

HashiCorp

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

HashiCorp Machine Learning 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