Rotate Array K Times

January 14, 2024

Problem #

Given an array nums and a non-negative integer k, rotate the array to the right by k steps. Each step involves moving the last element of the array to the front.

Example:

1. Input: nums = [1, 2, 3, 4, 5, 6, 7], k = 3 Output: [5, 6, 7, 1, 2, 3, 4]

Solution Approach #

The solution involves reversing parts of the array. First, reverse the entire array, then reverse the first k elements, and finally reverse the remaining n-k elements.

Algorithm Steps #

1. Normalize k to be within the array’s bounds (k %= len(nums)).
2. Reverse the entire array.
3. Reverse the first k elements.
4. Reverse the last n-k elements.
5. The array is now rotated k times.

Code (Python) #

def rotate(nums, k):
    n = len(nums)
    k %= n

    def reverse(i, j):
        while i < j:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1

    reverse(0, n - 1)
    reverse(0, k - 1)
    reverse(k, n - 1)

# Test the function
nums = [1, 2, 3, 4, 5, 6, 7]
rotate(nums, 3)
print(nums)  # Output: [5, 6, 7, 1, 2, 3, 4]

Time Complexity #

O(n), where n is the number of elements in the array. Each element is involved in a constant number of operations.

Space Complexity #

O(1), as the rotation is done in place with no need for extra space.