Merge Sorted Array - Leetcode 88 - TypeScript

Here's the Leetcode 88 solution using TypeScript.

Watch on YouTube

Leetcode 88 - Merge Sorted Array

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

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

Approach

Since both arrays are sorted, you can use two pointers to compare elements from the end of both arrays.

You'll use two pointers (m and n) initially set to the lengths of nums1 and nums2.

Then you can compare the elements at these positions, and the larger element is placed at the end of nums1.

Then you'll decrement the pointers and the position in nums1 accordingly.

You should continue this process until either of the arrays is fully merged.

If there are remaining elements in nums2 after the first loop, you'll add them to the beginning of nums1.

View on Excalidraw

Code Implementation

function merge(nums1: number[], m: number, nums2: number[], n: number): void {
  let last = m + n - 1

  while (m > 0 && n > 0) {
    if (nums1[m - 1] > nums2[n - 1]) {
      nums1[last] = nums1[m - 1]
      m -= 1
    } else {
      nums1[last] = nums2[n - 1]
      n -= 1
    }
    last -= 1
  }

  while (n > 0) {
    nums1[last] = nums2[n - 1]
    n -= 1
    last -= 1
  }
}

Time Complexity

This solution has the time complexity of O(m + n), where m and n are the lengths of the input arrays nums1 and nums2.

The algorithm iterates through the arrays once, and at each step, it compares and places elements in the correct position.

Since the length of the merged array is m + n, the time complexity is linear with respect to the combined length of both input arrays.

Space Complexity

The space complexity is O(1) or constant.

The algorithm performs the merging in-place without using any additional space that scales with the input size.

We use a constant amount of extra space for variables like last, m, n, and the loop control variables.

This makes the algorithm memory-efficient, as the space required to perform this algorithm remains constant regardless of the input size.