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 <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

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/

Explained and Solved: Rotate Array: DSA Problem

Comments

More from this blog

ClickHouse Deployment on Kubernetes Case Study

Spring Boot API Modernization Case Study

Analytics & Report Automation Suite Case Study

Project Orion Case Study

Learn GIT in a Day

Problem

Solution

Intuition

Approach

Complexity

Code

Java

Python

Command Palette

Comments

More from this blog

Problem

Solution

Intuition

Approach

Complexity

Code

Java

Python