Rotate Array

• Difficulty: Medium
• Topics: Array, Math, Two Pointers
• Link: https://leetcode.com/problems/rotate-array/

Problem Description

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation: 
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Constraints:

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

Follow up:

• Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
• Could you do it in-place with O(1) extra space?

Solution

1. Problem Deconstruction

Technical Definition:
Given an array nums of length n and a non-negative integer k, perform a right rotation such that each element is shifted right by k positions. Elements exiting the right end re-enter from the left end. Formally, the element originally at index i (0-based) moves to index (i + k) mod n in the rotated array. The operation must be performed in-place if possible, with optimal time complexity O(n) and space complexity O(1).

Beginner-Friendly Explanation:
Imagine you have a row of numbered boxes. You need to shift each number to the right by k steps. If a number reaches the end of the row, it wraps around to the start. After doing this, what’s the new order? For example, if you have boxes [1, 2, 3] and k=1, moving right once gives [3, 1, 2].

Mathematical Formulation:
Let nums be an array of length n. Define a rotation function R such that for each index i in the original array, the new value at index j in the rotated array satisfies:

$$\text{nums}_{\text{new}}[j] = \text{nums}[(j - k) \mod n]$$

However, to avoid negative indices, use:

$$\text{nums}_{\text{new}}[j] = \text{nums}[(n + j - k) \mod n]$$

Alternatively, by tracing the displacement:

$$\text{nums}[(i + k) \mod n] = \text{nums}[i] \quad \text{for all } i$$

Constraint Analysis:

• 1 <= nums.length <= 10^5:
  • Limitation: Rules out O(n²) solutions (e.g., brute-force rotation step-by-step).
  • Edge Case: Large n requires efficient algorithms. Arrays fit in memory (∼400 KB for 10⁵ integers), but cache-awareness is needed.
• -2^31 <= nums[i] <= 2^31 - 1:
  • Limitation: Values are large but irrelevant to rotation logic. No sign-handling issues.
  • Edge Case: Extreme values don’t affect indexing or swaps.
• 0 <= k <= 10^5:
  • Limitation: k may exceed n, making k mod n essential to avoid redundant rotations.
  • Edge Case: k = 0 or k = n results in no change. k > n must be reduced to k mod n.

---

2. Intuition Scaffolding

Analogies:

1. Real-World Metaphor (Conveyor Belt):
   Items on a conveyor belt move right. Items falling off are placed back at the start. After k steps, the belt’s state is the rotated array.

2. Gaming Analogy (Circular Puzzle):
   A circular track of tokens is shifted right by k positions. Tokens exiting the track re-enter from the left. This mimics rotation in puzzle games like “Ring Fit.”

3. Math Analogy (Modular Arithmetic):
   Rotation is a cyclic permutation. Each element’s index is transformed under the cyclic group ℤ/nℤ via addition of k mod n.

Common Pitfalls:

1. Ignoring k > n: Rotating by k = n + 5 is equivalent to k = 5. Not reducing k wastes computation.
2. Brute-Force Inefficiency: Shifting one step at a time leads to O(kn) time, which is O(10¹⁰) worst-case.
3. Extra Space Overuse: Using an auxiliary array violates O(1) space if not required.
4. Index Calculation Errors: Incorrect modulo arithmetic leads to out-of-bounds access.
5. In-Place Swap Mistakes: Cyclic replacements may incomplete cycles if n and k have common divisors.

---

3. Approach Encyclopedia

Approach 1: Brute Force (Step-by-Step Rotation)

• Logic: For each of k steps, shift all elements right by one (save last element, move others, insert saved at front).
• Complexity: Time O(k ⋅ n), Space O(1).
• Visualization:

  Initial: [1,2,3,4,5]  
  Step 1: [5,1,2,3,4]  
  Step 2: [4,5,1,2,3]  
  ...  
  

Approach 2: Auxiliary Array

• Logic: Create a new array. For each index i, place nums[i] at (i + k) mod n in the new array. Copy back to original.
• Complexity: Time O(n), Space O(n).
• Visualization:

  nums = [1,2,3,4], k=2 → new_array: 
    i=0: (0+2)%4=2 → new[2]=1
    i=1: (1+2)%4=3 → new[3]=2
    i=2: (2+2)%4=0 → new[0]=3
    i=3: (3+2)%4=1 → new[1]=4
  Result: [3,4,1,2]
  

Approach 3: Reverse Method (Optimal In-Place)

• Logic:
  1. Reduce k to k mod n.
  2. Reverse the entire array.
  3. Reverse the first k elements.
  4. Reverse the remaining n - k elements.
• Complexity: Time O(n), Space O(1).
• Derivation:
  • Reversal swaps elements symmetrically. Full reversal places the last k elements at the front but inverted. Reversing subarrays corrects the order.
  • Mathematically:
    Let R(arr, i, j) reverse subarray arr[i..j].
    Then: R(R(nums, 0, n-1), 0, k-1) and R(nums, k, n-1) yields rotation.
• Visualization:

  nums = [1,2,3,4,5,6,7], k=3
  Reverse full: [7,6,5,4,3,2,1]
  Reverse [0..2]: [5,6,7,4,3,2,1]
  Reverse [3..6]: [5,6,7,1,2,3,4]
  

Approach 4: Cyclic Replacements

• Logic: Move elements in cycles. Start at index 0, save nums[0]. Move element from (0 - k) mod n to 0, then to next index in cycle. Repeat for all cycles.
• Complexity: Time O(n), Space O(1).
• Visualization:

  nums = [1,2,3,4], k=2
  Cycle 1: 
    temp = nums[0]=1
    Move nums[(0-2)%4=2] to 0: [3,2,3,4]
    Move temp to 2: [3,2,1,4]
  Cycle 2: 
    Start at index 1 (next unused)...
  

---

4. Code Deep Dive

Optimal Solution (Reverse Method):

def rotate(nums, k):
    n = len(nums)
    k = k % n  # Reduce k to effective rotation
    # Reverse entire array
    reverse(nums, 0, n-1)
    # Reverse first k elements
    reverse(nums, 0, k-1)
    # Reverse remaining n-k elements
    reverse(nums, k, n-1)

def reverse(nums, start, end):
    while start < end:
        nums[start], nums[end] = nums[end], nums[start]
        start += 1
        end -= 1

Line-by-Line Analysis:

• k = k % n: Handles k > n by reducing to equivalent rotation.
• reverse(nums, 0, n-1): Flips the entire array, bringing尾部 elements to the front but inverted.
• reverse(nums, 0, k-1): Corrects the order of the first k elements.
• reverse(nums, k, n-1): Corrects the order of the remaining elements.

Edge Case Handling:

• k=0: k % n = 0, so no reversal occurs.
• n=1: All reversals are no-ops.
• k=n: k % n = 0, so no change.

---

5. Complexity War Room

Hardware-Aware Analysis:

• For n=10^5, the array uses ∼400 KB (4 bytes/int). Modern L3 caches are ∼8 MB, so the array fits, ensuring efficient in-place operations.

Industry Comparison Table:

Approach	Time Complexity	Space Complexity	Readability	Interview Viability
Brute Force	O(k⋅n)	O(1)	High	❌ Fails constraints
Auxiliary Array	O(n)	O(n)	High	✅ Acceptable
Reverse Method	O(n)	O(1)	Medium	✅ Optimal
Cyclic Replacements	O(n)	O(1)	Low	✅ Advanced

---

6. Pro Mode Extras

Variants:

• Left Rotation: Reverse first k elements, reverse remaining, then reverse entire array.
• Multiple Rotations: Precompute net k as (k1 + k2 + ...) mod n.
• LeetCode 123 (Multiple Transactions): Not directly related, but similar array manipulation skills.

Interview Cheat Sheet:

• First Step: Always reduce k via k % n.
• Mention Trade-offs: Auxiliary array is simpler but uses O(n) space. Reverse method is in-place but slightly harder to explain.
• Test Cases:
  • k=0, k=n, k>n
  • n=1, n=2
  • Negative numbers (value无关)