Merge Two Sorted Arrays
Problem
Two sorted arrays (ascending) are given. Print one sorted array that contains all elements of both.
Constraints
- 1 <= n, m <= 10^5
Examples
Input
3 1 3 5 3 2 4 6
Output
1 2 3 4 5 6
Solutions
Because both arrays are sorted, the smallest remaining element is always at the front of one of them. This is the merge step of merge sort.
/*
* Problem : Merge sorted arrays.
* Input : Two counts and two arrays.
* Output : The merged array.
* Approach: Two pointers.
* Time : O(n + m)
* Space : O(n + m)
* Java : 8 or newer.
*/
import java.util.Scanner;
import java.util.Arrays;
import java.util.stream.Collectors;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static int[] solve(int[] a, int[] b) {
int[] result = new int[a.length + b.length];
int i = 0;
int j = 0;
int k = 0;
// Step 1: Compare the front elements of both arrays and take the smaller one.
while (i < a.length && j < b.length) {
if (a[i] <= b[j]) {
result[k++] = a[i++];
} else {
result[k++] = b[j++];
}
}
// Step 2: One array is finished. Copy the rest of the other array.
while (i < a.length) {
result[k++] = a[i++];
}
while (j < b.length) {
result[k++] = b[j++];
}
return result;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int size = scanner.nextInt();
int[] a = new int[size];
for (int i = 0; i < size; i++) {
a[i] = scanner.nextInt();
}
int sizeB = scanner.nextInt();
int[] b = new int[sizeB];
for (int i = 0; i < sizeB; i++) {
b[i] = scanner.nextInt();
}
System.out.println(Arrays.stream(solve(a, b)).mapToObj(String::valueOf).collect(Collectors.joining(" ")));
}
}
Hints (1)
- Where is the smallest remaining element?