Are two lists the same multiset

Compare two lists ignoring order and duplicates count to determine if they form the same multiset.

multiset dictionary counting comparison

Write a function `same_multiset(a, b)` that takes two lists of integers (or any hashable comparable items) and returns `True` if they form the same multiset, i.e., every element appears the same number of times in both lists, regardless of order. If the lists have different lengths, return `False`. The lists are not necessarily sorted and may contain duplicates. You may not use `collections.Counter` (if you know it) — implement the counting manually using a dictionary or sets. Assume the input elements are hashable.

Your solution should be efficient: linear time complexity in the total number of elements.

Constraints

0 <= len(a), len(b) <= 10^5. Elements are hashable (e.g., integers, strings).

Example

>>> same_multiset([1, 2, 3], [3, 1, 2])
True
>>> same_multiset([1, 2, 2], [2, 1, 1])
False
>>> same_multiset([], [])
True

10 points ~10 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

First check if lengths differ — if so, return False immediately.

Count the occurrences of each element in the first list using a dictionary.

Iterate through the second list, decreasing the counts. If any element is missing or a count goes negative, return False.

At the end, ensure all counts are zero (or simply rely on length check and no negative counts).

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.