aCzyl_yung aCzyl_yung - 1 month ago 17
Python Question

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]])

Answer

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.