A permutation of the first n natural numbers is an arrangement or sequence where each number from 1 to n appears exactly once. To determine if an array is a permutation, the goal is to verify that it contains all numbers from 1 to n without duplicates. This can be done efficiently in O(n) time complexity. Here’s how:

Understanding Permutations

A permutation of an array [1, 2, 3, ..., n] means that the array is a rearrangement of these numbers. Thus, each number should appear exactly once.

Key Properties of a Permutation:

1. Length Check: The length of the array should be n .
2. Element Range: Every element should be between 1 and n .
3. Uniqueness: Each element should be unique.

Approach: Efficiently Checking Permutation in O(n)

To check if an array is a permutation, follow these steps:

1. Length Verification:
   • Ensure the array has n elements.
2. Counting Occurrences with a Hash Set:
   • Utilize a hash set to record numbers as they appear.
   • Loop through each element in the array:
     • If the element is outside the range [1, n] , it is not a permutation.
     • If the element is already in the set, it means there are duplicates, so it is not a permutation.
     • Otherwise, add the element to the set.
3. Final Check:
   • If the hash set contains exactly n elements, the array is a permutation.

Algorithm Implementation

Here’s the pseudocode for a better understanding:

• Step 1: The length is 4 , which matches the number of distinct natural numbers [1, 2, 3, 4] .
• Step 2: Insert elements into a set: \{4, 3, 2, 1\} .
• Step 3: The set has 4 elements, confirming it's a permutation.
• Empty Array: An array with zero elements is not a permutation.
• Array with Duplicate and Out of Range Elements: For example, an array [1, 2, 3, 3] or [0, 1, 2, 3] fails the permutation test.
• Space Optimization: Instead of using a hash set, a boolean array of size n could also be used to track occurrences, reducing additional space from handling complex data types.
• Real-world Applications: Permutation checks are useful in cryptography, competitive programming, and whenever order-sensitive operations occur in algorithms.