How to Solve: Rotate Array – Complete Guide for FAANG Interviews

How to Solve: Rotate Array – Complete Guide for FAANG Interviews

? Introduction

"This problem appears in 1 out of every 5 array-based interviews—mastering it proves you can optimize space, handle edge cases, and think in-place. Nail it, and you’ll stand out as a candidate who writes clean, efficient code under pressure."

? WHAT YOU NEED TO KNOW FIRST

Before tackling Rotate Array, ensure you understand: 1. Array indexing & modulo arithmetic – Critical for circular rotations. 2. In-place swaps & reversals – Key to optimizing space complexity. 3. Time/space trade-offs – When to use extra space vs. in-place operations.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK (Mental Checklist)

Follow this repeatable process for every Rotate Array problem:

1. Clarify the Problem
2. Ask: "Is rotation left or right?" (Default: right unless specified.)
3. Ask: "Can I use extra space?" (If not, in-place is required.)

4. Ask: "What’s the expected time/space complexity?" (Optimal: O(n) time, O(1) space.)

5. Handle Edge Cases

6. If nums is empty or k == 0, return immediately.

7. Normalize k: k = k % len(nums) (handles k > len(nums)).

8. Choose the Right Technique

9. Extra space allowed? → Brute-force (easiest).

10. In-place required? → Reverse trick (most efficient) or cyclic replacements.

11. Implement the Technique

12. For reverse trick:
    • Reverse entire array.
    • Reverse first k elements.
    • Reverse remaining n-k elements.

13. For cyclic replacements:

    • Track visited indices to avoid infinite loops.
    • Swap elements in cycles until all are placed.

14. Test with Examples

15. Small array (e.g., [1,2,3,4], k=2 → [3,4,1,2]).
16. Large k (e.g., k=5 for n=4 → same as k=1).

17. Empty array or k=0.

18. Analyze Complexity

19. Time: O(n) (each element moved once).
20. Space: O(1) (in-place) or O(n) (extra array).

? WORKED EXAMPLES

Example 1 – Basic (Right Rotation, In-Place)

Problem: Rotate array [1,2,3,4,5,6,7] by k=3 to the right.

Step-by-Step Solution (Reverse Trick)

1. Normalize k: k = 3 % 7 = 3.
2. Reverse entire array: [7,6,5,4,3,2,1].
3. Reverse first k elements: [5,6,7,4,3,2,1].
4. Reverse remaining elements: [5,6,7,1,2,3,4] (correct result).

Python Code

def rotate(nums, k):

    n = len(nums)

    k = k % n

    if n == 0 or k == 0:

        return


    # Reverse entire array

    nums.reverse()


    # Reverse first k elements

    nums[:k] = reversed(nums[:k])


    # Reverse remaining elements

    nums[k:] = reversed(nums[k:])

Complexity

• Time: O(n) (3 reversals, each O(n)).
• Space: O(1) (in-place).

Why This Works

• Reversing the entire array flips the order, bringing the last k elements to the front (but reversed).
• Reversing the first k and remaining n-k elements corrects their order.

Example 2 – Medium (Cyclic Replacements)

Problem: Rotate [1,2,3,4,5,6] by k=2 in-place without extra space.

Step-by-Step Solution (Cyclic Replacements)

1. Normalize k: k = 2 % 6 = 2.
2. Track visited indices to avoid infinite loops.
3. Start at index 0, swap nums[0] with nums[(0 + k) % n].
4. Swap 1 and 3 → [3,2,1,4,5,6].
5. Move to next index ((0 + k) % n = 2), swap nums[2] with nums[(2 + k) % n].
6. Swap 1 and 5 → [3,2,5,4,1,6].
7. Continue until all elements are placed (cycle completes when we return to index 0).

Python Code

def rotate(nums, k):

    n = len(nums)

    k = k % n

    if n == 0 or k == 0:

        return


    count = 0

    start = 0

    while count < n:

        current = start

        prev = nums[start]

        while True:

            next_idx = (current + k) % n

            nums[next_idx], prev = prev, nums[next_idx]

            current = next_idx

            count += 1

            if current == start:

                break

        start += 1

Complexity

• Time: O(n) (each element moved once).
• Space: O(1) (in-place).

Why This Works

• Each cycle places n / gcd(n, k) elements correctly.
• The loop terminates when all elements are visited.

Example 3 – Hard (Follow-Up: Left Rotation with Constraints)

Problem: Rotate [1,2,3,4,5,6,7] left by k=3 in O(1) space, but you cannot use the reverse trick.

Step-by-Step Solution (Juggling Algorithm)

1. Normalize k: k = 3 % 7 = 3.
2. Left rotation = right rotation by n-k:
3. k_left = n - k = 4.
4. Use cyclic replacements (same as Example 2).

Python Code

def rotate_left(nums, k):

    n = len(nums)

    k = k % n

    if n == 0 or k == 0:

        return


    # Convert left rotation to right rotation

    k = n - k

    count = 0

    start = 0

    while count < n:

        current = start

        prev = nums[start]

        while True:

            next_idx = (current + k) % n

            nums[next_idx], prev = prev, nums[next_idx]

            current = next_idx

            count += 1

            if current == start:

                break

        start += 1

Complexity

• Time: O(n).
• Space: O(1).

Why This Works

• Left rotation by k is equivalent to right rotation by n-k.
• Cyclic replacements handle the rotation in-place.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Alright, let’s lock this in. Rotate Array is all about three things: 1. Normalize k – Always do k = k % n to handle large rotations. 2. Choose your weapon – Extra space? Brute-force. In-place? Reverse trick or cyclic swaps. 3. Edge cases first – Empty array, k=0, or k=n are free points.

For the reverse trick, remember: reverse all, reverse first k, reverse the rest. For cyclic swaps, track visited indices to avoid infinite loops. Test with small arrays, and you’ll crush this in under 10 minutes. Now go practice—you’ve got this!

? Final Notes

• Practice Variations: Left rotation, negative k, large k.
• Whiteboard Tip: Sketch the array before/after rotation to visualize.
• Time Yourself: Aim for <15 minutes from problem statement to working code.

This framework is battle-tested—use it, and you’ll solve Rotate Array confidently in any interview. ?