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`

.

## 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.

## Top comments (0)