Log inSign up
mediumLeetCodeNot Started

Rotate Array

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

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

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?

Example 1 · Standard Right Rotation:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation: Rotate 1: [7,1,2,3,4,5,6], Rotate 2: [6,7,1,2,3,4,5], Rotate 3: [5,6,7,1,2,3,4].

Example 2 · k Greater than Length:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation: After 2 rotations, the last 2 elements move to the front.

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Two-pointer array reversal
  • Modulo arithmetic (k % n)

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the 3-step reversal technique for cyclic partitions.
  • Handle large rotation counts via modulo k % n.
  • Implement in-place two-pointer array reversals.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • If the array is sorted or can be sorted without violating problem requirements, evaluate Two Pointers or Binary Search.
  • If tracking contiguous subsegments with monotone expansion/shrinkage, apply Sliding Window.
  • If frequency or complement lookups are required in O(1) time, use a Hash Map or Frequency Array.

Connected Patterns:

Reverse Words in a StringString Rotation / Juggling Algorithm

1. Brute Force — Shift by 1 Step k Times

Intuition

In each step, save the last element and shift all elements one index to the right, placing the last element at index 0.

Algorithm

  1. Initialize required state variables and allocate data structures for Brute Force — Shift by 1 Step k Times.
  2. Iterate through the input array and apply the core algorithmic condition.
  3. Update boundaries, frequencies, or pointers in accordance with the invariant.
  4. Return the computed result or transformed array.

Brute Force Single Step Right Shift Trace (k Times)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 3, 4, 5, 6, 7]
Current operationSTEP 1 OF 6
Rotation 1 of 3: Element 7 wraps to front
Visual state
Values and pointers at this exact step
table
S
7
1
2
3
4
5
6
0
↑ Rotation 1
1
2
3
4
5
6
Rotations Done1
Array[7, 1, 2, 3, 4, 5, 6]
Variables at this step
Rotations Done
1
Array
[7, 1, 2, 3, 4, 5, 6]
Check / comparison
Save last element (7). Shift [1..6] right by 1 index. Put 7 at index 0.
Decision / next transition
Array after 1st rotation: [7, 1, 2, 3, 4, 5, 6].
Why this step matters

Rotation 1 of 3: Element 7 wraps to front. All other elements shift right by 1 position.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7public:
8 void rotate(vector<int>& nums, int k) {
9 int n = nums.size();
10 k = k % n;
11 for (int step = 0; step < k; ++step) {
12 int last = nums[n - 1];
13 for (int i = n - 1; i > 0; --i) {
14 nums[i] = nums[i - 1];
15 }
16 nums[0] = last;
17 }
18 }
19};
20
21int main() {
22 Solution sol;
23 vector<int> nums = {1, 2, 3, 4, 5, 6, 7};
24 int k = 3;
25 cout << "Initial: ";
26 for (int x : nums) cout << x << " ";
27 cout << "\n";
28
29 sol.rotate(nums, k);
30 cout << "Rotated: ";
31 for (int x : nums) cout << x << " ";
32 cout << "\n";
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for Brute Force — Shift by 1 Step k Times.
  • Space complexity: O(1) — Space complexity for Brute Force — Shift by 1 Step k Times.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Better — Extra Buffer Array

Intuition

Every element at index i moves to (i + k) % n. Allocate a secondary array, populate it, and copy back.

Algorithm

  1. Every element at index i moves to (i + k) % n
  2. Allocate a secondary array, populate it, and copy back.

Auxiliary Array with Modulo Index Mapping Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 3, 4, 5, 6, 7]
Current operationSTEP 1 OF 6
Map Idx 0: Value 1 moves to index 3 in temp array
Visual state
Values and pointers at this exact step
table
S
1
2
3
4
5
6
7
0
↑ (0+3)%7 = 3
1
2
3
4
5
6
temp[3]1
Variables at this step
temp[3]
1
Check / comparison
Map index 0 to (0 + 3) % 7 = 3: temp[3] = 1.
Decision / next transition
temp[3] = 1.
Why this step matters

Map Idx 0: Value 1 moves to index 3 in temp array.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7public:
8 void rotate(vector<int>& nums, int k) {
9 int n = nums.size();
10 k = k % n;
11 vector<int> temp(n);
12 for (int i = 0; i < n; ++i) {
13 temp[(i + k) % n] = nums[i];
14 }
15 nums = temp;
16 }
17};
18
19int main() {
20 Solution sol;
21 vector<int> nums = {1, 2, 3, 4, 5, 6, 7};
22 int k = 3;
23 cout << "Initial: ";
24 for (int x : nums) cout << x << " ";
25 cout << "\n";
26
27 sol.rotate(nums, k);
28 cout << "Rotated: ";
29 for (int x : nums) cout << x << " ";
30 cout << "\n";
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(N log N) — Time complexity for Better — Extra Buffer Array.
  • Space complexity: O(N) — Space complexity for Better — Extra Buffer Array.

3. Optimal — Three-Step Reversal Invariant

Intuition

Reverse the full array, then reverse the first k elements, then reverse the remaining n-k elements. This achieves in-place rotation in O(N) time with O(1) space.

Algorithm

  1. Reverse the full array, then reverse the first k elements, then reverse the remaining n-k elements
  2. This achieves in-place rotation in O(N) time with O(1) space.

Triple In-Place Reversal Algorithm Trace

2 of 2 questions left today
Step 1 / 7
Trace timeline14% explored
InputINPUT nums = [1, 2, 3, 4, 5, 6, 7]
Current operationSTEP 1 OF 7
Pass 1 (Outer Swap): Reverse entire array [0
Visual state
Values and pointers at this exact step
table
S
1
2
3
4
5
6
7
0
↑ L=0
1
2
3
4
5
6
↑ R=6
L0
R6
Array[7, 2, 3, 4, 5, 6, 1]
PhaseReverse All
Variables at this step
L
0
R
6
Array
[7, 2, 3, 4, 5, 6, 1]
Phase
Reverse All
Check / comparison
Pass 1: Reverse entire array. Swap nums[0] (1) and nums[6] (7).
Decision / next transition
nums[0]=7, nums[6]=1. Move L to 1, R to 5.
Why this step matters

Pass 1 (Outer Swap): Reverse entire array [0..6]. Swap first and last elements.

Step 1 / 7
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 void rotate(vector<int>& nums, int k) {
10 int n = nums.size();
11 k = k % n;
12 if (k == 0) return;
13
14 reverseRange(nums, 0, n - 1);
15 reverseRange(nums, 0, k - 1);
16 reverseRange(nums, k, n - 1);
17 }
18
19private:
20 void reverseRange(vector<int>& nums, int start, int end) {
21 while (start < end) {
22 swap(nums[start++], nums[end--]);
23 }
24 }
25};
26
27int main() {
28 Solution sol;
29 vector<int> nums = {1, 2, 3, 4, 5, 6, 7};
30 int k = 3;
31 cout << "Initial: ";
32 for (int x : nums) cout << x << " ";
33 cout << "\n";
34
35 sol.rotate(nums, k);
36 cout << "Optimal In-Place Rotated: ";
37 for (int x : nums) cout << x << " ";
38 cout << "\n";
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(N) — Time complexity for Optimal — Three-Step Reversal Invariant.
  • Space complexity: O(1) — Space complexity for Optimal — Three-Step Reversal Invariant.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Shift by 1 step k timesO(N * k)O(1)Shift all elements right by 1 position in a loop, repeated k times.Shifts N elements k times.
2.Better — Extra Buffer ArrayO(N)O(N)Place nums[i] at (i + k) % n in a new array, then copy back.Memory allocation of secondary array.
3.Optimal — Three-Step Reversal InvariantOptimalO(N)O(1)Reverse whole array, reverse first k, reverse remaining n-k elements.None; industry gold-standard.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Edge Case — Input: `, Expected: ` —
  • Edge Case — Input: `, Expected: ` —
  • Edge Case — Input: `, Expected: ` —

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Rotate Array?

2.Why is the brute force approach suboptimal for large inputs in Rotate Array?

3.Which data structure or technique enables the optimal solution for Rotate Array?

Back to DSA Sheet