Taro Logo

Rotate Array

Medium
Netflix logo
Netflix
6 views
Topics:
Arrays

You are given an integer array nums. Your task is to rotate the array to the right by k steps, where k is a non-negative integer. It is important to perform this rotation in-place, meaning you should modify the original array directly without using extra space proportional to the size of the array.

Example 1:

  • Input: nums = [1,2,3,4,5,6,7], k = 3
  • Output: [5,6,7,1,2,3,4] Explanation: Rotating to the right by 3 steps means each element shifts 3 positions to the right. The elements that reach the end wrap around to the beginning.

Example 2:

  • Input: nums = [-1,-100,3,99], k = 2
  • Output: [3,99,-1,-100] Explanation: Similarly, each element shifts 2 positions to the right, with wrap-around.

Constraints:

  • The length of the array nums is between 1 and 10^5 (inclusive).
  • Each element in nums is between -2^31 and 2^31 - 1 (inclusive).
  • The value of k is between 0 and 10^5 (inclusive).

Describe an algorithm to efficiently rotate the array in-place. Consider both the time and space complexity of your solution. Can you identify any edge cases?

Solution


Naive Solution: Brute Force

The most straightforward approach is to rotate the array one step at a time, repeating this process k times. For each rotation, we shift every element to the right, with the last element moving to the first position.

Algorithm:

  1. For k iterations:
  2. Store the last element of the array in a temporary variable.
  3. Shift all elements one position to the right.
  4. Place the temporary variable at the beginning of the array.

Code (Python):

def rotate_brute_force(nums, k):
    n = len(nums)
    for _ in range(k):
        temp = nums[n - 1]
        for i in range(n - 1, 0, -1):
            nums[i] = nums[i - 1]
        nums[0] = temp

Time Complexity: O(n*k), where n is the length of the array and k is the number of rotations. Each rotation takes O(n) time, and we perform k rotations.

Space Complexity: O(1). We use only a constant amount of extra space for the temporary variable.

Optimal Solution: Reversal Algorithm

A more efficient approach involves reversing sub-arrays of the original array. This method achieves the rotation in O(n) time.

Algorithm:

  1. Reduce k to its effective rotation count by taking k % n, where n is the length of the array.
  2. Reverse the entire array.
  3. Reverse the sub-array from the beginning to k - 1.
  4. Reverse the sub-array from k to the end of the array.

Explanation:

Reversing the entire array puts the elements in reverse order. Then, reversing the first k elements and the remaining n-k elements places the last k elements at the beginning of the array while preserving their order, and places the first n-k elements after the k elements, also preserving their order.

Code (Python):

def rotate_optimal(nums, k):
    n = len(nums)
    k %= n # Effective rotation count

    def reverse(nums, start, end):
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1

    reverse(nums, 0, n - 1)       # Reverse entire array
    reverse(nums, 0, k - 1)       # Reverse first k elements
    reverse(nums, k, n - 1)       # Reverse remaining elements

Time Complexity: O(n), where n is the length of the array. We perform three reversals, each taking O(n) time.

Space Complexity: O(1). The reversal is done in-place, requiring only constant extra space.

Edge Cases

  • Empty Array: If the input array is empty, no rotation is needed.
  • k = 0: If k is 0, no rotation is needed.
  • k = n: If k is equal to the length of the array, no rotation is effectively needed (the array returns to its original state).
  • k > n: The modulo operator (k %= n) handles cases where k is larger than the array length, ensuring that the rotation is within the bounds of the array.

Summary

The optimal reversal algorithm provides an efficient in-place solution for rotating an array by k steps. It achieves O(n) time complexity and O(1) space complexity, making it a preferred choice over the brute-force approach.