Absolute Permutation | Hacker Rank: Any way to make this python code faster without changing it's whole logic?

Question

https://www.hackerrank.com/challenges/absolute-permutation/problem

I know that if you work out the math and logic first, the algorithm can be simplified greatly (shifting indices), but is that the only way to solve this and pass all test cases? Checking if a value is in a list can be slow, but I don't know how to optimize/change that to a better code. Without altering the whole logic of my code, is it possible to tweak it to pass all test cases?

def absolutePermutation(number, k):
    newlist=[]
    for i in range(1,number+1):
        bigger=k+i
        smaller=i-k
        tmp=set(newlist)
        if (bigger>number and smaller<=0) or (bigger>number and smaller in tmp) or (smaller<=0 and bigger in tmp):
            return [-1]

        if smaller<=0 or smaller in tmp:
            newn=bigger
        else:
            newn=smaller

        #print(newn)

        newlist.append(newn)

    return newlist

Answer 1

Yeah, you are recreating tmp every iteration of your loop. This makes your solution O(n^2). You could easily make your solution O(n) by setting tmp before your loop and then updating it along with newlist. The reason your current solution is O(n^2) is that building the tmp set with all the items in newlist would take as long as new list. For example, if newlist=[1,2,3,4,5,6,7,...1000] then constructing the tmp set would take 1000 steps.

def absolutePermutation(number, k):
    newlist=[]
    tmp=set()
    for i in range(1,number+1):
        bigger=k+i
        smaller=i-k
        if (bigger>number and smaller<=0) or (bigger>number and smaller in tmp) or (smaller<=0 and bigger in tmp):
            return [-1]

        if smaller<=0 or smaller in tmp:
            newn=bigger
        else:
            newn=smaller

        #print(newn)

        newlist.append(newn)
        tmp.add(newn)

    return newlist