Merge Two Sorted Arrays

easy 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

Best approachTime O(n + m)Space O(n + m)

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.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * 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)
  1. Where is the smallest remaining element?