DEV Community

Yaz

Posted on • Updated on

Merge Sorted Array - Leetcode 88 - TypeScript

Here's the Leetcode 88 solution using TypeScript.

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.