##### Short Problem Definition:

We define *P* to be a permutation of the first *n* natural numbers in the range *[1,n]*. Let *pos[i]* denote the value at position *i* in permutation *P* using 1-based indexing.

*P* is considered to be an *absolute permutation* if *|pos[i]-i| = K* holds true for every *i*.

##### Link

##### Complexity:

time complexity is O(N)

space complexity is O(N)

##### Execution:

The time complexity of this solution is a question as is always true with hash maps. It is either O(N), O(NlogN) or O(N^2) depending on your particular implementation and hash algorithm.

After I solved this, I looked at the *editorial *and was amazed by the complex algorithm that they proposed. This is much simpler. Yet I agree that the editorial is more time/space effective.

Iterate over the list of all values [1,N]. Use the lowest available value from the [1,N] pool. Either *i-K* or *i+k*, if* i-K* is not available.

##### Solution:

#!/bin/python import math import os import random import re import sys # Complete the absolutePermutation function below. def absolutePermutation(n, k): solution = [] s = set(range(1,n+1)) for pos in xrange(1, n+1): if pos-k in s: solution.append(pos-k) s.remove(pos-k) elif pos+k in s: solution.append(pos+k) s.remove(pos+k) else: return [-1] return solution if __name__ == '__main__': fptr = open(os.environ['OUTPUT_PATH'], 'w') t = int(raw_input()) for t_itr in xrange(t): nk = raw_input().split() n = int(nk[0]) k = int(nk[1]) result = absolutePermutation(n, k) fptr.write(' '.join(map(str, result))) fptr.write('\n') fptr.close()

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.