Check whether array A is a permutation.
Problem
A non-empty array A consisting of N integers is given.
A permutation is a sequence containing each element from 1 to N once, and only once.
For example, array A such that:
A[0] = 4
A[1] = 1
A[2] = 3
A[3] = 2
is a permutation, but array A such that:
A[0] = 4
A[1] = 1
A[2] = 3
is not a permutation, because value 2 is missing.
The goal is to check whether array A is a permutation.
Write a function:
def solution(A)
that, given an array A, returns 1 if array A is a permutation and 0 if it is not.
Write an efficient algorithm for the following assumptions:
N is an integer within the range [1..100,000];
each element of array A is an integer within the range [1..1,000,000,000].
Example
A permutation is a sequence containing each element from 1 to N once, and only once.
For example, array A such that:
A[0] = 4
A[1] = 1
A[2] = 3
A[3] = 2
is a permutation, but array A such that:
A[0] = 4
A[1] = 1
A[2] = 3
is not a permutation, because value 2 is missing.
The goal is to check whether array A is a permutation.
Hint
We will maintain two variables:
false_positions: this is a list of size len(A) + 1 containing all False values at the time of initialization but are set to True as we would iterate over A
Note: at the initialization step itself, we would set A[0] = True
count_false: maintains a decrementing count of 'False' values remaining in the false_positions variable
We would iterate over the input array A and keep updating the false_positions and count_false variables.
After the we are done iterating over array A, we would see if count_false is zero or not.
If count_false is zero: we would return 'permutation found', otherwise 'permutation not found'.
Code
def solution(A):
false_positions = [False for i in range(len(A) + 1)]
count_false = len(A)
false_positions[0] = True
for i in range(len(A)):
if(A[i] <= len(A)):
if(false_positions[A[i]] == False):
false_positions[A[i]] = True
count_false -= 1
if count_false == 0:
return 1
else:
return 0
Example Test Cases
Detected time complexity:
O(N) or O(N * log(N))
([4, 1, 3, 2])
([4, 1, 3])
([1, 1, 4, 4]) # Suggested by Rohit Sud
Performance Tests
Correctness tests
extreme_min_max
single element with minimal/maximal value
single
single element
double
two elements
antiSum1
total sum is correct, but it is not a permutation, N <= 10
small_permutation
permutation + one element occurs twice, N = ~100
permutations_of_ranges
permutations of sets like [2..100] for which the anwsers should be false
Performance tests
medium_permutation
permutation + few elements occur twice, N = ~10,000
antiSum2
total sum is correct, but it is not a permutation, N = ~100,000
large_not_permutation
permutation + one element occurs three times, N = ~100,000
large_range
sequence 1, 2, ..., N, N = ~100,000
extreme_values
all the same values, N = ~100,000
various_permutations
all sequences are permutations
Solution 2: Rohit’s Algo
Sort the input array A using the language’s built-in sorting method.
We would maintain two variables:
one_is_there: that makes sure we have a one in the array. This helps our code from breaking in case the numbers sequenced from let’s say 3 to 10, or 2 to 8 (for example) but one is missing.
diff_one: that checks that in the sorted array all the consecutive elements in the sorted array A are at a gap of one.
Then we iterate over the input array and maintain these two flags.
At the end, we check value of these flags and return whether input array is a permutation (1) or not a permutation (0).
Rohit’s Solution
def solution(A):
A = sorted(A)
one_is_there = False
diff_one = False
if len(A) == 1 and A[0] == 1:
return 1
for i in range(len(A) - 1):
if A[i] == 1 or A[i+1] == 1:
one_is_there = True
if A[i+1] - A[i] != 1:
diff_one = False
return 0
else:
diff_one = True
if one_is_there and diff_one:
return 1
else:
return 0