for i in range(D):
   ele=A.pop(0)
   ans=A.append(ele)
   return ans

the above code is written by me where d is the number of times the array should rotate anti-clockwise and A is the array.

CodePudding user response：

Your code already runs in O(1) as you return after one iteration. If we fix that, we would get something like this:

def rot(x: list[T], offset: int) -> list[T]:
    """Rotates x by offset."""
    ans: list[T] = []
    for _ in range(offset):
        ans.append(x.pop(0))
    return ans

but it returns a prefix of x, not a rotation. It merely copies elements into ans.

If you instead append to x, rather than a new list ans, you will get your rotation.

def rot(x: list[T], offset: int) -> list[T]:
    """Rotates x by offset."""
    for _ in range(offset):
        x.append(x.pop(0))
    return x

It doesn't run in O(n)--far from it.

The x.pop(0) operation itself runs in O(n) because it involves copying all the remaining elements in x one forward, so if we do it offset times, the running time is O(offset * n).

Can we do better? Of course we can. A rotation of x is nothing more than x[:offset] x[:offset] (or similar if you allow a negative offset), so this function rotates x

def rot(x: list[T], offset: int) -> list[T]:
    """Rotates x by offset."""
    return x[offset:]   x[:offset]

and it does it in O(n) because we are only copying each element of x once (or at least a constant number of times). It also has the added benefit of not destroying the original x, but whether that is important depends on the application of the rotation and isn't always important.

Anyway, if you want to leave x alone and not modify it, you usually have to copy all its elements before you can modify a new array, and that puts a lower limit of Ω(n) on how fast it can get.

Even if you don't modify x, though, the usual definition of an array will give you a linear lower bound. If arrays are defined as starting at a given address, then having each element consecutively in memory, you cannot rearrange elements without moving them, and a rotation must move all of them, and thus you cannot do better than Θ(n).

That doesn't mean that we can't get constant time rotation, though. It just means that we can't get it that way. We can change what we mean by an array.

We could, for example, wrap up an underlying (real) array, the consecutive sequence of items, in objects that also remember an offset of how much we have rotated. When we index into it, we adjust for the offset--i -> (i offset)%n--and that will look exactly as if we had rotated the array.

@dataclass
class Array(Generic[T]):
    """Array with constant time rotations."""

    arr: list[T]    # Underlying data
    offset: int = 0  # Current offset

    def rot(self, offset: int) -> Array[T]:
        """Rotates self by offset."""
        return Array(self.arr, self.offset   offset)

    def __getitem__(self, i: int) -> T:
        """Get the value at index i."""
        return self.arr[(i   self.offset) % len(self.arr)]

    def __str__(self) -> str:
        """Printing string."""
        items = ', '.join(str(self[i]) for i, _ in enumerate(self.arr))
        return f"[{items}]"

If we rotate an array, it simulates nicely that we have a rotation, but we only did constant work.

>>> x = Array([1, 2, 3, 4, 5, 6, 7, 8])
>>> print(x.rot(2))
[3, 4, 5, 6, 7, 8, 1, 2]

Here, you can also have multiple references to the same underlying array, with different rotations. If you modify the array, though, all references will see the change--you don't get out of that if you want to rotate faster than O(n).

The x[:offset] x[offset:] rotation uses O(n) memory. Yes, we already use O(n) memory for x, but sometimes it matters that we don't use more than we already do, so another interesting question is if we can rotate in O(1) space--i.e. do the rotation in-place, modifying x without using more than constant extra memory.

The fake Array rotation does this, of course, but could we do it without faking it?

The simple rotation

def rot(x: list[T], offset: int) -> list[T]:
    """Rotate x by offset."""
    for _ in range(offset):
        x.append(x.pop(0))
    return x

does it, but at the cost of O(offset * n) time. Can we do it in O(n)?

Yes, because there is a nice relationship between reversing sequences--which we can easily do in O(n) time and O(1) space--and rotating:

def rev(x: list[T], i: int, j: int) -> None:
    """Reverse x[i:j] in-place."""
    j -= 1  # first element actually in the range
    while i < j:
        x[i], x[j] = x[j], x[i]
        i  = 1
        j -= 1


def rot(x: list[T], offset: int) -> list[T]:
    """Rotate x by offset."""
    rev(x, 0, offset)
    rev(x, offset, 0)
    rev(x, 0, len(x))
    return x

When you first reverse the prefix in-place and then the suffix, you get rev(x[:offset]) rev(x[offset:]) and when you reverse the entire sequence the prefix becomes the suffix and vice versa, and that reversal undo the original one, so you are left with x[offset:] x[:offset] which is the rotation.