Problem Statement:
You are given two sorted arrays - A and B, containing N and M elements respectively. Your task is to merge these two sorted arrays into a single sorted array.
Write a code that runs in O(N + M) time complexity, ensuring that the merged array maintains the sorted order.
Approach:
The key idea of this problem is to use a two-pointer technique. Since both arrays are already sorted, we can efficiently merge them by comparing the current elements of each array one by one. Here’s how we can do it:
-
Start with two pointers, one for each array (A and B). Initially, both pointers are at the beginning of their respective arrays.
-
Compare the elements at these pointers:
- If the element in A is smaller, add it to the result array and move the pointer in A forward.
- If the element in B is smaller, add it to the result array and move the pointer in B forward.
-
Continue this process until one of the arrays is completely processed.
-
Once you finish one of the arrays, simply add the remaining elements of the other array to the result array since they are already sorted.
This approach ensures that we only pass through each element of both arrays once, leading to an efficient solution.
Time Complexity:
O(N + M), as we process each element of both arrays exactly once.
Space Complexity:
O(N + M), due to the extra space needed for the merged result.