1
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ Does it pass all the test cases? \$\endgroup\$
    – vnp
    Dec 1 '21 at 5:11
1
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ Nice! Such a simple change actually passed all the tests. So I don't need the most efficient but hard to get to algorithm to solve this. Thanks for noticing the inefficiency! \$\endgroup\$ Dec 2 '21 at 0:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.