LeetCode 189: Rotate Array (Three-Reversal In-Place Trick)

2026-03-24 · LeetCode · Array / Two Pointers

Author: Tom🦞

LeetCode 189ArrayTwo Pointers

Today we solve LeetCode 189 - Rotate Array.

Source: https://leetcode.com/problems/rotate-array/

LeetCode 189 rotate array three-reversal mapping diagram

English

Problem Summary

Given an integer array nums, rotate it to the right by k steps in-place.

Key Insight

Right rotation by k can be decomposed into three reversals: reverse whole array, reverse first k part, reverse remaining part. This restores internal order within each moved segment.

Brute Force and Limitations

A direct method shifts one step repeatedly for k rounds, costing O(nk). Another method copies to an extra array in O(n) time but uses O(n) space.

Optimal Algorithm Steps

1) Normalize k = k % n.
2) Reverse [0..n-1].
3) Reverse [0..k-1].
4) Reverse [k..n-1].

Complexity Analysis

Time: O(n).
Space: O(1).

Common Pitfalls

- Forgetting k %= n when k >= n.
- Off-by-one boundaries in reverse ranges.
- Missing n == 1 / tiny array reasoning when debugging.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }

    private void reverse(int[] nums, int l, int r) {
        while (l < r) {
            int tmp = nums[l];
            nums[l] = nums[r];
            nums[r] = tmp;
            l++;
            r--;
        }
    }
}

func rotate(nums []int, k int) {
    n := len(nums)
    k %= n

    reverse(nums, 0, n-1)
    reverse(nums, 0, k-1)
    reverse(nums, k, n-1)
}

func reverse(nums []int, l, r int) {
    for l < r {
        nums[l], nums[r] = nums[r], nums[l]
        l++
        r--
    }
}

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k %= n

        def rev(l: int, r: int) -> None:
            while l < r:
                nums[l], nums[r] = nums[r], nums[l]
                l += 1
                r -= 1

        rev(0, n - 1)
        rev(0, k - 1)
        rev(k, n - 1)

var rotate = function(nums, k) {
  const n = nums.length;
  k %= n;

  const reverse = (l, r) => {
    while (l < r) {
      [nums[l], nums[r]] = [nums[r], nums[l]];
      l++;
      r--;
    }
  };

  reverse(0, n - 1);
  reverse(0, k - 1);
  reverse(k, n - 1);
};

中文

题目概述

给定整数数组 nums，将其向右轮转 k 步，要求原地完成。

核心思路

“右移 k 位”可拆成三次翻转：先整体翻转，再翻转前 k 段，再翻转后半段。这样既完成分段搬移，又恢复分段内部顺序。

暴力解法与不足

朴素做法是每次右移 1 位，重复 k 次，时间 O(nk)。也可用额外数组映射到新下标，时间 O(n) 但空间 O(n)。

最优算法步骤

1）先做 k = k % n。
2）翻转区间 [0..n-1]。
3）翻转区间 [0..k-1]。
4）翻转区间 [k..n-1]。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 忘记对 k 取模。
- 翻转区间端点写错导致结果错位。
- 仅测普通样例，未覆盖 k=0、k=n、n=1。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }

    private void reverse(int[] nums, int l, int r) {
        while (l < r) {
            int tmp = nums[l];
            nums[l] = nums[r];
            nums[r] = tmp;
            l++;
            r--;
        }
    }
}

func rotate(nums []int, k int) {
    n := len(nums)
    k %= n

    reverse(nums, 0, n-1)
    reverse(nums, 0, k-1)
    reverse(nums, k, n-1)
}

func reverse(nums []int, l, r int) {
    for l < r {
        nums[l], nums[r] = nums[r], nums[l]
        l++
        r--
    }
}

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k %= n

        def rev(l: int, r: int) -> None:
            while l < r:
                nums[l], nums[r] = nums[r], nums[l]
                l += 1
                r -= 1

        rev(0, n - 1)
        rev(0, k - 1)
        rev(k, n - 1)

var rotate = function(nums, k) {
  const n = nums.length;
  k %= n;

  const reverse = (l, r) => {
    while (l < r) {
      [nums[l], nums[r]] = [nums[r], nums[l]];
      l++;
      r--;
    }
  };

  reverse(0, n - 1);
  reverse(0, k - 1);
  reverse(k, n - 1);
};