Arrays: Rotating an Array

Rotating an array to the right means shifting every element to the right, where the last \(k\) elements go to the front. So the element at index \(0\) becomes the old element at index \(-k\), the element at index \(1\) becomes the old element at index \(1-k\), and so on.

• Method 1, Slicing

  PythonCopy

  class Solution:
      def rotate(self, nums: List[int], k: int) -> None:
          nums[:] = [nums[(i - k % len(nums))] for i in range(len(nums))]

• Method 2, Using Deques

  PythonCopy

  from collections import deque
  class Solution:
      def rotate(self, nums: List[int], k: int) -> None:
          deq_nums = deque(nums)
          deq_nums.rotate(k)
          nums[:] = deq_nums[:]

Time complexity: \(O(n)\) for both methods.

Space complexity: \(O(n)\). There is a way to get \(O(1)\) but did not learn it.

Programming lessons learned:

• To update a list in-place using a temporary one, nums[:] = temp[:] is cleaner and faster than looping through indices.

• A deque is a double-ended queue that supports efficient \(O(1)\) operations at both ends. It behaves like both a stack and a queue due to its available functions:

  • As a stack:

    • append()

    • pop()

  • As a queue:

    • appendleft()

    • popleft()

  It is the data structure used as a queue in Python, and to use it write:

  from collections import deque.