CODEWITHSUNDEEP
pythonpython-3.x
aCzyl_yung
aCzyl_yung

Reputation: 13

HackerRank Python - some test cases get "Terminated due to timeout", how can i optimize the code?

Currently, on HackerRank, I am trying to solve the Circular Array Rotation problem. Most of the test cases work, but some are "Terminated due to timeout".

How can I change my code to optimise it?

#!/bin/python3

import sys


n,k,q = input().strip().split(' ')
n,k,q = [int(n),int(k),int(q)]
a = [int(a_temp) for a_temp in input().strip().split(' ')]

m = []
for a0 in range(q):
    m.append(int(input().strip()))

for i in range (0, k % n):
    temp = a[n-1]    # Stores the last element temporarily
    a.pop(n-1)       # Removes the last element
    a = [temp] + a   # Appends the temporary element to the start (prepends)


for i in range (0, q):
    print(a[m[i]])

Upvotes: 0

Views: 1463

Answers (1)

Blckknght
Blckknght

Reputation: 104792

There's no need to transform the list at all. Just subtract k from the index you're passed whenever you do a lookup (perhaps with a modulus if k could be larger than n). This is O(1) per lookup, or O(q) overall.

Even if you wanted to transform the actual list, there's no need to do it one element at a time (which will require k operations that each take O(n) time, so O(n*k) total). You can simply concatenate a[-k:] and a[:-k] (again, perhaps with a modulus to fix the k > n case), taking O(n) time just once.

Upvotes: 1

Related Questions