Merge Two Sorted Arrays in JavaScript

Introduction

Merging two sorted arrays is a common problem often encountered in coding interviews. The task requires combining two sorted integer arrays into a single sorted array. Here's a detailed guide on solving this problem efficiently with examples and different approaches.

Problem Statement

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order. Additionally, you are provided with integers m and n, representing the number of elements in nums1 and nums2, respectively.

• The final merged array must also be in non-decreasing order.
• nums1 has a size of m + n, where the last n elements are initialized to 0 to accommodate the elements of nums2.
• The solution should merge nums2 into nums1 in-place, meaning no additional array can be used.

Approach 1: Two Pointers (Forward)

The two-pointer technique is a standard solution for merging sorted arrays. Here's how it works:

1. Use two pointers to traverse nums1 and nums2.
2. Compare elements from both arrays and insert the smaller element into nums1.
3. Continue until all elements are merged.

Code Implementation:

1 function merge(nums1, m, nums2, n) {
2     let i = 0, j = 0;
3     while (i < m + j && j < n) {
4         if (nums1[i] >= nums2[j]) {
5             nums1.splice(i, 0, nums2[j]); // Insert nums2[j] into nums1
6             j++;
7         }
8         i++;
9     }
10 
11     // Append remaining elements of nums2
12     while (j < n) {
13         nums1[m + j] = nums2[j];
14         j++;
15     }
16 
17     // Remove extra zeros
18     nums1.length = m + n;
19 }

Approach 2: Optimized with Reverse Two Pointers

Instead of inserting elements and shifting them, this approach fills nums1 from the back, avoiding unnecessary shifts.

1. Use two pointers starting from the ends of the actual elements in nums1 and nums2.
2. Place the larger of the two elements at the end of nums1.
3. Continue until all elements from nums2 are placed in nums1.

Code Implementation:

1 function merge(nums1, m, nums2, n) {
2     let i = m - 1, j = n - 1, k = m + n - 1;
3 
4     while (i >= 0 && j >= 0) {
5         if (nums1[i] > nums2[j]) {
6             nums1[k--] = nums1[i--];
7         } else {
8             nums1[k--] = nums2[j--];
9         }
10     }
11 
12     // If nums2 still has remaining elements
13     while (j >= 0) {
14         nums1[k--] = nums2[j--];
15     }
16 }

Comparison of Approaches

1. Forward Two Pointers

• Advantages: Intuitive and easy to understand.
• Disadvantages: Slower due to the overhead of shifting elements in the array during insertion.

2. Reverse Two Pointers

• Advantages: Efficient and avoids unnecessary array operations like shifting.
• Disadvantages: Slightly more complex and harder to understand for beginners.

Example Execution

1 let nums1 = [1, 2, 3, 0, 0, 0];
2 let nums2 = [2, 5, 6];
3 let m = 3, n = 3;
4 
5 merge(nums1, m, nums2, n);
6 console.log(nums1); // Output: [1, 2, 2, 3, 5, 6]

Merging two sorted arrays efficiently is a fundamental problem that demonstrates proficiency in array manipulation and algorithm optimization. Using techniques like double pointers, especially reverse pointers, not only enhances performance but also showcases your problem-solving skills during interviews.