Merge two sorted arrays in O(n + m) time using C++

Given two sorted arrays of integers, merge them into one sorted array containing all numbers

Example:

Input: first =[1, 4, 8],
       second = [1, 3, 4, 17]

Output: [1, 1, 3, 4, 4, 8, 17]

Note:

Your algorithm should run in O(n + m) time and use O(n + m) extra space.

Understanding the Problem

The core challenge of this problem is to merge two already sorted arrays into a single sorted array efficiently. This problem is significant in various applications such as merging results from two sorted datasets, combining sorted logs, or merging sorted lists in database queries.

Potential pitfalls include not handling duplicate elements correctly or not maintaining the sorted order during the merge process.

Approach

To solve this problem, we can use a two-pointer technique. This approach is efficient because it leverages the fact that both input arrays are already sorted.

Here’s a step-by-step breakdown of the approach:

Initialize two pointers, one for each array.
Compare the elements at the current positions of the two pointers.
Append the smaller element to the result array and move the corresponding pointer forward.
If one array is exhausted, append the remaining elements of the other array to the result array.

This approach ensures that we traverse each array only once, resulting in a time complexity of O(n + m), where n and m are the lengths of the two arrays.

Algorithm

Here is a detailed step-by-step breakdown of the algorithm:

Initialize two pointers, i and j, to 0.
Create an empty result array.
While both pointers are within the bounds of their respective arrays:
1. Compare the elements at first[i] and second[j].
2. Append the smaller element to the result array.
3. Move the pointer of the array from which the element was taken forward by one.
Once one of the arrays is exhausted, append the remaining elements of the other array to the result array.

Code Implementation

#include <iostream>
#include <vector>

std::vector<int> mergeSortedArrays(const std::vector<int>& first, const std::vector<int>& second) {
    std::vector<int> result;
    int i = 0, j = 0;
    
    // Traverse both arrays
    while (i < first.size() && j < second.size()) {
        if (first[i] <= second[j]) {
            result.push_back(first[i]);
            i++;
        } else {
            result.push_back(second[j]);
            j++;
        }
    }
    
    // Store remaining elements of the first array
    while (i < first.size()) {
        result.push_back(first[i]);
        i++;
    }
    
    // Store remaining elements of the second array
    while (j < second.size()) {
        result.push_back(second[j]);
        j++;
    }
    
    return result;
}

int main() {
    std::vector<int> first = {1, 4, 8};
    std::vector<int> second = {1, 3, 4, 17};
    
    std::vector<int> mergedArray = mergeSortedArrays(first, second);
    
    std::cout << "Merged array: ";
    for (int num : mergedArray) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

Complexity Analysis

The time complexity of this approach is O(n + m) because we traverse each element of both arrays exactly once. The space complexity is also O(n + m) because we store the merged result in a new array.

Edge Cases

Consider the following edge cases:

One or both input arrays are empty. The algorithm should handle this by returning the non-empty array or an empty array if both are empty.
Arrays with duplicate elements. The algorithm should correctly merge and include all duplicates.

Example edge cases:

Input: first = [], second = [1, 2, 3]
Output: [1, 2, 3]

Input: first = [1, 2, 3], second = []
Output: [1, 2, 3]

Input: first = [1, 1, 1], second = [1, 1, 1]
Output: [1, 1, 1, 1, 1, 1]

Testing

To test the solution comprehensively, consider a variety of test cases:

Simple cases with small arrays.
Cases where one array is significantly larger than the other.
Cases with duplicate elements.
Edge cases with empty arrays.

Using a testing framework like Google Test can help automate and manage these tests effectively.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Understand the problem requirements and constraints thoroughly.
Leverage the properties of the input data (e.g., sorted arrays) to devise an efficient solution.
Break down the problem into smaller, manageable steps.
Consider edge cases and test your solution against them.

Practice solving similar problems and studying algorithms to improve your problem-solving skills.

Conclusion

In this blog post, we discussed how to merge two sorted arrays efficiently using a two-pointer technique. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong algorithmic thinking and problem-solving skills.

Keep practicing and exploring further to enhance your understanding and proficiency in algorithms and data structures.

Additional Resources

For further reading and practice, consider the following resources: