⚡Flashcard Drill➔
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

  1. Reversal trick: reverse the whole array, then reverse the first k elements and the remaining n - k elements.
  2. After the full reversal, the last k elements are at the front but in reversed order; reversing each block restores the internal order.
  3. k must be reduced modulo n, since rotating by n is a no-op.
  4. 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: k can exceed n, and slicing with a large k would 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.
🎯 Drill This Card Now➔

🧩 Related Two Pointers Problems