Rotate Array

Hi Geeks! Welcome to 100 Days of Leetcode Challenge.

DAY 6

In this article, I’m going to explain about how to rotate an array efficiently.

This is nothing but just playing with Array.

Here is our given problem,

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

Example 1:

Input: [1,2,3,4,5,6,7] and 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: [-1,-100,3,99] and 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]

Note:

  • Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
  • Could you do it in-place with O(1) extra space?

How To Approach this problem?

  1. First reverse the whole array.
  2. Second reverse the array from 0 to k-1 elements.
  3. Third reverse the array from k to end of array elements.

Solution

class Solution {
    public void rotate(int[] nums, int k) {
        
        /*if k is bigger than the array length, to order k inside the 
        length of array, we use this order condition
        */
        k = k % nums.length;
        
        //First reverse the whole arrray
        reverse(nums,0,nums.length-1);
        
        //Second reverse the array from 0 to k-1 elements
        reverse(nums,0,k-1);
        
        //Third reverse the array from k to nums.length-1
        reverse(nums,k,nums.length-1);

    }
    
    public void reverse(int[] nums, int start, int end)
    {
        while(start < end)
        {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

Time complexity: O(n)

Space Complexity: O(1)

One thought on “Rotate Array

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s