# Explained and Solved: Rotate Array: DSA Problem

# Problem

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

**Example 1:**

```java
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:**

```java
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\] -&gt; \[1,2,3,4\]
    
* Voila, we have \[5,6,7,1,2,3,4\], our exact answer.
    

## **Approach**

1. Reverse the whole array.
    
2. Reverse up to k.
    
3. Reverse from k+1 to the last index.
    

## **Complexity**

* Time complexity: O(N)
    
* Space complexity: O(1)
    

## **Code**

### Java

```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

```java
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/](https://leetcode.com/problems/rotate-array/solutions/4376260/fully-explained-readable-and-100-efficient-java-solution/)