Backend interview prep

Start

Rotate Array (LeetCode

Learn how to solve the Rotate Array problem using repeated shifting, an extra array, cyclic replacement, and the optimal reversal algorithm. Includes intuition, dry runs, Java code, complexity analysis, edge cases, interview tips, and production applications.

Rotate Array (LeetCode #189)

Introduction

Rotate Array is a classic array manipulation problem frequently asked in coding interviews.

It is commonly associated with companies such as:

  • Amazon
  • Google
  • Microsoft
  • Meta
  • Apple
  • Adobe
  • Bloomberg
  • Oracle
  • Goldman Sachs

This problem tests your understanding of:

  • In-place array modification
  • Modular arithmetic
  • Array reversal
  • Cyclic movement
  • Time and space optimization
  • Edge-case handling

The most important insight is:

Rotating an array to the right by k positions can be achieved by reversing the entire array, then reversing the first k elements, and finally reversing the remaining elements.

Problem Statement

Given an integer array nums, rotate the array to the right by k steps.

The operation should ideally be performed in-place.

Example 1

Input

nums = [1,2,3,4,5,6,7]
k = 3

Output

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

Explanation:

Rotate 1 time

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

Rotate 2 times

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

Rotate 3 times

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

Example 2

Input

nums = [-1,-100,3,99]
k = 2

Output

[3,99,-1,-100]

What Does Rotation Mean?

Right rotation moves each element to a new position.

For an array of length n:

newIndex = (oldIndex + k) % n

Example:

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

k = 2

Indexes move as follows:

Old Index Value New Index
0 1 2
1 2 3
2 3 4
3 4 0
4 5 1

Final array:

[4,5,1,2,3]

Why Use k % n?

If:

n = 7

k = 10

Rotating 10 times is equivalent to rotating:

10 % 7 = 3

times.

Therefore:

k = k % nums.length;

This avoids unnecessary work.

Approach 1 — Rotate One Step at a Time

Idea

Repeat the following operation k times:

  1. Store the last element.
  2. Shift all other elements one position to the right.
  3. Place the saved element at index 0.

One-Step Rotation

graph TD
    N_1_2_3_4_5["(1,2,3,4,5)"] --> Save_5["Save 5"]
    Save_5["Save 5"] --> Shift_Right["Shift Right"]
    Shift_Right["Shift Right"] --> N_1_1_2_3_4["(1,1,2,3,4)"]
    N_1_1_2_3_4["(1,1,2,3,4)"] --> Place_5_at_Front["Place 5 at Front"]
    Place_5_at_Front["Place 5 at Front"] --> N_5_1_2_3_4["(5,1,2,3,4)"]

Java Code — Repeated Shifting

public class RotateArrayBruteForce {

    public void rotate(int[] nums, int k) {

        if (nums.length == 0) {

            return;

        }

        k %= nums.length;

        for (int rotation = 0;
             rotation < k;
             rotation++) {

            int last = nums[nums.length - 1];

            for (int i = nums.length - 1;
                 i > 0;
                 i--) {

                nums[i] = nums[i - 1];

            }

            nums[0] = last;

        }

    }

}

Complexity

Complexity Value
Time O(n × k)
Space O(1)

This approach modifies the array in-place but becomes slow when k is large.

Approach 2 — Using an Extra Array

Core Idea

Create a new array.

For every element at index i, calculate its rotated position:

(i + k) % n

Then copy the result back into the original array.

Example

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

k = 2

Mapping:

1 → index 2

2 → index 3

3 → index 4

4 → index 0

5 → index 1

Result:

[4,5,1,2,3]

Java Code — Extra Array

public class RotateArrayUsingExtraSpace {

    public void rotate(int[] nums, int k) {

        int length = nums.length;

        if (length == 0) {

            return;

        }

        k %= length;

        int[] rotated = new int[length];

        for (int i = 0; i < length; i++) {

            int newIndex = (i + k) % length;

            rotated[newIndex] = nums[i];

        }

        System.arraycopy(
                rotated,
                0,
                nums,
                0,
                length);

    }

}

Complexity

Complexity Value
Time O(n)
Space O(n)

This solution is simple and readable but does not satisfy the optimal constant-space requirement.

Approach 3 — Reversal Algorithm

Core Idea

Suppose:

nums = [1,2,3,4,5,6,7]

k = 3

The desired result is:

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

Perform three reversals.

Step 1 — Reverse the Entire Array

graph TD
    Original["Original"] --> N_1_2_3_4_5_6_7["(1,2,3,4,5,6,7)"]
    N_1_2_3_4_5_6_7["(1,2,3,4,5,6,7)"] --> Reverse_All["Reverse All"]
    Reverse_All["Reverse All"] --> N_7_6_5_4_3_2_1["(7,6,5,4,3,2,1)"]

Step 2 — Reverse the First k Elements

graph TD
    First_k_3_elements["First k = 3 elements"] --> N_7_6_5["(7,6,5)"]
    N_7_6_5["(7,6,5)"] --> Reverse["Reverse"]
    Reverse["Reverse"] --> N_5_6_7["(5,6,7)"]

Array becomes:

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

Step 3 — Reverse the Remaining Elements

graph TD
    Remaining_elements["Remaining elements"] --> N_4_3_2_1["(4,3,2,1)"]
    N_4_3_2_1["(4,3,2,1)"] --> Reverse["Reverse"]
    Reverse["Reverse"] --> N_1_2_3_4["(1,2,3,4)"]

Final array:

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

Why the Reversal Algorithm Works

Split the array into two parts.

A = First n - k elements

B = Last k elements

Original:

A B

Desired result:

B A

After reversing the entire array:

reverse(B) reverse(A)

Then reverse each part separately:

B A

This produces the required rotation.

Dry Run

Input

nums = [1,2,3,4,5,6,7]

k = 3

Normalize k

k = 3 % 7

k = 3

Reverse Whole Array

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

Reverse Index 0 to 2

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

Reverse Index 3 to 6

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

Final answer:

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

Java Code — Optimal Reversal Solution

public class RotateArray {

    public void rotate(int[] nums, int k) {

        int length = nums.length;

        if (length == 0) {

            return;

        }

        k %= length;

        reverse(
                nums,
                0,
                length - 1);

        reverse(
                nums,
                0,
                k - 1);

        reverse(
                nums,
                k,
                length - 1);

    }

    private void reverse(
            int[] nums,
            int left,
            int right) {

        while (left < right) {

            int temp = nums[left];

            nums[left] = nums[right];

            nums[right] = temp;

            left++;
            right--;

        }

    }

}

Cleaner Java Implementation

public class Solution {

    public void rotate(int[] nums, int k) {

        int n = nums.length;

        if (n <= 1) {

            return;

        }

        k %= n;

        if (k == 0) {

            return;

        }

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

    }

    private void reverse(
            int[] nums,
            int start,
            int end) {

        while (start < end) {

            int temp = nums[start];

            nums[start++] = nums[end];

            nums[end--] = temp;

        }

    }

}

Complexity Analysis

Complexity Value
Time O(n)
Space O(1)

Each element participates in a constant number of swaps.

No additional array is required.

Approach 4 — Cyclic Replacement

Core Idea

Every element moves to:

(currentIndex + k) % n

Instead of using another array, move values through cycles.

Because some rotations form multiple independent cycles, continue until all n elements have been moved.

Example

nums = [1,2,3,4,5,6]

k = 2

Movement:

0 → 2 → 4 → 0

Another cycle:

1 → 3 → 5 → 1

There are two separate cycles.

Java Code — Cyclic Replacement

public class RotateArrayUsingCycles {

    public void rotate(int[] nums, int k) {

        int length = nums.length;

        if (length == 0) {

            return;

        }

        k %= length;

        int moved = 0;

        for (int start = 0;
             moved < length;
             start++) {

            int currentIndex = start;
            int previousValue = nums[start];

            do {

                int nextIndex =
                        (currentIndex + k)
                                % length;

                int temp = nums[nextIndex];

                nums[nextIndex] = previousValue;

                previousValue = temp;

                currentIndex = nextIndex;

                moved++;

            } while (currentIndex != start);

        }

    }

}

Complexity of Cyclic Replacement

Complexity Value
Time O(n)
Space O(1)

This is also optimal but is harder to explain and implement correctly than the reversal approach.

Reversal vs Cyclic Replacement

Reversal Algorithm Cyclic Replacement
Easier to understand More complex
Three reverse operations Moves values through cycles
O(n) time O(n) time
O(1) space O(1) space
Preferred in interviews Useful advanced alternative

The reversal approach is usually the best interview answer.

Edge Cases

Empty Array

Input

[]

No operation is required.

Single Element

Input

[5]

k = 100

Output:

[5]

k Is Zero

Input

[1,2,3]

k = 0

Output:

[1,2,3]

k Equals Array Length

Input

[1,2,3,4]

k = 4

Normalize:

4 % 4 = 0

Output:

[1,2,3,4]

k Is Greater Than Array Length

Input

[1,2,3,4,5]

k = 7

Normalize:

7 % 5 = 2

Output:

[4,5,1,2,3]

Duplicate Values

Input

[1,1,2,2,3]

k = 2

Output:

[2,3,1,1,2]

The algorithm works regardless of duplicate values.

Negative Values

Input

[-1,-2,-3,-4]

k = 1

Output:

[-4,-1,-2,-3]

Left Rotation

A common follow-up asks for rotation to the left.

Example:

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

k = 2

Left rotation result:

[3,4,5,1,2]

Left Rotation Using Reversal

Steps:

  1. Reverse the first k elements.
  2. Reverse the remaining elements.
  3. Reverse the whole array.
public class LeftRotateArray {

    public void rotateLeft(int[] nums, int k) {

        int n = nums.length;

        if (n == 0) {

            return;

        }

        k %= n;

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

    }

    private void reverse(
            int[] nums,
            int left,
            int right) {

        while (left < right) {

            int temp = nums[left];

            nums[left] = nums[right];

            nums[right] = temp;

            left++;
            right--;

        }

    }

}

Right Rotation vs Left Rotation

For an array of length n:

Right rotate by k

is equivalent to:

Left rotate by n - k

after normalizing k.

Example:

n = 7

Right rotate by 3

=

Left rotate by 4

Comparison of Approaches

Approach Time Space Recommended
Repeated shifting O(n × k) O(1) No
Extra array O(n) O(n) Good starting point
Cyclic replacement O(n) O(1) Advanced
Reversal algorithm O(n) O(1) Best

Common Interview Mistakes

Mistake 1 — Forgetting to Normalize k

Without:

k %= nums.length;

the algorithm may perform unnecessary work or use incorrect indexes.

Mistake 2 — Dividing by Zero for Empty Arrays

This is invalid:

k %= nums.length;

when:

nums.length = 0

Check the length first.

Mistake 3 — Reversing the Wrong Ranges

For right rotation:

Reverse whole array

Reverse 0 to k - 1

Reverse k to n - 1

Mistake 4 — Off-by-One Errors

Correct boundaries:

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

Mistake 5 — Using Extra Space Without Mentioning It

The temporary-array solution is valid but requires:

O(n)

additional space.

Mistake 6 — Confusing Right and Left Rotation

Right rotation moves the final k values to the beginning.

Left rotation moves the first k values to the end.

Mistake 7 — Repeating One-Step Rotation for Large k

The repeated-shifting method can degrade to:

O(n²)

when k is proportional to n.

Production Applications

Array rotation concepts appear in:

  • Circular buffers
  • Ring queues
  • Scheduling systems
  • Log rotation
  • Load-balancing algorithms
  • Time-series data alignment
  • Image row transformations
  • Sliding dashboards
  • Round-robin assignment
  • Cache replacement systems

Real-World Example — Round-Robin Scheduling

Suppose workers are assigned in this order:

[A,B,C,D]

After one scheduling round, rotate by one:

[D,A,B,C]

Repeated rotation can model fair task distribution.

In actual production systems, circular indexes are usually more efficient than physically rotating the array.

Real-World Example — Circular Buffer

A circular buffer does not normally move every element.

Instead, it adjusts logical start and end indexes using modular arithmetic.

Conceptually:

newIndex = (index + offset) % capacity

The Rotate Array problem builds the same modular-indexing intuition.

Follow-Up Question 1 — Can Rotation Be Done Without Moving Data?

Yes.

Maintain a logical offset.

Example:

physicalIndex

=

(logicalIndex + offset) % n

This is useful in circular buffers and view-based data structures.

Follow-Up Question 2 — What If k Is Negative?

A negative value can represent left rotation.

Normalize it using:

k = ((k % n) + n) % n;

Then perform right rotation by the normalized value.

Example:

k = -2

n = 5

Normalized right rotation:

((-2 % 5) + 5) % 5

=

3

Left rotation by 2 equals right rotation by 3.

Follow-Up Question 3 — Rotate a Linked List

For a linked list:

  1. Find the length.
  2. Connect the tail to the head to form a cycle.
  3. Find the new tail.
  4. Break the cycle.

This becomes LeetCode #61 — Rotate List.

Follow-Up Question 4 — Rotate a Matrix

Matrix rotation requires different transformations.

For a 90-degree clockwise rotation:

  1. Transpose the matrix.
  2. Reverse every row.

This becomes LeetCode #48 — Rotate Image.

Follow-Up Question 5 — What If the Array Is Very Large?

Consider:

  • Logical offsets instead of physical movement
  • Chunk-based rotation
  • Memory-mapped files
  • Block swap algorithms
  • Distributed data partition movement

For normal in-memory arrays, the reversal algorithm remains optimal.

Follow-Up Question 6 — Why Is Reversal Better Than Sorting?

Sorting changes the element order based on value.

Rotation must preserve the relative order of all elements.

Therefore, sorting cannot solve this problem.

Interview Explanation

A strong interview explanation could be:

I first normalize k using k % n. To rotate in-place, I reverse the entire array, which brings the last k elements to the front but in reverse order. I then reverse the first k elements and the remaining n-k elements separately. This restores the order within both groups and produces the required rotation in O(n) time and O(1) extra space.

Interview Tips

Interviewers commonly ask:

  • Why normalize k?
  • Why does the reversal algorithm work?
  • Why are three reversals required?
  • What is the time complexity?
  • What is the extra-space complexity?
  • How do you handle an empty array?
  • How would you rotate left?
  • Can you solve it using cyclic replacement?
  • Can rotation be represented using a logical offset?
  • How would the solution change for a linked list or matrix?

Explain the split into:

A B

↓

B A

before writing the code.

Unit Tests

import static org.junit.jupiter.api.Assertions.assertArrayEquals;

import org.junit.jupiter.api.Test;

class RotateArrayTest {

    private final RotateArray solution =
            new RotateArray();

    @Test
    void shouldRotateTypicalArray() {

        int[] nums =
                {1, 2, 3, 4, 5, 6, 7};

        solution.rotate(nums, 3);

        assertArrayEquals(
                new int[]{5, 6, 7, 1, 2, 3, 4},
                nums);

    }

    @Test
    void shouldRotateWhenKExceedsLength() {

        int[] nums = {1, 2, 3, 4, 5};

        solution.rotate(nums, 7);

        assertArrayEquals(
                new int[]{4, 5, 1, 2, 3},
                nums);

    }

    @Test
    void shouldHandleSingleElement() {

        int[] nums = {1};

        solution.rotate(nums, 10);

        assertArrayEquals(
                new int[]{1},
                nums);

    }

    @Test
    void shouldHandleZeroRotation() {

        int[] nums = {1, 2, 3};

        solution.rotate(nums, 0);

        assertArrayEquals(
                new int[]{1, 2, 3},
                nums);

    }

    @Test
    void shouldHandleNegativeValues() {

        int[] nums = {-1, -100, 3, 99};

        solution.rotate(nums, 2);

        assertArrayEquals(
                new int[]{3, 99, -1, -100},
                nums);

    }

}

Summary

The Rotate Array problem demonstrates how modular arithmetic and array reversal can replace repeated element shifting.

The brute-force shifting solution is in-place but may require:

O(n × k)

time.

The extra-array solution improves time to:

O(n)

but uses additional memory.

The reversal algorithm is optimal:

Time: O(n)

Space: O(1)

It performs three carefully chosen reversals to transform:

A B

into:

B A

Key Takeaways

  • Normalize rotation using k % n.
  • Handle the empty array before applying modulo.
  • Right rotation moves the final k values to the front.
  • Repeated shifting is simple but inefficient.
  • An extra array provides an easy O(n) solution.
  • Cyclic replacement is optimal but more complex.
  • The reversal algorithm is the preferred interview solution.
  • Reverse the complete array first.
  • Reverse the first k elements.
  • Reverse the remaining n-k elements.
  • Achieve O(n) time and O(1) extra space.
  • Use modular arithmetic for circular data structures.
  • Explain the A B → B A transformation clearly.