{x}
blog image

Rotate Array

Given an integer array nums, 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 <= 105
  • -231 <= nums[i] <= 231 - 1
  • 0 <= k <= 105

 

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?

Solution Explanation for Rotating an Array

The problem asks to rotate an array nums to the right by k steps. This means shifting each element k positions to the right. Elements that go beyond the end of the array wrap around to the beginning.

Several approaches can solve this, but we'll focus on the highly efficient "Reverse Three Times" method.

Approach: Reverse Three Times

This method leverages the power of array reversal to achieve the rotation in linear time and constant space. The steps are as follows:

  1. Reverse the entire array: This puts the elements in reverse order.
  2. Reverse the first k elements: This reverses the last k elements of the originally reversed array, placing them in the correct rotated order at the beginning.
  3. Reverse the remaining n-k elements: This reverses the first n-k elements (which were the last n-k elements in the original array), putting them in the correct order at the end.

Example:

Let's say nums = [1, 2, 3, 4, 5, 6, 7] and k = 3.

  1. Reverse the entire array: nums becomes [7, 6, 5, 4, 3, 2, 1]
  2. Reverse the first k=3 elements: nums becomes [5, 6, 7, 4, 3, 2, 1]
  3. Reverse the remaining n-k=4 elements: nums becomes [5, 6, 7, 1, 2, 3, 4] which is the correctly rotated array.

Code Implementation (Python3)

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        def reverse(i: int, j: int):
            while i < j:
                nums[i], nums[j] = nums[j], nums[i]
                i, j = i + 1, j - 1
 
        n = len(nums)
        k %= n  # Handle cases where k is larger than array length
        reverse(0, n - 1)
        reverse(0, k - 1)
        reverse(k, n - 1)

The reverse function is a helper function that reverses a portion of the array. The main rotate function applies the three reversals. Note the k %= n line—this ensures that k is within the bounds of the array length, handling cases where k might be greater than n.

Time and Space Complexity Analysis

  • Time Complexity: O(n). Each reversal step iterates through the array (or a portion of it) once.
  • Space Complexity: O(1). The algorithm operates in-place; it doesn't use extra space proportional to the input size. The space used by the reverse function's variables is constant.

The provided code examples in other languages (Java, C++, Go, TypeScript, Rust, JavaScript, C#) follow the same algorithm and have the same time and space complexity. The primary difference lies in the syntax and specific array manipulation techniques of each language.