Funcia
Lv.1arraytwo-pointers

Merge Two Sorted Arrays

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Two arrays a and b are each sorted in non-decreasing order. Return one array, sorted in non-decreasing order, that contains every element of both (duplicates kept).

Examples

abresult
[1, 4, 7][2, 3, 8, 9][1, 2, 3, 4, 7, 8, 9]
[][5, 5][5, 5]
[-3, 0, 0][0, 10][-3, 0, 0, 0, 10]

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(a: int[], b: int[]) → int[]

Constraints

  • 0≤0 \le a.length, b.length ≤100,000\le 100{,}000, 1≤1 \le a.length + b.length
  • −109≤-10^9 \le a[i], b[i] ≤109\le 10^9
  • a and b are each sorted in non-decreasing order.

Expected complexity

Time
O(N + M)
Space
O(N + M)

Examples

abExpected
[1,4,7][2,3,8,9][1,2,3,4,7,8,9]
[][5,5][5,5]
[-3,0,0][0,10][-3,0,0,0,10]

Hint

Hint

Keep a pointer into each array and repeatedly take the smaller front element; when one runs out, append the rest of the other. Inserting each element of b into a (shifting everything after it) is O(N×M)O(N \times M) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251592 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4010verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.