LeetCode Solution #88: Merge Sorted Array in JavaScript

In this post, we will discuss the solution to LeetCode problem #88: Merge Sorted Array. This problem involves merging two sorted arrays into a single sorted array.

Before we discuss the solution, let's go over the problem statement and constraints.

Problem Statement

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note that the number of elements initialized in nums1 and nums2 are m and n respectively.

You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Constraints

• -10^9 <= nums1[i], nums2[i] <= 10^9
• 0 <= m, n <= 10^6
• 0 <= m + n <= 10^6

Example

Input:

nums1 = [1,2,3,0,0,0]

m = 3

nums2 = [2,5,6]

n = 3

Output:

Copy code

[1,2,2,3,5,6]

Now that we understand the problem, let's discuss a solution.

Solution

The solution to this problem is quite simple. We can iterate over the two arrays, nums1 and nums2, and merge them into a single array by comparing their elements.

To do this, we can use two pointers, i and j, to keep track of the current positions in nums1 and nums2 respectively. We can then iterate over the elements in nums1 and nums2, comparing their values and adding the smaller element to the result array.

Here is the pseudocode for this solution:

function merge(nums1, m, nums2, n):
  result = []
  i = 0
  j = 0
  while i < m and j < n:
    if nums1[i] < nums2[j]:
      result.append(nums1[i])
      i += 1
    else:
      result.append(nums2[j])
      j += 1


  # Add remaining elements
  while i < m:
    result.append(nums1[i])
    i += 1
  while j < n:
    result.append(nums2[j])
    j += 1


  return result

This solution is simple and has a time complexity of O(m+n) since we have to iterate over both nums1 and nums2.

JavaScript Code:

function merge(nums1, m, nums2, n) {
  // initialize pointers to the start of each input array
  let i = 0;
  let j = 0;

  // initialize the result array
  const result = [];

  // iterate over the input arrays until one of them is empty
  while (i < m && j < n) {
    // add the smaller of the two values at the current pointers to the result array
    if (nums1[i] < nums2[j]) {
      result.push(nums1[i]);
      i++;
    } else {
      result.push(nums2[j]);
      j++;
    }
  }

  // add any remaining elements from nums1 to the result array
  while (i < m) {
    result.push(nums1[i]);
    i++;
  }

  // add any remaining elements from nums2 to the result array
  while (j < n) {
    result.push(nums2[j]);
    j++;
  }

  // copy the result array back into nums1
  for (let k = 0; k < m + n; k++) {
    nums1[k] = result[k];
  }
}

Conclusion

In this post, we discussed a solution to LeetCode problem #88: Merge Sorted Array. This problem is a simple application of the merge operation on two sorted arrays. We discussed a simple solution that has a time complexity of O(m+n), where m and n are the lengths of nums1 and nums2 respectively.