Rotate Array

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

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]

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 <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1
• 0 <= k <= 10^5

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?

## Rotate Array

This problem requires rotating an array to the right by `k` steps. Let's explore different approaches to solve it.

### Naive Approach (Brute Force)

The most straightforward approach is to rotate the array one step at a time, repeating this `k` times. This involves moving the last element to the beginning and shifting all other elements to the right.

```python
def rotate_naive(nums, k):
    n = len(nums)
    for _ in range(k):
        temp = nums[n - 1]
        for i in range(n - 1, 0, -1):
            nums[i] = nums[i - 1]
        nums[0] = temp

Optimal Approach (Reversal Algorithm)

A more efficient approach involves reversing array segments. The steps are:

1. Reverse the entire array.
2. Reverse the first k elements.
3. Reverse the remaining n - k elements.

def rotate_optimal(nums, k):
    n = len(nums)
    k %= n  # Handle cases where k > n

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

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

Example

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

# Initial array: [1, 2, 3, 4, 5, 6, 7]
# Reverse the entire array: [7, 6, 5, 4, 3, 2, 1]
# Reverse the first k elements: [5, 6, 7, 4, 3, 2, 1]
# Reverse the remaining n-k elements: [5, 6, 7, 1, 2, 3, 4]

Big(O) Run-time Analysis (Optimal Approach)

The optimal approach consists of three reversal operations. Each reversal iterates through a portion of the array once.

• Reversing the entire array: O(n)
• Reversing the first k elements: O(k)
• Reversing the remaining n - k elements: O(n - k)

The overall time complexity is O(n + k + (n - k)) which simplifies to O(2n), and further to O(n), where n is the length of the array.

Big(O) Space Usage Analysis (Optimal Approach)

The reversal algorithm operates in-place, meaning it does not require any additional data structures that scale with the input size. It only uses a constant amount of extra space for temporary variables during the reversal process.

Thus, the space complexity is O(1).

Edge Cases and Considerations

• Empty Array: If the input array is empty, no rotation is needed.
• k = 0: If k is zero, the array remains unchanged.
• k > n: If k is greater than the length of the array, we use k % n to ensure the rotation is within the bounds of the array.
• Negative k: The problem statement specifies that k is non-negative, but if negative values were allowed, we could normalize k by adding n until it becomes non-negative and then take k % n.

def rotate(nums, k):
    n = len(nums)
    if n == 0:
        return  # No rotation needed for empty array

    k %= n  # Normalize k to be within the range of array length

    if k == 0:
        return  # No rotation needed if k is 0

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

    reverse(nums, 0, n - 1)  # Reverse entire array
    reverse(nums, 0, k - 1)  # Reverse first k elements
    reverse(nums, k, n - 1)  # Reverse remaining n-k elements