Problem

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note: You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

Similar Problem

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.

This is similar to Merge Two Sorted Linked Lists.

Examples

Example 1:

1
2
3

nums1 = {2, 4, 5, _, _, _}, m = 3
nums2 = {1, 3, 6}, n = 3
sortedArray = {1, 2, 3, 4, 5, 6}

Example 2:

1
2
3
4
5
6

Input:
nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output:
 [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Solution

The key to solve this problem is moving element of A and B backwards. If B has some elements left after A is done, also need to handle that case.

Method 1 - Merge Sort

The idea is to start from end, by moving elements from A and B. If B has some elements left after A is done, also need to handle that case.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

public void merge(int nums1[], int m, int nums2[], int n) {
	int k = m + n - 1;
	m--;
	n--;
	while (m >= 0 && n >= 0) {
		if (num1[m] < nums2[n]) {
			num1[k] = nums2[n];
			n--;
		} else {
			num1[k] = num1[m];
			m--;
		}
		k--;
	}
	while (n >= 0) {
		num1[k] = nums2[n];
		n--;
		k--;
	}
}

Complexity

  • ⏰ Time complexity: O (m+n), where size of A as m and size of B as n. So , a linear time algorithm.
  • 🧺 Space complexity: O(1)

Problem 2 - What if We don’t Have Extra Space in Second Array

Problem

Given two integer arrays A and B sorted in increasing order, merge A and B into a single sorted array C in increasing order.

Examples

1
2
3
4
5
6
7
8

Input : 
A = {1, 3, 5, 6}, B = {2, 4, 7}

Output:
{1, 2, 3, 4, 5, 6, 7}

Explanation : 
Merging A and B into a single sorted array produces the above output.

Solution

Then this becomes easier problem. We can just iterate on the array from start as well:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public int[] merge(int[] nums1, int[] nums2) {
	int m = A.length;
	int n = B.length;

	int[] ans = new int[m+n] ;
	int i=0 , j = 0, k = 0;
	while(i < m && j < n){
		if(num1[i] < nums2[j]){
			ans[k] = num1[i];
			i++; k++;
		}else{
			ans[k] = nums2[j];
			j++; k++;
		}
	}
	while(i < m) {
		ans[k++] = num1[i++];
	}
	
	while (j < n) {
		ans[k++] = nums2[j++];
	}

	return ans;
}