LeetCode 189 - Rotate Array

The problem asks us to rotate a given integer array nums to the right by k steps. In other words, each element of the array should be shifted k positions forward, and the elements that "fall off" the end wrap around to the front of the array.

leetcodemediumarraymathtwo-pointers

LeetCode Problem 189

Difficulty: 🟡 Medium
Topics: Array, Math, Two Pointers

Solution

Problem Understanding

The problem asks us to rotate a given integer array nums to the right by k steps. In other words, each element of the array should be shifted k positions forward, and the elements that "fall off" the end wrap around to the front of the array. For example, if nums = [1,2,3,4,5] and k = 2, the last two elements [4,5] move to the front, resulting in [4,5,1,2,3].

The input nums is a standard list or array of integers, with length between 1 and 105, and each integer fits within the 32-bit signed integer range. The integer k can be as large as 105, which means a naive solution that rotates the array one step at a time would be too slow. The output is the same array nums, modified in-place, meaning no new array should be returned or allocated if an optimal solution is implemented.

Important edge cases include when k is zero (no rotation needed), when k is equal to the length of the array (rotation results in the same array), and when the array contains only one element. These constraints guarantee that the array is non-empty, but the rotation amount k may be larger than the array length, so modulo arithmetic is necessary.

Approaches

The brute-force approach rotates the array one step at a time, k times. In each step, we save the last element, shift all other elements one position to the right, and place the saved element at index 0. This works correctly because it simulates the rotation exactly as described. However, its time complexity is O(n * k) because shifting the array requires O(n) operations and it is repeated k times, which becomes inefficient for large arrays or large k.

The optimal approach uses the array reversal technique. The key insight is that rotating the array k steps to the right is equivalent to reversing the whole array, then reversing the first k elements, and finally reversing the remaining n-k elements. This approach works in-place with O(1) extra space and requires only O(n) operations. The reasoning is that reversing subarrays preserves the relative order of rotated segments.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * k) O(1) Rotates one step at a time, inefficient for large k
Optimal O(n) O(1) Uses array reversal technique, in-place and efficient

Algorithm Walkthrough

  1. Compute the effective rotation using k = k % n, where n is the length of the array. This handles cases where k is greater than n.
  2. Reverse the entire array. This moves the elements that should appear at the end to the beginning, but in reverse order.
  3. Reverse the first k elements. This restores the correct order of the rotated segment.
  4. Reverse the remaining n-k elements. This restores the correct order of the remaining segment.
  5. The array nums is now rotated k steps to the right in-place.

Why it works: Reversing the entire array flips the positions of all elements. By reversing the first k elements and the remaining elements separately, we restore the relative order within the rotated segments. This guarantees the array is rotated correctly while using constant extra space.

Python Solution

from typing import List

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k %= n  # handle cases where k > n

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

        reverse(0, n - 1)      # reverse the whole array
        reverse(0, k - 1)      # reverse the first k elements
        reverse(k, n - 1)      # reverse the rest

This implementation first computes the effective k using modulo. The helper function reverse swaps elements in-place between two indices. We reverse the entire array, then reverse the first k elements to fix the rotated segment, and finally reverse the remaining elements to restore their original order. This mirrors the algorithm described above.

Go Solution

func rotate(nums []int, k int)  {
    n := len(nums)
    k %= n // handle cases where k > n

    reverse := func(start, end int) {
        for start < end {
            nums[start], nums[end] = nums[end], nums[start]
            start++
            end--
        }
    }

    reverse(0, n-1) // reverse the whole array
    reverse(0, k-1) // reverse the first k elements
    reverse(k, n-1) // reverse the rest
}

In Go, we use a similar approach. The reverse function is defined as an anonymous function capturing nums and swaps elements between two indices. The main difference from Python is the syntax and that slices in Go are references, so changes in-place directly modify the original array.

Worked Examples

Example 1: nums = [1,2,3,4,5,6,7], k = 3

Step Operation nums
Initial - [1,2,3,4,5,6,7]
Reverse all reverse(0,6) [7,6,5,4,3,2,1]
Reverse first k reverse(0,2) [5,6,7,4,3,2,1]
Reverse rest reverse(3,6) [5,6,7,1,2,3,4]

Example 2: nums = [-1,-100,3,99], k = 2

Step Operation nums
Initial - [-1,-100,3,99]
Reverse all reverse(0,3) [99,3,-100,-1]
Reverse first k reverse(0,1) [3,99,-100,-1]
Reverse rest reverse(2,3) [3,99,-1,-100]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element is reversed at most twice, total O(n)
Space O(1) Only a few pointers are used, in-place

The algorithm only traverses the array a constant number of times, so it scales linearly with the input size. No extra array is allocated, so the space complexity is constant.

Test Cases

# provided examples
sol = Solution()
nums1 = [1,2,3,4,5,6,7]
sol.rotate(nums1, 3)
assert nums1 == [5,6,7,1,2,3,4]  # Example 1

nums2 = [-1,-100,3,99]
sol.rotate(nums2, 2)
assert nums2 == [3,99,-1,-100]   # Example 2

# boundary cases
nums3 = [1]
sol.rotate(nums3, 0)
assert nums3 == [1]               # single element, no rotation

nums4 = [1,2]
sol.rotate(nums4, 2)
assert nums4 == [1,2]             # rotation equal to length

nums5 = [1,2,3]
sol.rotate(nums5, 4)
assert nums5 == [3,1,2]           # rotation greater than length
Test Why
nums1, k=3 standard rotation example
nums2, k=2 negative and positive integers
nums3, k=0 single element, no rotation
nums4, k=2 rotation equal to array length
nums5, k=4 rotation larger than array length

Edge Cases

One important edge case is when k is zero. In this case, the array should remain unchanged. The modulo operation ensures that we handle this naturally without extra checks. Another edge case is when k is equal to the length of the array; modulo arithmetic converts this into a zero rotation. A third edge case is a single-element array, which does not change regardless of k. The algorithm handles all of these correctly because the reversal operations are effectively no-ops for these scenarios. Additionally, when k is greater than n, taking k % n ensures the rotation is meaningful and avoids unnecessary operations.