Rotate Array #leetcode189 # Problem Statement:

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 step 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 step to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Constraints:
- \(1 \leq \text{nums.length} \leq 10^5\)
- \(-2^{31} \leq \text{nums[i]} \leq 2^{31} - 1\)
- \(0 \leq k \leq 10^5\)

### Solution Approach

To rotate the array to the right by k steps:
1. Normalize k: If k is greater than the length of the array, we take k % n (where n is the length of the array) because rotating by n or more steps brings us back to a previous state.
2. Reverse the Entire Array: This sets up the rotation by moving elements from the end to the beginning.
3. Reverse the First k Elements: This places the k elements that were moved to the start in their correct positions.
4. Reverse the Remaining Elements: This places the remaining elements in their correct positions.

### Code Implementation

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k %= nums.size(); // Normalize k
        reverse(nums.begin(), nums.end()); 
        reverse(nums.begin(), nums.begin() + k); // Step 2: Reverse the first k elements
        reverse(nums.begin() + k, nums.end()); 
    }
};

### Step-by-Step Iteration with Explanation

Let's walk through the process for the input nums = [1,2,3,4,5,6,7] and k = 3.

1. Normalize k:

   k %= nums.size(); // k = 3 % 7 = 3
   

2. Reverse the Entire Array:

   reverse(nums.begin(), nums.end()); // nums becomes [7,6,5,4,3,2,1]
   

3. Reverse the First k Elements:

   reverse(nums.begin(), nums.begin() + k); // nums becomes [5,6,7,4,3,2,1]
   

4. Reverse the Remaining Elements:

   reverse(nums.begin() + k, nums.end()); // nums becomes [5,6,7,1,2,3,4]
   

### Time Complexity

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

Total time complexity is O(n) because each element is reversed exactly once.

### Space Complexity

The space complexity is O(1) because the algorithm only uses a constant amount of extra space regardless of the input size.

This approach efficiently rotates the array using a three-step reversal process, making it both time and space efficient.