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

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

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

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 data from different sources, combining search results, and more. A common pitfall is to use a naive approach that doesn't take advantage of the fact that the input arrays are already sorted.

Approach

To solve this problem, we can use a two-pointer technique. This approach leverages the fact that both arrays are already sorted, allowing us to merge them in linear time.

Naive Solution

A naive solution would involve concatenating the two arrays and then sorting the resulting array. However, this approach is not optimal as it would have a time complexity of O((n + m) log(n + m)) due to the sorting step.

Optimized Solution

The optimized solution involves using two pointers, one for each array. We compare the elements at these pointers and append the smaller element to the result array, then move the pointer of the array from which the element was taken. This process continues until we have traversed both arrays.

Algorithm

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

1. Initialize two pointers, one for each array.
2. Initialize an empty result array.
3. While both pointers are within the bounds of their respective arrays:
   • Compare the elements at the pointers.
   • Append the smaller element to the result array.
   • Move the pointer of the array from which the element was taken.
4. Once one of the arrays is fully traversed, append the remaining elements of the other array to the result array.

Code Implementation

public class MergeSortedArrays {
    public static int[] merge(int[] first, int[] second) {
        int n = first.length;
        int m = second.length;
        int[] result = new int[n + m];
        int i = 0, j = 0, k = 0;

        // Traverse both arrays
        while (i < n && j < m) {
            if (first[i] <= second[j]) {
                result[k++] = first[i++];
            } else {
                result[k++] = second[j++];
            }
        }

        // Store remaining elements of first array
        while (i < n) {
            result[k++] = first[i++];
        }

        // Store remaining elements of second array
        while (j < m) {
            result[k++] = second[j++];
        }

        return result;
    }

    public static void main(String[] args) {
        int[] first = {1, 4, 8};
        int[] second = {1, 3, 4, 17};
        int[] mergedArray = merge(first, second);

        // Print the merged array
        for (int num : mergedArray) {
            System.out.print(num + " ");
        }
    }
}

Complexity Analysis

The time complexity of this algorithm is O(n + m) because we traverse each array once. The space complexity is also O(n + m) due to the additional space required for the result array.

Edge Cases

Consider the following edge cases:

• One or both arrays are empty.
• Arrays contain duplicate elements.
• Arrays of different lengths.

The algorithm handles these cases effectively by design.

Testing

To test the solution comprehensively, consider the following test cases:

• Both arrays are empty: first = [], second = []
• One array is empty: first = [1, 2, 3], second = []
• Arrays with duplicate elements: first = [1, 2, 2], second = [2, 3, 4]
• Arrays of different lengths: first = [1], second = [2, 3, 4, 5]

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

• Understand the problem constraints and leverage them (e.g., arrays are sorted).
• Think about efficient ways to merge or combine data.
• Practice similar problems to improve 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 improving algorithmic thinking and coding skills.

Additional Resources

For further reading and practice, consider the following resources:

• LeetCode: Merge Sorted Array
• GeeksforGeeks: Merge Two Sorted Arrays
• Coding Ninjas: Merge Two Sorted Arrays