Skip to main content
Talentd

Rotate Array - Solution & Explanation

MediumArrayMathTwo Pointers20 min readAsked at: Amazon, Microsoft, Apple +24
Practice this problem

Problem Statement

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

 

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation: 
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

 

Constraints:

  • 1 <= nums.length <= 105
  • -231 <= nums[i] <= 231 - 1
  • 0 <= k <= 105

 

Follow up:

  • Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
  • Could you do it in-place with O(1) extra space?

Approach Overview

Problem Overview: You’re given an integer array nums and an integer k. The task is to rotate the array to the right by k steps, meaning each element shifts right and wraps around to the beginning. For example, rotating [1,2,3,4,5,6,7] by 3 results in [5,6,7,1,2,3,4].

This problem tests your understanding of array manipulation and how to perform cyclic shifts efficiently. A key detail: when k is larger than the array length, only k % n rotations matter.

Approach 1: Using Additional Array (O(n) time, O(n) space)

Create a new array of the same size and place each element directly in its rotated position. First compute k = k % n so unnecessary rotations are avoided. Then iterate through the array and place each element at index (i + k) % n in the new array. After the pass finishes, copy the result back to the original array.

This approach works because the modulo operation naturally handles the wrap‑around from the end of the array back to the front. It’s easy to implement and very readable. The tradeoff is extra memory usage since an additional array of size n is required.

Approach 2: In-Place Reversal (O(n) time, O(1) space)

The optimal solution avoids extra memory by reversing sections of the array in place. The key insight: a right rotation can be expressed as three reversals. First reverse the entire array. Then reverse the first k elements. Finally reverse the remaining n - k elements.

Example: [1,2,3,4,5,6,7] with k = 3. Reverse all → [7,6,5,4,3,2,1]. Reverse first 3 → [5,6,7,4,3,2,1]. Reverse the rest → [5,6,7,1,2,3,4]. Each reversal uses two pointers moving from both ends toward the center, a common pattern in two pointers problems.

This method performs a constant number of passes over the array, giving O(n) time complexity and O(1) extra space. The math behind the rotation and modulo operation ties directly to concepts in math and cyclic indexing.

Recommended for interviews: Interviewers typically expect the in-place reversal approach. The additional array solution shows you understand the rotation mapping, but the reversal method demonstrates deeper algorithmic thinking and space optimization. Both run in linear time, but achieving O(1) space is the key differentiator.

Approach 1: Using Additional Array

This approach involves using an additional array to store the rotated order of elements. We calculate the new position for each element and place it in the new array. Finally, copy the elements of this new temporary array back into the original array.

This C solution creates a temporary array of the same size as the input. It calculates the new index for each element using modulo arithmetic to ensure cyclic behavior, then it fills this temporary array and finally copies it back into the original array.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) where n is the number of elements in the array. Space Complexity: O(n) due to the use of an additional array for rotation.

Try this approach in the editor →

Approach 2: In-Place Reversal

This approach involves reversing parts of the array to achieve the rotation without additional space. First, reverse the whole array, then reverse the first k elements, and finally reverse the remaining n-k elements. This series of reversals effectively performs the rotation in-place without needing extra storage.

This C solution performs in-place array reordering by reversing the entire array, the first k elements, and the last n-k elements. This avoids the need for auxiliary space while achieving the desired rotation result.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n). Space Complexity: O(1) as it does not require additional arrays.

Try this approach in the editor →

Approach 3: Reverse three times

We can assume the length of the array is n and calculate the actual number of steps needed by taking the module of k and n, which is k bmod n.

Next, let us reverse three times to get the final result:

  1. Reverse the entire array.
  2. Reverse the first k elements.
  3. Reverse the last n - k elements.

For example, for the array [1, 2, 3, 4, 5, 6, 7], k = 3, n = 7, k bmod n = 3.

  1. In the first reverse, reverse the entire array. We get [7, 6, 5, 4, 3, 2, 1].
  2. In the second reverse, reverse the first k elements. We get [5, 6, 7, 4, 3, 2, 1].
  3. In the third reverse, reverse the last n - k elements. We get [5, 6, 7, 1, 2, 3, 4], which is the final result.

The time complexity is O(n), where n is the length of the array. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using Additional Array

Time Complexity: O(n) where n is the number of elements in the array. Space Complexity: O(n) due to the use of an additional array for rotation.

In-Place Reversal

Time Complexity: O(n). Space Complexity: O(1) as it does not require additional arrays.

Reverse three times—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Using Additional ArrayO(n)O(n)Simple implementation and readability matter more than memory usage
In-Place ReversalO(n)O(1)Preferred in interviews or memory-constrained environments

Video Solution

Rotate Array - Leetcode 189 - Python • NeetCode • 261,014 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Rotate Array easy or hard?
Rotate Array is usually classified as a medium difficulty problem. The basic idea is simple, but recognizing the in-place reversal trick and implementing it correctly is what makes the problem more challenging.
How to solve Rotate Array in O(n)?
Use the reversal technique. First compute k % n, reverse the entire array, then reverse the first k elements, and finally reverse the remaining n - k elements. This transforms the array into the rotated order in linear time.
Rotate Array Python or Java solution?
Python and Java solutions typically implement either the extra array approach or the in-place reversal approach. The reversal version is preferred because it runs in O(n) time with O(1) additional space.
What is the best approach for Rotate Array?
The in-place reversal method is considered the best approach. It rotates the array in O(n) time using only O(1) extra space by reversing the entire array, then reversing the first k elements and the remaining elements.
Is Rotate Array asked at Google/Amazon/Meta?
Rotate Array is a common interview problem that appears in coding interviews at companies like Amazon, Google, and Meta. It tests array manipulation, modular arithmetic, and in-place algorithm design.
What data structure is used in Rotate Array?
The problem primarily uses arrays. Some implementations also rely on the two-pointer technique to reverse parts of the array efficiently while keeping the operation in-place.
What is the time complexity of Rotate Array?
Most optimal solutions run in O(n) time because each element must be moved or processed at least once. The in-place reversal technique performs three linear passes over the array but still remains O(n).

Ready to solve this problem?

Practice Rotate Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Make K-Subarray Sums Equal

Next

Maximum Number of Matching Indices After Right Shifts