Learn to Rotate an Array to Right in JAVA: A LeetCode Interview Question

Introduction

Array rotation is a common problem that frequently appears in coding interviews, especially in DSA (Data Structures and Algorithms) preparation. This blog post will guide you through an efficient solution for rotating an array to the right by k steps, a typical LeetCode challenge. Whether you're preparing for an upcoming interview or brushing up on your coding skills, this article will equip you with the necessary insights and a clear Java solution.

Problem Statement

Given an array of integers and a number k, your task is to rotate the array to the right by k steps. For instance, if you have the array [1, 2, 3, 4, 5, 6, 7, 8] and k = 2, the output should be [7, 8, 1, 2, 3, 4, 5, 6].

Approach

The most efficient way to solve this problem is by using the reversal algorithm, which operates in linear time complexity, O(n), and requires O(1) additional space. Here’s how it works:

1. Reverse the entire array.
2. Reverse the first k elements.
3. Reverse the remaining elements.

This three-step process allows us to achieve the desired rotation without using extra space for a new array.

Java Solution

Here’s a Java implementation of the solution:

import java.util.Arrays;

public class RotateArrayToRightByKSteps {

public static void main(String[] args) {

int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};

int key = 2;

System.out.println("Original Arrya: "+Arrays.toString(arr));

rotateArrayToRight(arr, key);

System.out.println("\nArray after "+key+"

                            steps rotation to the right\n"+Arrays.toString(arr));

}

private static void rotateArrayToRight(int[] arr, int key) {

if (arr.length==0 || key <=0) {

return;

}

// Adjust key if it's greater than the length of the array

key = key % arr.length;

int start = 0;

int end = arr.length-1;

//First reversing the whole array

while (start<end) {

int temp = arr[start];

arr[start] = arr[end];

arr[end] = temp;

start++;

end--;

}

//Now reverse first k steps of array

int i =0;

int j = key-1;

while (i<j) {

int temp = arr[i];

arr[i]=arr[j];

arr[j]=temp;

i++;

j--;

}

//Now reversing the remaining array

int p=key;

int q=arr.length-1;

while (p<q) {

int temp = arr[p];

arr[p] = arr[q];

arr[q] = temp;

p++;

q--;

}

}

}

Explanation of the Code

• Main Method: Initializes the array and calls the rotateArrayToRight method.
• rotateArrayToRight Method: Adjusts k, reverses the entire array, reverses the first k elements, and then reverses the rest.
• reverse Method: A helper method that reverses a portion of the array in place.

Conclusion

Understanding how to efficiently rotate an array is essential for DSA interviews and coding challenges on platforms like LeetCode. This solution not only provides clarity on the problem but also enhances your problem-solving skills. Practice this algorithm and similar problems to boost your confidence and readiness for your next interview.

Tags:

#LeetCode #DSA #Java #ArrayRotation #CodingInterview #InterviewPrep #Algorithms #DataStructures #CodingChallenges