> For the complete documentation index, see [llms.txt](https://private-26.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://private-26.gitbook.io/notes/coding/hard/88.-merge-sorted-array.md).

# 88. Merge Sorted Array

Given two sorted array the goal is to merge them

```
Input
nums1 = [1,2,3,0,0,0], m = 3, 
nums2 = [2,5,6], n = 3

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

the first array has capacity to hold to the merged sorted array.

***

### Intuition

* Uses two pointers two track the current position in respective arrays
* Since `nums1` is of size $m+n$ use this extra space to store the merged array.

### Approach

* Iterate through the arrays from the end and place the larger element in the end of `nums1`.

### Complexity

* **Time complexity** : $\text{O}(m+n)$
  * Since we iterate over the $m+n$ array elements only once.
* **Space complexity** : $\text{O}(1)$
  * Not using any extra space, apart from the one provided

### Code

```java
int i  = m-1 , j = n-1; 

// Start filling the merged array from end
for(int k = n+m-1; k >= 0; k--) {
	// We compare if there are elements left in one of the array 
	// if all elements are finished simply put all the remaining 
	// elements
	if(i >= 0 && j >= 0) {
		nums1[k]= nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
	} else if (i >=0) {
		nums1[k] = nums1[i--];
	} else {
		nums1[k] = nums2[j--];
	}
}
```