JavaMediumTwo Pointers20 min
Merge two sorted arrays
Print the merged sorted values, retaining duplicates, separated by single spaces. Follow the stated ordering and edge-case conventions exactly. Interviewers use this task to probe algorithm selection, invariants, and boundary handling.
Input
n, n sorted integers, m, then m sorted integers.
Output
Print the merged sorted values, retaining duplicates, separated by single spaces.
Constraints
0 <= n,m <= 100000; values in [-1000000000,1000000000], nondecreasing.
Example
Input
3 1 3 5 3 2 4 6
Output
1 2 3 4 5 6
Example 2 input
2 -5 9 3 -6 0 10
Output
-6 -5 0 9 10
This example exercises a further boundary or ordering case.
Public test cases (2)
Input
3 1 3 5 3 2 4 6
Expected output
1 2 3 4 5 6
Input
2 1 1 2 1 2
Expected output
1 1 1 2
Hints (2)
- Identify the state needed to avoid recomputing work for each element.
- Advance the pointer whose current value is smaller until both arrays are exhausted.
Target complexity: time O(n+m) · space O(n+m)