PythonMediumTwo Pointers20 min

Merge two sorted arrays

Keep every occurrence of duplicate values. Either input array may be empty. Interviewers use this problem to assess advance a pointer only in the array supplying the next output.

Input

First line: n and m. Second line: n sorted integers. Third line: m sorted integers.

Output

Print the result values separated by single spaces; print an empty line for an empty result.

Constraints

0 <= n, m <= 100000; -10^9 <= values <= 10^9.

Example

Input

3 3
1 3 5
2 4 6

Output

1 2 3 4 5 6

Example 2 input

2 2
1 1
1 1

Output

1 1 1 1

Duplicate values from both arrays must all be retained.

Public test cases (2)

Input
```
3 3
1 3 5
2 4 6
```
Expected output
```
1 2 3 4 5 6
```
Input
```
3 2
-3 0 0
0 9
```
Expected output
```
-3 0 0 0 9
```

Hints (2)

Identify the state needed to avoid repeated work.
Advance a pointer only in the array supplying the next output.

Target complexity: time O(n + m) · space O(n + m) for the result

Your solution

import sys


def solve_merge_sorted_arrays(a, b):
    # your code
    return []


if __name__ == "__main__":
    data = sys.stdin.read()
    tokens = list(map(int, data.split()))
    n, m = tokens[:2]
    a = tokens[2:2 + n]
    b = tokens[2 + n:2 + n + m]
    result = solve_merge_sorted_arrays(a, b)
    print(" ".join(map(str, result)))

Standard input

Checking runner availability…

Reference solution

Check whether a number is prime · Easy
Check whether a string is a palindrome · Easy
Check whether two strings are anagrams · Easy
Compute the factorial of a number · Easy
Count vowels and consonants · Easy
Find the first occurrence with binary search · Easy
Find the missing number from zero through n · Easy
Find the second largest distinct value · Easy
Generate the Fibonacci series · Easy
Remove duplicate values while preserving order · Easy

All Python programs

Merge two sorted arrays

Input

Output

Constraints

Example

Public test cases (2)

Your solution

Reference solution

More Python programs