aCzyl_yung - 8 days ago 7x

Python Question

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.

Source (Stackoverflow)

Comments