Rotate an Array Left or Right by K Positions - Java

Category: Medium | Concepts used: Extra array rotation, in-place reversal trick

---

Problem Statement

Given an array and a number K, rotate the array left (or right) by K positions.

Input : [1,2,3,4,5], K=2, rotate RIGHT      Output: [4,5,1,2,3]
Input : [1,2,3,4,5], K=2, rotate LEFT        Output: [3,4,5,1,2]

Examples (with edge scenarios)

#	Input	K	Direction	Output	Why
1	[1,2,3,4,5]	2	Right	[4,5,1,2,3]	Last 2 elements move to front
2	[1,2,3,4,5]	2	Left	[3,4,5,1,2]	First 2 elements move to end
3	[1,2,3,4,5]	5 (K == length)	Either	[1,2,3,4,5]	Full rotation = no visible change
4	[1,2,3,4,5]	7 (K > length)	Either	Same as K=2 (7 mod 5 = 2)	K larger than array length wraps around
5	[]	any K	Either	[]	Nothing to rotate

Common Fresher Mistake

Mistake	What happens	Fix
Not reducing K using K % length first	Unnecessary repeated rotations, or index errors if K > length	Always compute K = K % arr.length first (careful: also guard against length == 0)
Rotating one position at a time, K times, in a loop	Works, but wastes time — O(n*K) instead of O(n)	Prefer a single-pass approach (extra array, or the reversal trick)

---

Before You Code: Clarify the Contract

Before choosing an algorithm, confirm whether the array may be null or empty, whether duplicates and original order matter, whether the method may modify the input, and whether the answer should contain values or original indices. These choices can change both the code and the best data structure.

Analogy: The Divided Notebook Reversal

Imagine you have a binder notebook with 5 pages: [1, 2, 3, 4, 5]. You want to shift the last 2 pages to the front ([4, 5, 1, 2, 3]):

• Step 1 (Reverse everything): You take the entire stack of pages and flip it upside down: [5, 4, 3, 2, 1]. Now the pages you wanted at the front (4 and 5) are at the front, but they are backwards (5 then 4). The remaining pages are also at the back but backwards (3, 2, 1).
• Step 2 (Reverse first chunk): You take just the first 2 pages ([5, 4]) and flip them back to their original order: [4, 5].
• Step 3 (Reverse second chunk): You take the remaining 3 pages ([3, 2, 1]) and flip them back to their original order: [1, 2, 3].
• Your binder is now perfectly rotated!

---

Solution 1 — Using an Extra Array (Simple)

Intuition

For a right rotation by K, imagine cutting the array into two parts: the last K elements, and everything before them. In the rotated result, that last chunk simply moves to the front, followed by the rest — like sliding a deck of cards’ bottom portion to the top.

import java.util.Arrays;

public class RotateArrayExtra {
    public static int[] rotateRight(int[] arr, int k) {
        int n = arr.length;
        if (n == 0) return arr;
        k = k % n; // handle K larger than array length

int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            result[(i + k) % n] = arr[i]; // shift each element k positions forward, wrapping around
        }
        return result;
    }

public static void main(String[] args) {
        System.out.println(Arrays.toString(rotateRight(new int[]{1,2,3,4,5}, 2))); // [4,5,1,2,3]
        System.out.println(Arrays.toString(rotateRight(new int[]{1,2,3,4,5}, 7))); // same as K=2
    }
}

Output:

[4, 5, 1, 2, 3]
[4, 5, 1, 2, 3]

Dry Run (arr=[1,2,3,4,5], k=2)

n=5, k=2%5=2

i=0: result[(0+2)%5=2] = 1  -> result=[_,_,1,_,_]
i=1: result[(1+2)%5=3] = 2  -> result=[_,_,1,2,_]
i=2: result[(2+2)%5=4] = 3  -> result=[_,_,1,2,3]
i=3: result[(3+2)%5=0] = 4  -> result=[4,_,1,2,3]
i=4: result[(4+2)%5=1] = 5  -> result=[4,5,1,2,3]

Final: [4, 5, 1, 2, 3]

Interviewer’s take

Clean and correct — the (i + k) % n trick for “wraparound” indexing is a good, reusable pattern. Uses O(n) extra space though, which some interviewers will ask you to eliminate.

Follow-up questions you might get:

• “Can you rotate the array in-place, without extra space?” → leads to Solution 2.

---

Solution 2 — The Reversal Trick (In-Place, O(1) Extra Space)

Intuition

Here’s a clever trick: to rotate right by K, (1) reverse the entire array, (2) then reverse just the first K elements, (3) then reverse the remaining elements. Reversing the whole thing flips everything backward; re-reversing each of the two “halves” separately un-flips them internally while keeping their new overall positions — the net effect is exactly a rotation.

public class RotateArrayReversal {

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

public static void rotateRight(int[] arr, int k) {
        int n = arr.length;
        if (n == 0) return;
        k = k % n;

reverse(arr, 0, n - 1);       // Step 1: reverse the whole array
        reverse(arr, 0, k - 1);        // Step 2: reverse the first k elements
        reverse(arr, k, n - 1);        // Step 3: reverse the remaining elements
    }

public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        rotateRight(arr, 2);
        System.out.println(java.util.Arrays.toString(arr)); // [4, 5, 1, 2, 3]
    }
}

Output:

[4, 5, 1, 2, 3]

Dry Run (arr=[1,2,3,4,5], k=2)

Step 1: reverse whole array (0 to 4)
  [1,2,3,4,5] -> [5,4,3,2,1]

Step 2: reverse first k=2 elements (0 to 1)
  [5,4,3,2,1] -> [4,5,3,2,1]

Step 3: reverse remaining elements (2 to 4)
  [4,5,3,2,1] -> [4,5,1,2,3]

Final: [4, 5, 1, 2, 3]

Interviewer’s take

This is the preferred, most impressive answer — true O(1) extra space, O(n) time, done entirely in-place using only a reusable reverse() helper. This “reverse the parts to rotate the whole” trick is a well-known and elegant pattern that’s great to have in your toolkit — it comes up in several array manipulation problems.

Follow-up questions you might get:

• “How would you rotate LEFT instead of right using this trick?” → Same three-step idea, just reverse the first (n-k) elements and the remaining k elements instead (or equivalently, treat “rotate left by K” as “rotate right by n-k”).
• “What’s the time complexity of the three reverse calls combined?” → Each reverse touches its portion once; combined, all three together still only touch each element a constant number of times — overall O(n).

---

📊 Visual Flowchart

graph TD
    Start["Input Array [1, 2, 3, 4, 5], K=2"] --> Step1["Step 1: Reverse Entire Array<br>[5, 4, 3, 2, 1]"]
    Step1 --> Step2["Step 2: Reverse First K elements (0 to K-1)<br>[4, 5, 3, 2, 1]"]
    Step2 --> Step3["Step 3: Reverse Remaining elements (K to N-1)<br>[4, 5, 1, 2, 3]"]
    Step3 --> End["Result: [4, 5, 1, 2, 3]"]

---

Final Verdict — Which Solution Should You Give?

• Solution 2 (reversal trick) is the gold-standard answer for this classic problem — mention it even if you start with Solution 1.

---

Quick Recap

Approach	Time	Space	In-place?
Extra array	O(n)	O(n)	No
Reversal trick	O(n)	O(1)	Yes