DSA-008 · In-place rotation by reversal
Rotate Array
Intermediate · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 6560 deterministic checks. Learner drafts are not executed.
Understand the problem
Rotate an array to the right by k positions in place. Keep the same array object and reorder its values according to the right-rotation mapping.
- nums is non-null with 0–100,000 signed int values; k is a nonnegative long from 0 to Long.MAX_VALUE. Negative k is outside the contract.
- Mutate nums and return void. For nonempty input, the value originally at i ends at (i+(k mod n)) mod n. Empty input remains empty.
- The optimized algorithm uses O(1) auxiliary space. Normalize only after the empty check to avoid division by zero. Repeated values retain their occurrence positions under the same mapping.
Examples
Input:
nums=[1,2,3,4,5,6,7], k=3
Output:nums becomes [5,6,7,1,2,3,4]The last three positions move to the front without reversing either block’s final order.
Input:
nums=[1,2,3], k=4
Output:nums becomes [3,1,2]Four right steps are equivalent to one because k mod 3 is one.
Before you start
- Modular index mapping
- Two-pointer reversal and mutation ownership
Recognize the structure
Rotation moves two contiguous blocks while preserving the internal order of each. Reversal changes both block order and internal orientation in a controllable way. This is an in-place permutation problem, unlike returning a separate shifted copy.
Try before revealing
Hint 1
Describe a right rotation as moving a suffix before a prefix.
Hint 2
What order does reversing the whole concatenation produce?
Hint 3
Reverse the whole array, then each of its two new blocks.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Copy the original and write destinations
Clone nums, normalize shift, and write original[i] to nums[(i+shift)%n]. For [1,2,3,4] and shift 1, the destinations are 1,2,3,0, giving [4,1,2,3]. This is O(n) time and O(n) copy space; it is a useful independent mapping for testing the constant-space implementation.
Improve the baseline
Split into A and B
For right shift s, let B be the last s values and A the preceding values. The desired result is BA.
Reverse the entire array
Reversing AB produces reverse(B) followed by reverse(A). The blocks are in the desired order but both are backwards.
Repair each block’s orientation
Reverse positions 0..s-1 and s..n-1. This yields B followed by A with each original internal order restored. A zero normalized shift can return immediately.
Why it is correct
Permutation through swaps
Each reversal swaps symmetric positions within an inclusive range and preserves every occurrence. No value is lost or duplicated.
Block identity
Writing Aᴿ for reversal, (AB)ᴿ=BᴿAᴿ. Reversing those two resulting ranges gives BA, exactly the right-rotation block decomposition.
Bounds and termination
After normalization, 0≤s<n. For nonzero s both ranges are valid; each reversal shrinks its two-pointer interval. Empty input is handled before modulo, and s=0 leaves input unchanged.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
public final class Solution {
public static void rotate(int[] nums, long k) {
if (nums.length == 0) return;
int shift = (int) (k % nums.length);
if (shift == 0) return;
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, shift - 1);
reverse(nums, shift, nums.length - 1);
}
private static void reverse(int[] nums, int left, int right) {
while (left < right) {
int temporary = nums[left]; nums[left] = nums[right]; nums[right] = temporary;
left++; right--;
}
}
public static void baseline(int[] nums, long k) {
if (nums.length == 0) return;
int shift = (int) (k % nums.length);
int[] original = nums.clone();
for (int i = 0; i < nums.length; i++) nums[(i + shift) % nums.length] = original[i];
}
}
Read the meaningful blocks
Keep k as long until modulo
Casting a huge k to int first can lose its intended normalized shift.
Use inclusive reversal bounds
The first block ends at shift-1; using shift would rotate the wrong split.
Swap before advancing
Each pair is exchanged once. The left<right guard naturally handles empty or singleton ranges.
Complexity
O(n) time: reversing the whole array and both disjoint blocks performs linear total swaps. O(1) auxiliary space and no separately allocated output.
The copy-and-map baseline is O(n) time and O(n) extra storage. Repeating a one-step shift k times can cost O(nk), even though k may be much larger than n.
Exact-state walkthroughs
Reveal normal and boundary traces
Restore both reversed blocks
Input: {"nums":[1,2,3,4,5],"k":2} · Final state: [4,5,1,2,3]
Step 1 of 9: Guard empty input and normalize the right shift.
A normalized shift is bounded before conversion to int.
- 0: 1
- 1: 2
- 2: 3
- 3: 4
- 4: 5
| Variable | Value |
|---|---|
| values | [1,2,3,4,5] |
| shift | 2 |
See the affected Java block
1 public final class Solution { 2 public static void rotate(int[] nums, long k) { 3 if (nums.length == 0) return; 4 int shift = (int) (k % nums.length); 5 if (shift == 0) return; 6 reverse(nums, 0, nums.length - 1); 7 reverse(nums, 0, shift - 1); 8 reverse(nums, shift, nums.length - 1); 9 } 10 private static void reverse(int[] nums, int left, int right) { 11 while (left < right) { 12 int temporary = nums[left]; nums[left] = nums[right]; nums[right] = temporary; 13 left++; right--; 14 } 15 } 16 public static void baseline(int[] nums, long k) { 17 if (nums.length == 0) return; 18 int shift = (int) (k % nums.length); 19 int[] original = nums.clone(); 20 for (int i = 0; i < nums.length; i++) nums[(i + shift) % nums.length] = original[i]; 21 } 22 } 23
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Guard empty input and normalize the right shift.
A normalized shift is bounded before conversion to int.
- values
[1,2,3,4,5]- shift
2
- Begin the whole reversal.
Each reversal permutes its own inclusive range without losing an occurrence.
- phase
"whole"- start
0- end
4- left
0- right
4- values
[1,2,3,4,5]
- Swap a symmetric pair and shrink the range.
Positions outside the remaining interval have their reversed destinations for this phase.
- phase
"whole"- start
0- end
4- leftBefore
0- rightBefore
4- left
1- right
3- values
[5,2,3,4,1]
- Swap a symmetric pair and shrink the range.
Positions outside the remaining interval have their reversed destinations for this phase.
- phase
"whole"- start
0- end
4- leftBefore
1- rightBefore
3- left
2- right
2- values
[5,4,3,2,1]
- Begin the front reversal.
Each reversal permutes its own inclusive range without losing an occurrence.
- phase
"front"- start
0- end
1- left
0- right
1- values
[5,4,3,2,1]
- Swap a symmetric pair and shrink the range.
Positions outside the remaining interval have their reversed destinations for this phase.
- phase
"front"- start
0- end
1- leftBefore
0- rightBefore
1- left
1- right
0- values
[4,5,3,2,1]
- Begin the back reversal.
Each reversal permutes its own inclusive range without losing an occurrence.
- phase
"back"- start
2- end
4- left
2- right
4- values
[4,5,3,2,1]
- Swap a symmetric pair and shrink the range.
Positions outside the remaining interval have their reversed destinations for this phase.
- phase
"back"- start
2- end
4- leftBefore
2- rightBefore
4- left
3- right
3- values
[4,5,1,2,3]
- Final in-place state; the Java method returns void.
The completed state satisfies the declared output and mutation contract.
- result
[4,5,1,2,3]
A full cycle
Input: {"nums":[1,2,3],"k":3} · Final state: [1,2,3]
Step 1 of 2: Guard empty input and normalize the right shift.
A normalized shift is bounded before conversion to int.
- 0: 1
- 1: 2
- 2: 3
| Variable | Value |
|---|---|
| values | [1,2,3] |
| shift | 0 |
See the affected Java block
1 public final class Solution { 2 public static void rotate(int[] nums, long k) { 3 if (nums.length == 0) return; 4 int shift = (int) (k % nums.length); 5 if (shift == 0) return; 6 reverse(nums, 0, nums.length - 1); 7 reverse(nums, 0, shift - 1); 8 reverse(nums, shift, nums.length - 1); 9 } 10 private static void reverse(int[] nums, int left, int right) { 11 while (left < right) { 12 int temporary = nums[left]; nums[left] = nums[right]; nums[right] = temporary; 13 left++; right--; 14 } 15 } 16 public static void baseline(int[] nums, long k) { 17 if (nums.length == 0) return; 18 int shift = (int) (k % nums.length); 19 int[] original = nums.clone(); 20 for (int i = 0; i < nums.length; i++) nums[(i + shift) % nums.length] = original[i]; 21 } 22 } 23
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Guard empty input and normalize the right shift.
A normalized shift is bounded before conversion to int.
- values
[1,2,3]- shift
0
- Final in-place state; the Java method returns void.
The completed state satisfies the declared output and mutation contract.
- result
[1,2,3]
Test the contract
Input:
nums=[], k=5
Output:[]No modulo by zero.
Input:
nums=[7], k=100
Output:[7]Singleton.
Input:
nums=[1,2,3], k=0
Output:[1,2,3]Zero shift.
Input:
nums=[1,2,3,4], k=4
Output:[1,2,3,4]A full cycle changes nothing.
Common mistakes and counterexamples
Apply modulo before the empty check
Counterexample: An empty array has n=0.
Return before computing k%n.
Cast k before normalizing
Counterexample: Long.MAX_VALUE is not safely represented as an int.
Compute long modulo n, then cast the bounded remainder.
Choose left-rotation block order
Counterexample: [1,2,3], k=1 must become [3,1,2].
Use the final suffix as the block moved to the front.
Overwrite destinations from the same array without protection
Counterexample: Writing a new value can destroy a source needed later.
Use the copied baseline, safe cycles, or proven reversal swaps.
Follow-ups
Rotate left by k.
For n>0, convert to a right shift (n-(k%n))%n or derive the opposite reversal sequence. Keep direction explicit and avoid negative modulo surprises.
Use cyclic replacements instead.
Move values along modular cycles while preserving the displaced value. Visit every cycle, not just the one starting at zero; gcd(n,shift) determines the number of cycles.
Rotate a linked list.
Find length and tail, normalize k, locate the new tail, connect the old tail to the old head, and break the cycle at the new boundary. Node identity replaces index swapping as the main invariant.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 109/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.