# Hackerrank: Absolute Permutation - How do I make this code more efficient

The problem is basically this: Return the permutation of the set of the first n natural numbers which satisfies the following property:

|pos(i) - i| = k
∀ i ∈ (1,n)
where pos(i) is the ith number in the permutation

If no such permutation exists, return -1.

Note: the input is the integer n.

The full problem is on HackerRank.

The code for the main algorithm:

try:
for y in g.keys():
g[y] = [y-k,y+k]
if y - k <=0:
g[y].remove(y-k)
if y + k > n:
g[y].remove(y+k)

d = []
for y in range(1,n+1):
if len(g[y]) == 1:
if g[y][0] not in d:
d.append(g[y][0])
if len(g[y]) == 2:
if g[y][0] not in d:
d.append(g[y][0])

if len(set(d)) == len(d) and len(d) == n:
return d
else:
return [-1]
except:
return [-1]


g is a previously defined dictionary containing the first n natural numbers as keys with each key initially being assigned a value of 0

the first block changes the value of the key y to the possible numbers that could be at position y in the permutation, namely, y - k or y + k

d is the list that will contain the final permutation. If the value for i in g has only one number, then that number is added to d. If it contains 2 numbers, the first number is added by default. If the first number is already in d, the second number is added. d is printed if, finally, d contains n elements and there are no repeating elements.

On hackerrank, 9 of the 13 test cases are successful, but the last 4 return a timeout error. I've run through the code step by step and it's clear that the second block is taking way too long for larger numbers. I know using list comprehension would make it faster, but I have no idea how to convert that into list comprehension.

How do I make this code more efficient?

• There are 2 "if" that are doing same thing. Why don't you use only 1 "if"? if len<=2 then add once. Mar 11, 2021 at 18:33
• If I don't include the if len == 1 statement then I get an index error when checking if g[y][1] is in d. Mar 11, 2021 at 18:46
• Where are you checking if g[y][1] is in d? Mar 11, 2021 at 19:03
• Why do you say "the input is the integer n" when in reality it's n and k? And better show the whole absolutePermutation(n, k) function. Mar 11, 2021 at 21:03
• "On hackerrank, 9 of the 13 test cases are successful" - I tried it and got "Wrong Answer" for 6 of the test cases. Mar 11, 2021 at 23:29

You test not in d, where d is a list. That's slow. Use an additional set for those membership tests.

Simpler way: Note that the number 1 must go to position 1+k. It has nowhere else to go. Also, the only number that can go to position 1 is the number 1+k. So numbers 1 and 1+k must switch places. Similarly, the numbers 2 and 2+k must switch places (unless k<2). And so on. The entire first k numbers must switch with the next k numbers.

After that, the reasoning repeats, numbers (2k+1) and (2k+1)+k must switch. The entire third chunk of k numbers must switch with the fourth chunk of k numbers. And so on.

In other words, numbers in the first, third, fifth, etc chunk of k numbers must move k positions to the right and numbers in the other chunks of k numbers must move k positions to the left. In yet other words, add k to the odd-numbered chunks and subtract k from the even-numbered chunks.

A solution that tries to build it and discards it if it's invalid:

def absolutePermutation(n, k):
p = [i+1 + (-k if k and i//k%2 else k) for i in range(n)]
return p if max(p) == n else [-1]


Shorter but slower (still accepted):

def absolutePermutation(n, k):
p = [i+1 + k*(-1)**(k and i//k) for i in range(n)]
return p if max(p) == n else [-1]


Alternatively, check whether it'll work and build it only if it will. It will iff there's an even number of complete k-chunks, i.e., if n is divisible by 2k:

def absolutePermutation(n, k):
if k == 0:
return range(1, n+1)
if n % (2*k):
return [-1]
return [i+1 + k*(-1)**(k and i//k) for i in range(n)]



Yet another, starting with the identity permutation and then swapping slices:

def absolutePermutation(n, k):
K = 2 * k
if k and n % K:
return [-1]
p = list(range(1, n+1))
for i in range(k):
p[i::K], p[i+k::K] = p[i+k::K], p[i::K]
return p


A longer but quite nice version using the grouper recipe to give us the chunks:

def absolutePermutation(n, k):
numbers = range(1, n+1)
if k == 0:
yield from numbers
elif n % (2*k):
yield -1
else:
chunks = grouper(numbers, k)
for chunk in chunks:
yield from next(chunks)
yield from chunk


Many programming puzzles of this sort can be solved without brute-force computations if you can figure out the pattern. Rather than trying to implement a solution to the puzzle, it's often helpful to write some temporary code just to explore. The small script below does that. For each list size from 1 through max_n, we find the permutations having valid solutions, along with the corresponding k values.

Some patterns jump about pretty quickly. Odd-sized lists appear to support only k=0. Even-sized lists are interesting: take a close look, for example, at sizes 6 and 8.

import sys
from itertools import permutations

def main():
max_n = int(sys.argv[1])
fmt = '{:<6} {:<4} {}'
div = '-' * 40
print(fmt.format('SIZE', 'K', 'PERM'))
for size in range(1, max_n + 1):
print(div)
for tup in permutations(range(1, size + 1)):
diffs = [abs(j + 1 - x) for j, x in enumerate(tup)]
ds = sorted(set(diffs))
if len(ds) == 1:
k = ds[0]
print(fmt.format(size, k, tup))

main()


Output for max_n=9:

SIZE   K    PERM
----------------------------------------
1      0    (1,)
----------------------------------------
2      0    (1, 2)
2      1    (2, 1)
----------------------------------------
3      0    (1, 2, 3)
----------------------------------------
4      0    (1, 2, 3, 4)
4      1    (2, 1, 4, 3)
4      2    (3, 4, 1, 2)
----------------------------------------
5      0    (1, 2, 3, 4, 5)
----------------------------------------
6      0    (1, 2, 3, 4, 5, 6)
6      1    (2, 1, 4, 3, 6, 5)
6      3    (4, 5, 6, 1, 2, 3)
----------------------------------------
7      0    (1, 2, 3, 4, 5, 6, 7)
----------------------------------------
8      0    (1, 2, 3, 4, 5, 6, 7, 8)
8      1    (2, 1, 4, 3, 6, 5, 8, 7)
8      2    (3, 4, 1, 2, 7, 8, 5, 6)
8      4    (5, 6, 7, 8, 1, 2, 3, 4)
----------------------------------------
9      0    (1, 2, 3, 4, 5, 6, 7, 8, 9)