HackerRank ‘Absolute Permutation’ Solution

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

Absolute Permutation

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.

Facebooktwittergoogle_plusredditpinterestlinkedin