Teaching Kids Programming – Algorithms to Rotate an Array

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:
Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Constraints:
1 <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 – 1
0 <= k <= 10^5

Follow up:
Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
Could you do it in-place with O(1) extra space?

Hints:
The easiest solution would use additional memory and that is perfectly fine.

The actual trick comes when trying to solve this problem without using any additional memory. This means you need to use the original array somehow to move the elements around. Now, we can place each element in its original location and shift all the elements around it to adjust as that would be too costly and most likely will time out on larger input arrays.

One line of thought is based on reversing the array (or parts of it) to obtain the desired result. Think about how reversal might potentially help us out by using an example.

The other line of thought is a tad bit complicated but essentially it builds on the idea of placing each element in its original position while keeping track of the element originally in that position. Basically, at every step, we place an element in its rightful position and keep track of the element already there or the one being overwritten in an additional variable. We can’t do this in one linear pass and the idea here is based on cyclic-dependencies between elements.

Using a List to Simulate the Array Rotation

The most basic method is to simulate as we are told. Each rotation removes one element from the end of the array and insert it to the front. The following time complexity is O(KN) because there are K rotation (where K is modulus by N) and each insert-to-front takes O(N) time.

1
2
3
4
5
6
7
8

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k %= n        
        for _ in range(k):
            x = nums.pop()
            nums.insert(0, x)
        return nums

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k %= n        
        for _ in range(k):
            x = nums.pop()
            nums.insert(0, x)
        return nums

Using a Double Ended Queue to Rotate More Efficiently

If it is a double-ended queue, then inserting to the front is O(1) constant. However, we may need to copy to/from the additional deque which takes O(N) time (as we need to convert array to deque and convert it back). The overall time complexity is O(N + K + N) which is still O(N) as K is less or equal to N after we do “k %= n”

1
2
3
4
5
6
7
8
9
10

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        a = deque(nums[:])
        n = len(nums)
        k %= n
        for _ in range(k):
            x = a.pop()
            a.appendleft(x)
        nums[:] = list(a)
        return nums

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        a = deque(nums[:])
        n = len(nums)
        k %= n
        for _ in range(k):
            x = a.pop()
            a.appendleft(x)
        nums[:] = list(a)
        return nums

Reverse Sub Arrays to Rotate

We can reverse the array once, then reverse the first K elements, and then reverse the last N-K elements. The time complexity is O(N).

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        def rev(nums, i, j):
            while i < j:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
                j -= 1        
        n = len(nums)
        k %= n
        rev(nums, 0, n - 1)
        rev(nums, 0, k - 1)
        rev(nums, k, n - 1)
        return nums

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        def rev(nums, i, j):
            while i < j:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
                j -= 1        
        n = len(nums)
        k %= n
        rev(nums, 0, n - 1)
        rev(nums, 0, k - 1)
        rev(nums, k, n - 1)
        return nums

Alternatively, we can use the Python list comprehension to do this one line.

1
2
3
4
5

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

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

–EOF (The Ultimate Computing & Technology Blog) —