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)

0 thoughts on “Rotate Array”

  1. Pingback: 100 Days Leetcode Challenge – Passion of Programming

Leave a Comment

Your email address will not be published. Required fields are marked *