How to Solve Rotate Array on LeetCode
The Rotate Array problem is a popular LeetCode interview question testing your array manipulation and in-place algorithm skills.
Problem Statement
Given an array, rotate the array to the right by k steps, where k is non-negative.
Example:
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Why This Problem Matters for Interviews
This problem:
- Assesses in-place and O(1) space solutions
- Shows off your pointer and indexing abilities
- Appears in many follow-up or combination problems
Approaches to Rotate Array
1. In-Place Array Reversal (Optimal)
Reverse the whole array, then reverse the two parts.
Time Complexity: O(n)
Space Complexity: O(1)
def rotate(nums: list[int], k: int) -> None:
n = len(nums)
k %= n
def reverse(left, right):
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
reverse(0, n-1)
reverse(0, k-1)
reverse(k, n-1)
2. Cyclic Replacements
Rotate elements in cycles.
Time Complexity: O(n)
Space Complexity: O(1)
def rotate(nums: list[int], k: int) -> None:
n = len(nums)
k %= n
count = 0
start = 0
while count < n:
current = start
prev = nums[start]
while True:
next_idx = (current + k) % n
nums[next_idx], prev = prev, nums[next_idx]
current = next_idx
count += 1
if start == current:
break
start += 1
Key Interview Talking Points
- Difference between O(n) extra space and in-place approaches
- Why modulus with n is necessary
- Pitfalls with cycles (non-coprime k and n)
- Edge cases: k=0, k>=n
Big O Complexity Recap
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| In-Place Reversal | O(n) | O(1) |
| Cyclic Replacement | O(n) | O(1) |
Pro Interview Tips
- Walk through each reversal step with an example.
- Discuss why in-place matters for large inputs.
- Practice with test cases