## Question

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

The final sorted array should not be returned by the function, but instead be *stored inside the array *`nums1`

. To accommodate this, `nums1`

has a length of `m + n`

, where the first `m`

elements denote the elements that should be merged, and the last `n`

elements are set to `0`

and should be ignored. `nums2`

has a length of `n`

.

## The Efficient Approach

To solve this problem efficiently, we utilize a technique that involves iterating from the end of the arrays rather than the beginning. This is a strategic move as it allows us to fill `nums1`

from the end, avoiding the overwriting of elements that we have not yet processed.

### The Solution: Step-by-Step

Here is a JavaScript function that elegantly solves this problem:

javascriptCopy code

```
def merge(nums1, m, nums2, n):
i = m - 1 # Pointer for the last element in the original part of nums1
j = n - 1 # Pointer for the last element in nums2
k = m + n - 1 # Pointer for the last position in nums1
while j >= 0:
if i >= 0 and nums1[i] > nums2[j]:
nums1[k] = nums1[i] # Place the larger element at the end of nums1
k -= 1
i -= 1
else:
nums1[k] = nums2[j] # Place the element from nums2 in nums1
k -= 1
j -= 1
```

How Does This Work?

**Initialization**: We start by initializing three pointers:

`i`

points to the last element of the original`nums1`

.`j`

points to the last element of`nums2`

.`k`

is set to the last position of the`nums1`

array.

**Merging**: The `while`

loop continues as long as there are elements in `nums2`

(i.e., `j >= 0`

). Inside the loop, we compare the elements pointed to by `i`

and `j`

.

- If
`nums1[i]`

is greater than`nums2[j]`

, we place`nums1[i]`

in the position pointed to by`k`

in`nums1`

, and decrement both`i`

and`k`

. - Otherwise, we place
`nums2[j]`

in the position pointed to by`k`

, and decrement both`j`

and`k`

.

**No Need to Handle Remaining**: Since we are filling`nums1`

Elements`nums1`

from the end, if there are any elements left in the original`nums1`

array, they are already in their correct position.**In-Place Operation**: The entire operation is done within the`nums1`

array, ensuring that the space complexity remains constant, i.e., O(1).

## Complexity Analysis

**Time Complexity**: O(m+n) - Each element in both`nums1`

and`nums2`

is looked at a maximum of once.**Space Complexity**: O(1) - No extra space is used; all operations are performed in-place.

## Conclusion

This solution to LeetCode 88 demonstrates a clever use of pointers and in-place array manipulation. It's an efficient and elegant approach that handles the merging with a minimal time and space complexity, showcasing the power of algorithmic thinking in solving coding problems.

Checkout more Leetcode solutions.