Introduction

To check whether array B is a permutation of array A, you need to verify that both arrays contain exactly the same elements with exactly the same frequencies. The order does not matter, but length and counts do.

The Core Definition

Two arrays are permutations of each other if:

• they have the same length
• every distinct value appears the same number of times in both arrays

That means [3, 1, 4, 2] and [4, 2, 1, 3] are permutations, but [1, 2, 2] and [1, 1, 2] are not because the frequencies differ.

The shortest useful mental model is: permutation checking is a multiset-equality problem.

Method 1: Sort Both Arrays

The simplest general solution is to sort both arrays and compare them element by element.

1
2def is_permutation_sort(a, b):
3    if len(a) != len(b):
4        return False
5    return sorted(a) == sorted(b)
6
7
8print(is_permutation_sort([3, 1, 4, 2], [4, 2, 1, 3]))
9print(is_permutation_sort([1, 2, 2], [1, 1, 2]))

This is easy to write and easy to trust. Its time complexity is O(n log n) because sorting dominates the work.

For many small and medium-sized datasets, that is perfectly acceptable.

Method 2: Count Frequencies With a Hash Map

If you want linear time, count how often each value appears.

1from collections import Counter
2
3
4def is_permutation_count(a, b):
5    if len(a) != len(b):
6        return False
7    return Counter(a) == Counter(b)
8
9
10print(is_permutation_count([3, 1, 4, 2], [4, 2, 1, 3]))
11print(is_permutation_count([1, 2, 2], [1, 1, 2]))

This runs in O(n) expected time with O(n) extra space. It is usually the best answer when the arrays are not already sorted and you care more about speed than minimal memory.

The same idea can be written manually without Counter:

1
2def is_permutation_manual(a, b):
3    if len(a) != len(b):
4        return False
5
6    counts = {}
7    for value in a:
8        counts[value] = counts.get(value, 0) + 1
9
10    for value in b:
11        if value not in counts:
12            return False
13        counts[value] -= 1
14        if counts[value] < 0:
15            return False
16
17    return True

That version makes the underlying logic explicit.

Method 3: Counting Array for Small Integer Ranges

If the arrays contain integers in a small known range, you can replace the hash map with a counting array.

1
2def is_permutation_small_range(a, b, max_value):
3    if len(a) != len(b):
4        return False
5
6    counts = [0] * (max_value + 1)
7    for value in a:
8        counts[value] += 1
9    for value in b:
10        counts[value] -= 1
11        if counts[value] < 0:
12            return False
13
14    return True
15
16
17print(is_permutation_small_range([0, 2, 1, 2], [2, 0, 2, 1], 2))

This is very fast, but it only fits problems where the domain is constrained and non-negative.

How to Choose Among the Methods

A practical guide is:

• use sorting when clarity is more important than absolute performance
• use a frequency map for general linear-time checking
• use a counting array only when the value range is small and known

The correct choice depends on the data model, not just on asymptotic complexity.

If the arrays are already sorted, comparison is even simpler because no extra work is needed beyond a direct scan.

Common Pitfalls

A common mistake is checking only whether both arrays contain the same distinct values. Frequency matters too, so sets alone are not enough.

Another mistake is forgetting the length check. If the lengths differ, the arrays cannot be permutations.

People also often write a frequency decrement loop but forget to reject negative counts immediately. That can hide mismatches until later.

Finally, be clear about element types. If the arrays contain complex objects, permutation checking depends on the equality semantics of those objects, not just on their printed appearance.

Summary

• Two arrays are permutations of each other when they have the same length and the same value frequencies.
• Sorting both arrays is the simplest general solution.
• A frequency map gives expected O(n) time for general data.
• A counting array is a fast special-case optimization for small integer ranges.
• Do not use sets alone when duplicates matter.