Discussion on Arrays: Left Rotation Challenge

unitraxx 3 years ago+ 1 comment

Obviously this solves the problem, but is a terrible solution. Pop is an O(N) operation. So your solution becomes O(K*N). This should be done in O(N) total time complexity. You do have the space requirement of O(1) correct. All the standard solutions have a O(N) space complexity.

asfaltboy 2 years ago+ 1 comment

True. However, it becomes an elegant solution if we use collections.dequeue instead of list. Double ended queues have a popleft method, which is an O(1) operation:

def array_left_rotation(a, n, k):
    for _ in range(k):
        a.append(a.popleft())
    return a

More info: https://wiki.python.org/moin/TimeComplexity#collections.deque https://docs.python.org/3/library/collections.html#collections.deque

AffineStructure 2 years ago+ 1 comment

They have rotate built into the deque

def array_left_rotation(a, n, k):
    a = deque(a)
    for i in range(k):
        a.rotate(-1)
    return a

josegabriel_st 1 year ago+ 0 comments

You have O(n) in:

a = deque(a)

In order to avoid this, you should use a deque from the beginning like:

from collections import deque

def array_left_rotation(a, n, k):
    a.rotate(-k)

n, k = map(int, input().strip().split(' '))
a = deque(map(int, input().strip().split(' ')))
array_left_rotation(a, n, k);
print(*a, sep=' ')

And array_left_rotation only takes O(k) instead of O(n).

Note that a is pased by reference, so there is no need to return anything, but this could be an issue for some user cases, for this particular problem, it works.