Funcia
Lv.1countinghashsorting

Common Elements

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

Given two integer arrays a and b, return every element common to both, sorted in ascending order. A value that repeats appears in the result as many times as the smaller of its counts in a and b. Return an empty array if nothing is common.

Examples

abresult
[1, 2, 2, 1][2, 2][2, 2]
[4, 9, 5][9, 4, 9, 8, 4][4, 9]
[1, 3][2, 4][]

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

  • 1≤1 \le a.length, b.length ≤200,000\le 200{,}000
  • −109≤-10^9 \le a[i], b[j] ≤109\le 10^9

Expected complexity

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

Examples

abExpected
[1,2,2,1][2,2][2,2]
[4,9,5][9,4,9,8,4][4,9]
[1,3][2,4][]

Hint

Hint

Either count the values of a in a hash map and consume them while scanning b (then sort), or sort both arrays and walk them with two pointers, emitting a value whenever the pointers meet equal elements. Searching b for each element of a is O(N⋅M)O(N \cdot 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 251494 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

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

No result yet. Run or submit your code.