NeetCode #202LC-189MediumTwo PointersNC 250
← Back to All Problems#202 · #189 · Rotate Array(轮转数组)
📌 Problem Statement & Constraints
Given an integer array
nums, rotate it to the right by k steps, in place. Constraints: 1 <= nums.length <= 10^5, 0 <= k <= 10^5.💡 Core Algorithmic Approaches
- Reversal trick: reverse the whole array, then reverse the first
kelements and the remainingn - kelements. - After the full reversal, the last
kelements are at the front but in reversed order; reversing each block restores the internal order. kmust be reduced modulon, since rotating bynis a no-op.- This achieves O(n) time with O(1) space, avoiding the O(n) auxiliary array of the naive slice approach.
💻 Benchmark Python3 Implementation
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
n = len(nums)
k %= n # rotating by n is a no-op
if k == 0:
return
def rev(lo: int, hi: int) -> None:
while lo < hi:
nums[lo], nums[hi] = nums[hi], nums[lo]
lo += 1
hi -= 1
rev(0, n - 1) # reverse everything
rev(0, k - 1) # restore the first block
rev(k, n - 1) # restore the second block⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): three reversals, each linear.
💾 Space Complexity
O(1): in place.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting
k %= n:kcan exceedn, and slicing with a largekwould be wrong (or, in the reversal version, would index out of range). - Using
nums[:] = nums[-k:] + nums[:-k]: correct and concise, but allocates O(n) extra space. - Reversing the blocks in the wrong order: reverse the whole array first, then the two blocks.
- Off-by-one in the block boundaries: the first block is
[0, k-1]and the second is[k, n-1].
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.