How to rotate Array in Java with given n number without extra space?

Rotate Array LeetCode solution in Java with explanation | Rotate array without extra array

Problem Description :

Given an array, 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]

We have to rotate array based on given k number. We have multiple solution for this problem.

1. Using Temporary array.
2. Recursively rotate array one by one.
3. Reverse array and swap the elements

Here, we will seen 3rd solution.

Solution 1 : Rotate array in java without extra space

import java.util.Scanner;

public class RotateArray {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
       
        System.out.println("enter array size");
        int size = sc.nextInt();

        int[] array = new int[size];
        System.out.println("Enter values");
       
        for (int i = 0; i < array.length; i++) {
            array[i] = sc.nextInt();
        }
       
        System.out.println("enter k");
        int k = sc.nextInt();
    
        // Check if k is not greater than array size
        if (k > array.length) {
            k = k%array.length;
        }
       
        if (array.length > 1) {
           
            // Reverse an array
            for (int i = 0; i < array.length / 2; i++) {
                int temp = array[i];
                array[i] = array[array.length - 1 - i];
                array[array.length - 1 - i] = temp;
            }
           
            // Swaping elements from 0 to k 
            int middle = k-1;
            for (int i = 0; i < k/2; i++) {
                int temp = array[i];
                array[i] = array[middle];
                array[middle] = temp;
                middle--;
            }
           
            // Swaping elements from k to array length
            int last = array.length-1;
            for (int i = 0; i < (array.length-k)/2; i++) {
                int temp = array[i+k];
                array[i+k] = array[last];
                array[last] = temp;
                last--;
            }
           
        }

        // Print rotate array
        for (int i = 0; i <array.length; i++) {
            System.out.println(array[i]);
        }
    }
}

Solution explanation :

• First, reverse an array. 
• array = [1, 2, 3, 4, 5, 6, 7], reversed array = [7, 6, 5, 4, 3, 2, 1], k = 3
  
• Now, swap the array from 0 to k-1.
• swap 0 and k-1 value. swap 0th index value with 2nd index value
• [5, 6, 7, 4, 3, 2, 1]
• Now, swap values from kth index to array length
• swap 3rd index to 6th index
• [5, 6, 7, 1, 3, 2, 4]
• swap 4th index to 5th index
• [5, 6, 7, 1, 2, 3, 4]
• We got solution.

We can also reduce line of code using same approach. lets see code.

Solution 2 : Rotate array in java without extra space

public void rotate(int[] array, int k) {
    k %= array.length;
    reverse(array, 0, array.length - 1);
    reverse(array, 0, k - 1);
    reverse(array, k, array.length - 1);
}

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

Other articles you may like :

• Simple Text Editor HackerRank Solution in Java with Explanation