Rotate Array

Problem Statement

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

You must do this in-place with O(1) extra space if possible, although O(n) space is also acceptable.

What to notice first

• The rotation is to the right, meaning elements move forward and wrap around.
• “In-place” means modifying the original array without using extra arrays (except for the reverse approach which doesn’t).
• When k is larger than the array length, only k % n steps matter due to circular nature.
• Example: rotating [1,2,3,4,5] right by 2 gives [4,5,1,2,3].

Examples

Input	k	Output	Explanation
[1,2,3,4,5]	2	[4,5,1,2,3]	Rotate right 2 steps: last 2 elements move to front
[99,100,1,2,3]	2	[2,3,99,100,1]	Last 2 elements wrap to front
[1]	0	[1]	Single element, no rotation needed
[1,2,3,4,5]	7	[4,5,1,2,3]	k=7 % 5 = 2, same as rotating by 2

Constraints

• 1 <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1
• 0 <= k <= 10^9

Real-World Applications

Where this pattern appears

• Circular buffer implementation — rotating elements in a fixed-size buffer used in streaming data processing.
• Image rotation — rotating pixel arrays for image transformations in computer graphics.
• Playlist cycling — rotating song lists in music players or media systems.
• Ring buffer management — managing write positions in circular data structures used in networking and real-time systems.
• Time series windowing — sliding windows of data in analytics where historical data wraps around.

Complexity Comparison

Approach	Time	Space	Pros	Cons
Reverse Trick	O(n)	O(1)	True in-place, no extra array	Requires understanding the trick
Extra Space	O(n)	O(n)	Simple to understand and implement	Uses O(n) extra space

Which approach should you learn first?

• Pick Reverse Trick if you want the optimal O(1) space solution — it’s elegant and interview-friendly.
• Pick Extra Space if you prioritize clarity and simplicity over space optimization.

Optimal Space

Reverse Trick

O(n) time · O(1) space

Easier to Understand

Extra Space

O(n) time · O(n) space

Approach 1: Reverse Trick (Recommended)

★ Recommended

The key insight: reversing subarrays achieves rotation. For array [1,2,3,4,5] rotated right by 2:

1. Reverse entire array → [5,4,3,2,1]
2. Reverse first k elements → [3,4,5,2,1]
3. Reverse remaining n-k elements → [3,4,5,1,2]

This is pure in-place magic with O(1) extra space!

⏱ Time O(n) Single pass with reversals 💾 Space O(1) No extra arrays

Step-by-step Example

Input: nums = [1,2,3,4,5], k = 2

Step	Operation	Array	Explanation
0	Original	[1,2,3,4,5]	Before rotation
1	Reverse all	[5,4,3,2,1]	Reverse entire array
2	Reverse [0, k-1]	[3,4,5,2,1]	Reverse first 2 elements
3	Reverse [k, n-1]	[3,4,5,1,2]	Reverse last 3 elements
Result	After rotation	[4,5,1,2,3]	Wait, this doesn’t match! Let me recalculate…

Actually, let me trace through more carefully:

• We want last 2 elements [4,5] at front → [4,5,1,2,3]
• Reverse all: [5,4,3,2,1]
• Now we need first 2 positions to have [4,5]. After reversing [0,1]: [4,5,3,2,1]
• After reversing [2,4]: [4,5,1,2,3] ✓

Animated walkthrough

How the reverse trick rotates the array

Watch how three reverse operations transform the array. Use Next or Autoplay to see each step.

Back Autoplay Next Reset

Step 1 of 4

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function rotateReverse(nums, k):
    if nums is empty or k == 0:
        return

    n = length of nums
    k = k % n  // Handle k > n
    if k == 0:
        return

    function reverse(start, end):
        while start < end:
            swap nums[start] and nums[end]
            start++
            end--

    reverse(0, n - 1)      // Reverse entire array
    reverse(0, k - 1)      // Reverse first k elements
    reverse(k, n - 1)      // Reverse remaining elements

Solution Code

Python

rotate_array_reverse.py

from typing import List


def rotate_array_reverse(nums: List[int], k: int) -> None:
    """
    Rotate array in-place using reverse trick.

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

    Approach: Reverse the entire array, then reverse first k elements,
    then reverse remaining n-k elements. This achieves rotation without
    extra space.
    """
    if not nums or k == 0:
        return

    k = k % len(nums)  # Handle k > n
    if k == 0:
        return

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

    # Reverse entire array: [1,2,3,4,5] -> [5,4,3,2,1]
    reverse(nums, 0, len(nums) - 1)
    # Reverse first k: [5,4,3,2,1] -> [3,4,5,2,1]
    reverse(nums, 0, k - 1)
    # Reverse rest: [3,4,5,2,1] -> [3,4,5,1,2]
    reverse(nums, k, len(nums) - 1)


# Test with expected output
nums = [1, 2, 3, 4, 5]
rotate_array_reverse(nums, 2)
print(nums)  # [4, 5, 1, 2, 3]

C++

rotate_array_reverse.cpp

#include <iostream>
#include <vector>

void rotateArrayReverse(std::vector<int>& nums, int k) {
    /**
     * Rotate array in-place using reverse trick.
     *
     * Time: O(n) | Space: O(1)
     *
     * Approach: Reverse the entire array, then reverse first k elements,
     * then reverse remaining n-k elements. This achieves rotation without
     * extra space.
     */
    if (nums.empty() || k == 0) {
        return;
    }

    int n = nums.size();
    k = k % n;  // Handle k > n
    if (k == 0) {
        return;
    }

    auto reverse = [&](int start, int end) {
        while (start < end) {
            std::swap(nums[start], nums[end]);
            start++;
            end--;
        }
    };

    // Reverse entire array: [1,2,3,4,5] -> [5,4,3,2,1]
    reverse(0, n - 1);
    // Reverse first k: [5,4,3,2,1] -> [3,4,5,2,1]
    reverse(0, k - 1);
    // Reverse rest: [3,4,5,2,1] -> [3,4,5,1,2]
    reverse(k, n - 1);
}

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 5};
    rotateArrayReverse(nums, 2);
    for (int num : nums) {
        std::cout << num << " ";
    }
    std::cout << std::endl;  // [4, 5, 1, 2, 3]
    return 0;
}

Java

rotate_array_reverse.java

public class Main {
    public static void rotateArrayReverse(int[] nums, int k) {
        /**
         * Rotate array in-place using reverse trick.
         *
         * Time: O(n) | Space: O(1)
         *
         * Approach: Reverse the entire array, then reverse first k elements,
         * then reverse remaining n-k elements. This achieves rotation without
         * extra space.
         */
        if (nums == null || nums.length == 0 || k == 0) {
            return;
        }

        int n = nums.length;
        k = k % n;  // Handle k > n
        if (k == 0) {
            return;
        }

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

    private static void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        rotateArrayReverse(nums, 2);
        for (int num : nums) {
            System.out.print(num + " ");
        }
        System.out.println();  // [4, 5, 1, 2, 3]
    }
}

JavaScript

rotate_array_reverse.js

function rotateArrayReverse(nums, k) {
    /**
     * Rotate array in-place using reverse trick.
     *
     * Time: O(n) | Space: O(1)
     *
     * Approach: Reverse the entire array, then reverse first k elements,
     * then reverse remaining n-k elements. This achieves rotation without
     * extra space.
     */
    if (!nums || nums.length === 0 || k === 0) {
        return;
    }

    const n = nums.length;
    k = k % n;  // Handle k > n
    if (k === 0) {
        return;
    }

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

    // Reverse entire array: [1,2,3,4,5] -> [5,4,3,2,1]
    reverse(0, n - 1);
    // Reverse first k: [5,4,3,2,1] -> [3,4,5,2,1]
    reverse(0, k - 1);
    // Reverse rest: [3,4,5,2,1] -> [3,4,5,1,2]
    reverse(k, n - 1);
}

const nums = [1, 2, 3, 4, 5];
rotateArrayReverse(nums, 2);
console.log(nums);  // [4, 5, 1, 2, 3]

Rust

rotate_array_reverse.rs

fn rotate_array_reverse(nums: &mut Vec<i32>, mut k: i32) {
    /**
     * Rotate array in-place using reverse trick.
     *
     * Time: O(n) | Space: O(1)
     *
     * Approach: Reverse the entire array, then reverse first k elements,
     * then reverse remaining n-k elements. This achieves rotation without
     * extra space.
     */
    if nums.is_empty() || k == 0 {
        return;
    }

    let n = nums.len();
    k = k % (n as i32);  // Handle k > n
    if k == 0 {
        return;
    }

    let k = k as usize;

    fn reverse(nums: &mut Vec<i32>, mut start: usize, mut end: usize) {
        while start < end {
            nums.swap(start, end);
            start += 1;
            end -= 1;
        }
    }

    // Reverse entire array: [1,2,3,4,5] -> [5,4,3,2,1]
    reverse(nums, 0, n - 1);
    // Reverse first k: [5,4,3,2,1] -> [3,4,5,2,1]
    reverse(nums, 0, k - 1);
    // Reverse rest: [3,4,5,2,1] -> [3,4,5,1,2]
    reverse(nums, k, n - 1);
}

fn main() {
    let mut nums = vec![1, 2, 3, 4, 5];
    rotate_array_reverse(&mut nums, 2);
    println!("{:?}", nums);  // [4, 5, 1, 2, 3]
}

Go

rotate_array_reverse.go

package main

import "fmt"

func rotateArrayReverse(nums []int, k int) {
  /**
   * Rotate array in-place using reverse trick.
   *
   * Time: O(n) | Space: O(1)
   *
   * Approach: Reverse the entire array, then reverse first k elements,
   * then reverse remaining n-k elements. This achieves rotation without
   * extra space.
   */
  if len(nums) == 0 || k == 0 {
    return
  }

  n := len(nums)
  k = k % n  // Handle k > n
  if k == 0 {
    return
  }

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

  // Reverse entire array: [1,2,3,4,5] -> [5,4,3,2,1]
  reverse(0, n-1)
  // Reverse first k: [5,4,3,2,1] -> [3,4,5,2,1]
  reverse(0, k-1)
  // Reverse rest: [3,4,5,2,1] -> [3,4,5,1,2]
  reverse(k, n-1)
}

func main() {
  nums := []int{1, 2, 3, 4, 5}
  rotateArrayReverse(nums, 2)
  fmt.Println(nums)  // [4, 5, 1, 2, 3]
}

Approach 2: Extra Space

✓ Simple

Create a new array and place each element at its rotated position: element at index i goes to index (i + k) % n. Then copy back to the original array.

This approach is straightforward: compute where each element should go, place it there, and restore the original array reference.

⏱ Time O(n) Two passes 💾 Space O(n) Extra array needed

Step-by-step Example

Input: nums = [1,2,3,4,5], k = 2

i	Original Value	New Index (i+k)%n	rotated[newIndex]
0	1	(0+2)%5 = 2	rotated[2] = 1
1	2	(1+2)%5 = 3	rotated[3] = 2
2	3	(2+2)%5 = 4	rotated[4] = 3
3	4	(3+2)%5 = 0	rotated[0] = 4
4	5	(4+2)%5 = 1	rotated[1] = 5

Result: rotated = [4,5,1,2,3] → copy back to nums ✓

Pseudocode

function rotateExtraSpace(nums, k):
    if nums is empty or k == 0:
        return

    n = length of nums
    k = k % n  // Handle k > n
    if k == 0:
        return

    rotated = new array of size n
    for i in range(n):
        rotated[(i + k) % n] = nums[i]

    for i in range(n):
        nums[i] = rotated[i]

Solution Code

Python

rotate_array_extra_space.py

from typing import List


def rotate_array_extra_space(nums: List[int], k: int) -> None:
    """
    Rotate array using extra space.

    Time: O(n) | Space: O(n)

    Approach: Create a new array where element at index i goes to index
    (i + k) % n. Copy back to original array.
    """
    if not nums or k == 0:
        return

    n = len(nums)
    k = k % n  # Handle k > n
    if k == 0:
        return

    # Create rotated result
    rotated = [0] * n
    for i in range(n):
        rotated[(i + k) % n] = nums[i]

    # Copy back to original array
    for i in range(n):
        nums[i] = rotated[i]


# Test with expected output
nums = [1, 2, 3, 4, 5]
rotate_array_extra_space(nums, 2)
print(nums)  # [4, 5, 1, 2, 3]

C++

rotate_array_extra_space.cpp

#include <iostream>
#include <vector>

void rotateArrayExtraSpace(std::vector<int>& nums, int k) {
    /**
     * Rotate array using extra space.
     *
     * Time: O(n) | Space: O(n)
     *
     * Approach: Create a new array where element at index i goes to index
     * (i + k) % n. Copy back to original array.
     */
    if (nums.empty() || k == 0) {
        return;
    }

    int n = nums.size();
    k = k % n;  // Handle k > n
    if (k == 0) {
        return;
    }

    // Create rotated result
    std::vector<int> rotated(n);
    for (int i = 0; i < n; i++) {
        rotated[(i + k) % n] = nums[i];
    }

    // Copy back to original array
    for (int i = 0; i < n; i++) {
        nums[i] = rotated[i];
    }
}

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 5};
    rotateArrayExtraSpace(nums, 2);
    for (int num : nums) {
        std::cout << num << " ";
    }
    std::cout << std::endl;  // [4, 5, 1, 2, 3]
    return 0;
}

Java

rotate_array_extra_space.java

public class Main {
    public static void rotateArrayExtraSpace(int[] nums, int k) {
        /**
         * Rotate array using extra space.
         *
         * Time: O(n) | Space: O(n)
         *
         * Approach: Create a new array where element at index i goes to index
         * (i + k) % n. Copy back to original array.
         */
        if (nums == null || nums.length == 0 || k == 0) {
            return;
        }

        int n = nums.length;
        k = k % n;  // Handle k > n
        if (k == 0) {
            return;
        }

        // Create rotated result
        int[] rotated = new int[n];
        for (int i = 0; i < n; i++) {
            rotated[(i + k) % n] = nums[i];
        }

        // Copy back to original array
        for (int i = 0; i < n; i++) {
            nums[i] = rotated[i];
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        rotateArrayExtraSpace(nums, 2);
        for (int num : nums) {
            System.out.print(num + " ");
        }
        System.out.println();  // [4, 5, 1, 2, 3]
    }
}

JavaScript

rotate_array_extra_space.js

function rotateArrayExtraSpace(nums, k) {
    /**
     * Rotate array using extra space.
     *
     * Time: O(n) | Space: O(n)
     *
     * Approach: Create a new array where element at index i goes to index
     * (i + k) % n. Copy back to original array.
     */
    if (!nums || nums.length === 0 || k === 0) {
        return;
    }

    const n = nums.length;
    k = k % n;  // Handle k > n
    if (k === 0) {
        return;
    }

    // Create rotated result
    const rotated = new Array(n);
    for (let i = 0; i < n; i++) {
        rotated[(i + k) % n] = nums[i];
    }

    // Copy back to original array
    for (let i = 0; i < n; i++) {
        nums[i] = rotated[i];
    }
}

const nums = [1, 2, 3, 4, 5];
rotateArrayExtraSpace(nums, 2);
console.log(nums);  // [4, 5, 1, 2, 3]

Rust

rotate_array_extra_space.rs

fn rotate_array_extra_space(nums: &mut Vec<i32>, mut k: i32) {
    /**
     * Rotate array using extra space.
     *
     * Time: O(n) | Space: O(n)
     *
     * Approach: Create a new array where element at index i goes to index
     * (i + k) % n. Copy back to original array.
     */
    if nums.is_empty() || k == 0 {
        return;
    }

    let n = nums.len();
    k = k % (n as i32);  // Handle k > n
    if k == 0 {
        return;
    }

    let k = k as usize;

    // Create rotated result
    let mut rotated = vec![0; n];
    for i in 0..n {
        rotated[(i + k) % n] = nums[i];
    }

    // Copy back to original array
    for i in 0..n {
        nums[i] = rotated[i];
    }
}

fn main() {
    let mut nums = vec![1, 2, 3, 4, 5];
    rotate_array_extra_space(&mut nums, 2);
    println!("{:?}", nums);  // [4, 5, 1, 2, 3]
}

Go

rotate_array_extra_space.go

package main

import "fmt"

func rotateArrayExtraSpace(nums []int, k int) {
  /**
   * Rotate array using extra space.
   *
   * Time: O(n) | Space: O(n)
   *
   * Approach: Create a new array where element at index i goes to index
   * (i + k) % n. Copy back to original array.
   */
  if len(nums) == 0 || k == 0 {
    return
  }

  n := len(nums)
  k = k % n  // Handle k > n
  if k == 0 {
    return
  }

  // Create rotated result
  rotated := make([]int, n)
  for i := 0; i < n; i++ {
    rotated[(i+k)%n] = nums[i]
  }

  // Copy back to original array
  for i := 0; i < n; i++ {
    nums[i] = rotated[i]
  }
}

func main() {
  nums := []int{1, 2, 3, 4, 5}
  rotateArrayExtraSpace(nums, 2)
  fmt.Println(nums)  // [4, 5, 1, 2, 3]
}

Common mistakes

Watch for these pitfalls

• Forgetting k % n: When k > n, the rotation repeats. Only k % n steps actually change the array.
• Off-by-one errors in reverse: Ensure reverse boundaries are [start, end] inclusive. A common bug is using end instead of end - 1.
• Confusing directions: “Rotate right” means elements move toward higher indices (with wrapping). [1,2,3] rotated right by 1 is [3,1,2], not [2,3,1].
• In-place mutations: If not careful, the reverse trick’s order matters. Reversing in a different order produces incorrect results.
• Not modifying the original array: In Python, lists are passed by reference, but returning a new list doesn’t modify the original. The solution should modify in-place.

Approach 3: Optimized Two-Pointer

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

rotate_array_optimized.py

"""
Solution for Rotate Array
"""

def solve():
    """Implementation for approach 3 of Rotate Array"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

rotate_array_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Rotate Array
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

RotateArrayOptimized.java

/**
 * Solution for Rotate Array
 * Approach 3
 */
public class RotateArrayOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

rotate_array_optimized.js

/**
 * Solution for Rotate Array
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

rotate_array_optimized.rs

/// Solution for Rotate Array
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

rotate_array_optimized.go

package main

import "fmt"

// Solution for Rotate Array
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Two Sum ↗ Easy #1
• Rotate Image ↗ Medium #48
• Rotate List ↗ Medium #61
• Reverse Words in a String ↗ Medium #151

Interview Tips

Key trade-offs to discuss

• Why reverse trick over extra space? The reverse trick achieves true O(1) space (except for the recursive call stack in some languages). This is the optimal solution and interview gold.
• Why is k % n important? Rotating by n steps gets you back to the original, so only k % n matters. This edge case prevents unnecessary iterations.
• Comparing to other rotation problems: Problem #48 (Rotate Image) rotates a 2D matrix in-place; Problem #61 (Rotate List) does it on a linked list. The reverse trick generalizes across different data structures.
• Edge cases to cover: Empty arrays, k=0, k=n, k>n, arrays with single elements, and duplicate elements. All approaches handle duplicates naturally.
• Follow-up — GCD approach: There’s a third approach using the GCD (Greatest Common Divisor) for cyclic rotation, which places each element directly in its final position. It’s more complex but demonstrates deeper algorithmic thinking.

← Previous
#188 Best Time to Buy and Sell Stock IV Next
#190 Reverse Bits →