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

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 be to concatenate the two arrays and then sort the resulting array. However, this approach is not optimal as it has a time complexity of O((n + m) log(n + m)) due to the sorting step.

Optimized Solution

The optimized solution involves using two pointers to traverse both arrays and compare their elements. We initialize two pointers, one for each array, and iterate through both arrays, adding the smaller element to the result array and moving the corresponding pointer forward. This ensures that we maintain the sorted order in the result array.

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 current pointers.
   • Add the smaller element to the result array.
   • Move the pointer of the array from which the smaller element was taken.
4. Once one of the arrays is exhausted, add the remaining elements of the other array to the result array.

Code Implementation

function mergeSortedArrays(first, second) {
  // Initialize pointers for both arrays
  let i = 0;
  let j = 0;
  // Initialize the result array
  let result = [];

  // Traverse both arrays
  while (i < first.length && j < second.length) {
    // Compare elements at the current pointers
    if (first[i] < second[j]) {
      // Add the smaller element to the result array
      result.push(first[i]);
      // Move the pointer of the first array
      i++;
    } else {
      // Add the smaller element to the result array
      result.push(second[j]);
      // Move the pointer of the second array
      j++;
    }
  }

  // Add remaining elements of the first array, if any
  while (i < first.length) {
    result.push(first[i]);
    i++;
  }

  // Add remaining elements of the second array, if any
  while (j < second.length) {
    result.push(second[j]);
    j++;
  }

  return result;
}

// Example usage
const first = [1, 4, 8];
const second = [1, 3, 4, 17];
console.log(mergeSortedArrays(first, second)); // Output: [1, 1, 3, 4, 4, 8, 17]

Complexity Analysis

The time complexity of this algorithm is O(n + m), where n and m are the lengths of the two input arrays. This is because we traverse each array exactly once. The space complexity is also O(n + m) due to the result array that stores all elements from both input arrays.

Edge Cases

Potential edge cases include:

• One or both input arrays being empty.
• Arrays containing duplicate elements.
• Arrays of different lengths.

Our algorithm handles these edge cases effectively by ensuring that all elements are added to the result array in sorted order.

Testing

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

• Both arrays are empty: mergeSortedArrays([], []) should return [].
• One array is empty: mergeSortedArrays([1, 2, 3], []) should return [1, 2, 3].
• Arrays with duplicate elements: mergeSortedArrays([1, 2, 2], [2, 3, 4]) should return [1, 2, 2, 2, 3, 4].
• Arrays of different lengths: mergeSortedArrays([1], [2, 3, 4, 5]) should return [1, 2, 3, 4, 5].

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

• Understand the problem constraints and leverage any given properties (e.g., sorted arrays).
• Think about efficient ways to merge or combine data without unnecessary operations.
• Practice similar problems to develop a strong understanding of common patterns and techniques.

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 problem-solving skills and preparing for technical interviews.

Additional Resources

For further reading and practice, consider the following resources:

• LeetCode: Merge Sorted Array
• GeeksforGeeks: Merge Two Sorted Arrays
• HackerRank: Merge Two Sorted Linked Lists