absolute_permutation.py

# source: https://www.hackerrank.com/challenges/absolute-permutation/problem
# video: https://youtu.be/Z0bpJiVz0no

def absolutePermutation(n, k):
    if k == 0:  # no need to swap anything
        return list(range(1, n + 1))
    cache = set(range(1, n + 1)) # O(n)
    output = []
    for i in range(1, n + 1): # O(n)
        lower = i - k
        upper = i + k
        if lower in cache:
            cache.remove(lower)
            output.append(lower)
        elif upper in cache:
            cache.remove(upper)
            output.append(upper)
        else:
            return [-1]

    return output # total time complexity = O(n)