LeetCode 189: Rotate Array Solution in Python Explained

Problem Statement

In LeetCode 189, you’re given:

• nums: an integer array.
• k: an integer representing the number of steps to rotate right.

Your task is to rotate nums to the right by k steps in-place, modifying the original array without using extra space beyond O(1). Rotating right by k means moving the last k elements to the front, shifting the rest left (e.g., [1,2,3,4,5,6,7] with k=3 becomes [5,6,7,1,2,3,4]). This differs from stock trading like LeetCode 188: Best Time to Buy and Sell Stock IV, focusing on array manipulation.

Constraints

• 1 <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1
• 0 <= k <= 10^5
• O(1) extra space required.

Example

Let’s see some cases:

Copy codeInput: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation: Rotate right 3 steps: [1,2,3,4,5,6,7] → [5,6,7,1,2,3,4].

Copy codeInput: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation: Rotate right 2 steps: [-1,-100,3,99] → [3,99,-1,-100].

Copy codeInput: nums = [1,2], k = 3
Output: [2,1]
Explanation: k=3 mod 2=1, rotate right 1 step: [1,2] → [2,1].

These examples show we’re rotating in-place.

Understanding the Problem

How do you solve LeetCode 189: Rotate Array in Python? Take nums = [1,2,3,4,5,6,7], k = 3. We need to shift the array right by 3 steps in-place, resulting in [5,6,7,1,2,3,4]. Using an extra array (e.g., copy last 3, shift rest, append) is O(n) space, violating the constraint. We need an O(1) space solution, possibly by reversing parts of the array or cycling elements. This isn’t a DNA sequence task like LeetCode 187: Repeated DNA Sequences; it’s about in-place array rotation. We’ll use: 1. Reverse Three Parts: O(n) time, O(1) space—our best solution. 2. Cyclic Replacements: O(n) time, O(1) space—an alternative.

Let’s dive into the best solution.

Best Solution: Reverse Three Parts Approach

Explanation

Reverse Three Parts rotates the array in-place by:

• Normalizing k to k % n (e.g., k=3 for n=7 is same as k=10).
• Reverse the entire array.
• Reverse the first k elements.
• Reverse the remaining n-k elements.

This achieves O(n) time (three reversals), O(1) space (few variables), and simplicity by leveraging the reversal property: reversing all, then reversing parts, restores word order correctly.

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

• Reverse all: [7,6,5,4,3,2,1].
• Reverse 0 to k-1: [5,6,7,4,3,2,1].
• Reverse k to n-1: [5,6,7,1,2,3,4].

Step-by-Step Example

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

Goal: Modify nums to [5,6,7,1,2,3,4].

• Step 1: Normalize k.
• n = 7, k = 3 % 7 = 3.
• Step 2: Reverse entire array.
• [1,2,3,4,5,6,7] → [7,6,5,4,3,2,1].
• Step 3: Reverse first k elements (0 to 2).
• [7,6,5,4,3,2,1] → [5,6,7,4,3,2,1].
• Step 4: Reverse remaining n-k elements (3 to 6).
• [5,6,7,4,3,2,1] → [5,6,7,1,2,3,4].
• Finish: nums = [5,6,7,1,2,3,4].

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

Goal: Modify nums to [3,99,-1,-100].

• Step 1: n = 4, k = 2 % 4 = 2.
• Step 2: Reverse all.
• [-1,-100,3,99] → [99,3,-100,-1].
• Step 3: Reverse 0 to 1.
• [99,3,-100,-1] → [3,99,-100,-1].
• Step 4: Reverse 2 to 3.
• [3,99,-100,-1] → [3,99,-1,-100].
• Finish: nums = [3,99,-1,-100].

How the Code Works (Reverse Three Parts) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef rotate(nums: list[int], k: int) -> None:
    # Line 1: Reverse helper function
    def reverse(arr: list[int], start: int, end: int) -> None:
        # Reverse subarray (e.g., [1,2,3] → [3,2,1])
        while start < end:
            arr[start], arr[end] = arr[end], arr[start]
            # Swap elements (e.g., 1↔7)
            start += 1
            end -= 1

    # Line 2: Normalize k
    n = len(nums)
    # Array length (e.g., 7)
    k = k % n
    # Effective rotation (e.g., 3 % 7 = 3)
    if k == 0:
        # No rotation needed (e.g., k=7 for n=7)
        return

    # Line 3: Reverse entire array
    reverse(nums, 0, n - 1)
    # Full reversal (e.g., [1,2,3,4,5,6,7] → [7,6,5,4,3,2,1])

    # Line 4: Reverse first k elements
    reverse(nums, 0, k - 1)
    # First part (e.g., [7,6,5,4,3,2,1] → [5,6,7,4,3,2,1])

    # Line 5: Reverse remaining n-k elements
    reverse(nums, k, n - 1)
    # Last part (e.g., [5,6,7,4,3,2,1] → [5,6,7,1,2,3,4])

    # No return, nums modified in-place

This detailed breakdown clarifies how reversing three parts efficiently rotates the array in-place.

Alternative: Cyclic Replacements Approach

Explanation

Cyclic Replacements rotates by moving elements to their final positions:

• Compute effective k = k % n.
• Use a cycle-following approach:
• Start at 0, move element to position (i + k) % n.
• Continue until cycle completes or all elements visited.
• Track visited count to handle all elements.

It’s a practical alternative, O(n) time (each element moved once), O(1) space (few variables), but more complex due to cycle management.

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

• Start at 0: 1→3, 4→6, 7→2, 3→5, 6→1, 2→4, 5→0.
• Result: [5,6,7,1,2,3,4].

Step-by-Step Example (Alternative)

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

• Step 1: k = 3 % 7 = 3, count = 0.
• Step 2: Follow cycle from 0.
• 0(1) → 3: temp=4, nums[3]=1, count=1.
• 3(1) → 6: nums[6]=temp=4, count=2.
• 6(4) → 2: temp=3, nums[2]=4, count=3.
• 2(4) → 5: nums[5]=3, count=4.
• 5(3) → 1: temp=2, nums[1]=3, count=5.
• 1(3) → 4: nums[4]=2, count=6.
• 4(2) → 0: nums[0]=5, count=7.
• Step 3: All visited (count=n), stop.
• Finish: nums = [5,6,7,1,2,3,4].

How the Code Works (Cyclic)

Copy codedef rotateCyclic(nums: list[int], k: int) -> None:
    n = len(nums)
    k = k % n
    if k == 0:
        return
    count = 0
    start = 0
    while count < n:
        curr = start
        prev = nums[start]
        while True:
            next_idx = (curr + k) % n
            temp = nums[next_idx]
            nums[next_idx] = prev
            prev = temp
            curr = next_idx
            count += 1
            if curr == start:
                break
        start += 1

Complexity

• Reverse Three Parts:
• Time: O(n) – three reversals.
• Space: O(1) – constant space.
• Cyclic Replacements:
• Time: O(n) – each element moved once.
• Space: O(1) – constant space.

Efficiency Notes

Reverse Three Parts is the best solution with O(n) time and O(1) space, offering simplicity and predictability—Cyclic Replacements matches complexity but is more complex due to cycle tracking, making it less intuitive despite equal efficiency.

Key Insights

• Reverse: Three-step flip.
• Cyclic: Position chasing.
• In-Place: O(1) space.

Additional Example

For nums = [1,2,3], k=1:

• Goal: [3,1,2].
• Reverse: [3,2,1] → [3,2,1] → [3,1,2].

Edge Cases

• k=0: No change.
• Single Element: No change.
• k > n: Modulo handles.

Both solutions handle these well.

Final Thoughts

LeetCode 189: Rotate Array in Python is a clever in-place challenge. The Reverse Three Parts solution excels with its efficiency and clarity, while Cyclic Replacements offers an alternative approach. Want more? Try LeetCode 186: Reverse Words in a String II for in-place strings or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 189 on LeetCode with [1,2,3,4,5,6,7], k=3, aiming for [5,6,7,1,2,3,4]—test your skills now!