# Problem

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 <= 10<sup>5</sup>`

`-2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1`

`0 <= k <= 10<sup>5</sup>`

# Solution

**Intuition**

If I have [1,2,3,4,5,6,7] and k=3 then I need to shift 3 elements cyclically.

With that, my final result will be [5,6,7,1,2,3,4]

Initially, I was solving it by traditional approach like single shift, which took me O(kN) time.

To think differently, I have tried to understand the approach in a bottom-up approach: solution to the problem.

If I see [5,6,7] that is the k partition, [1,2,3,4] that is shifted element partition, if I reverse [1,2,3,4] I will get [4,3,2,1].

If I look whole combined array at this step, then it will be [7,6,5,4,3,2,1] which is, yes, you are right, the reversal of the original array.

So here I decode it like this:

Go from [1,2,3,4,5,6,7] to [7,6,5,4,3,2,1]: Reverse the whole array.

Now I need to reverse [7,6,5] which is the last k element of the array, it will seem as if we rotate them when this subpartition has been swapped. So we will have: [5,6,7,4,3,2,1]

Now look carefully you will observe [5,6,7] are at their place. You only make [4,3,2,1] right.

Again you are correct, reverse this sub-partition: [4,3,2,1] -> [1,2,3,4]

Voila, we have [5,6,7,1,2,3,4], our exact answer.

**Approach**

Reverse the whole array.

Reverse up to k.

Reverse from k+1 to the last index.

**Complexity**

Time complexity: O(N)

Space complexity: O(1)

**Code**

### Java

```
class Solution {
public void reverse(int[] nums, int start, int end)
{
while(start<end)
{
nums[end] = nums[start]+nums[end]-(nums[start]=nums[end]);
start++;
end--;
}
}
public void rotate(int[] nums, int k) {
k=k%nums.length;
reverse(nums, 0, nums.length-1);
reverse(nums, 0, k-1);
reverse(nums, k, nums.length-1);
}
}
```

### Python

```
class Solution:
def reverse(self, nums: List[int], start: int, end: int) -> None:
while start<end:
nums[start], nums[end] = nums[end], nums[start]
start+=1
end-=1
def rotate(self, nums: List[int], k: int) -> None:
k=k%len(nums)
self.reverse(nums, 0, len(nums)-1)
self.reverse(nums, 0, k-1)
self.reverse(nums, k, len(nums)-1)
```

I have also posted the same solution on Leetcode: https://leetcode.com/problems/rotate-array/solutions/4376260/fully-explained-readable-and-100-efficient-java-solution/