Example 1 · empty
- Arguments
- a
[]
b[]
- Expected return
[]
Test data
- Input
{"a":[],"b":[]}- Expected output
[]
Merge sorted sequences
Merge sorted sequences
EasyYour task
- Merge two inputs sorted in nondecreasing order into one nondecreasing list.
- Include every value and preserve all duplicate counts.
Required API
- MergeSorted
func MergeSorted(a, b []int) []int
Behavior
- Leave both inputs unchanged.
- Either input may be empty; if both are empty, return [].
Constraints
- The input is already valid: the combined length is 0–200, and each integer is between -10,000 and 10,000 inclusive.
- Use a forward cursor for each input and aim for O(len(a) + len(b)) time.
- Do not concatenate and sort, use a sorting helper or add dependencies.
- Do not count output storage in auxiliary-space analysis.
- Separate calls are independent.
Notes and example notation
Examples use {"a": [...], "b": [...]}.
Examples
The runner calls your functions directly; you do not need to parse JSON.
Example 2 · interleave
- Arguments
- a
[ 1, 4, 8 ]
b[ 2, 3, 9 ]
- Expected return
[ 1, 2, 3, 4, 8, 9 ]
Test data
- Input
{"a":[1,4,8],"b":[2,3,9]}- Expected output
[1,2,3,4,8,9]
Example 3 · duplicates
- Arguments
- a
[ 1, 1, 3 ]
b[ 1, 2, 3 ]
- Expected return
[ 1, 1, 1, 2, 3, 3 ]
Test data
- Input
{"a":[1,1,3],"b":[1,2,3]}- Expected output
[1,1,1,2,3,3]
Example 4 · one empty
- Arguments
- a
[]
b[ -3, 0, 2 ]
- Expected return
[ -3, 0, 2 ]
Test data
- Input
{"a":[],"b":[-3,0,2]}- Expected output
[-3,0,2]
Solution guide
Reveal solution guide — spoilers
Approach
- Allocate a fresh output sequence and maintain one forward cursor into each sorted input.
- While both cursors have values, append the smaller current value and advance only its cursor. When equal, either side may be chosen first, but advance just that side so both occurrences are eventually included.
- After one input is exhausted, append every remaining value from the other input in order. Do not concatenate and sort or change either input.
Why it works
Each cursor points to the smallest unconsumed value in its input. The smaller of those two values is therefore the smallest remaining value overall. Appending it preserves sorted output, and consuming each input position once preserves every duplicate count.
Complexity
O(a + b) time for input lengths a and b, with O(1) auxiliary space excluding the O(a + b) returned output. Both cursors move forward at most their input length.
Edge cases to check
- Either input may be empty; both empty produce an empty result.
- Equal values within and across inputs must all remain in the result.
- Copy the unconsumed tail into the new result rather than modifying either input.
Restoring local drafts…
Checking execution availability…
Public examples
NO CODE EXECUTEDExplore the examples.
View inputs and expected outputs. Examples do not run your code.