BL
U

36. Check If Two Arrays Contain Identical Multiset

Easy

Problem Description

Given two arrays AA and BB of size NN and MM, determine whether they contain the exact same multiset of elements (the same numbers with identical frequencies).

Input Format

  • •Line 1: Two space-separated integers NN and MM (1≤N,M≤1051 \le N, M \le 10^5).
  • •Line 2: NN space-separated integers A1,…,ANA_1, \dots, A_N.
  • •Line 3: MM space-separated integers B1,…,BMB_1, \dots, B_M.

Output Format

Print true if both arrays contain the same multiset, else false.

Example 1:
Input:
4 4
1 2 3 2
2 1 2 3
Output:
true
Explanation: Both contain one 1, two 2s, and one 3.
Example 2:
Input:
3 3
1 2 3
1 2 4
Output:
false
Explanation: Elements differ (3 vs 4).
Example 3:
Input:
3 2
1 2 3
1 2
Output:
false
Explanation: Different sizes cannot have identical multisets.
Constraints:
  • Standard integer bounds: 32-bit signed integer or input range [1, 10^5].
  • Time complexity target: O(N) or O(N log N) where applicable.
  • Auxiliary space target: O(1) or minimal auxiliary memory.
Follow up:Can this algorithm be adapted to an online streaming setting where the entire input cannot be held in memory simultaneously?
1,180 Online