Hello guys, welcome to this post with another array-based coding problem. In the last article, we've learned about finding missing numbers in the array with duplicates and today we'll solve the problem of

##

Suppose, you were given an integer array [1, 2, 3, 4, 5, 6, 7, 8] and asked to rotate left by 4 and then rotate right by 4. Write a program to accomplish array rotation by left and right.

input: [1, 2, 3, 4, 5, 6, 7, 8]

first output: [5, 6, 7, 8, 1, 2, 3, 4]

second output: [1, 2, 3, 4, 5, 6, 7, 8]

It's also very different from the String rotation problem we have seen earlier, where we had to check if two strings are the rotation of each other or not. Here

##

The solution to this problem is simple, but you need

If we rotate this to left by 1 then every element will move towards the start of the array (index zero) by 1 place and in this course the first element, 10 will be moved from the first index to the last index. The rotate array will now look like [20, 30, 10].

Similarly,

For example, if take [20, 30, 10] and rotate this array to right by 1 place it will look like [10, 20, 30], which is same as the original array.

Btw, if you are not familiar with array and other essential data structure like list, binary tree, stack, queue, etc, Please refer

##

Here is the sample Java program to rotate arrays in Java. We have created two methods here rotateLeft() and rotateRight(), both method takes array and numberOfRotations as a parameter.

Even though I have added length to capture the length of input array it's optional because you can always get that from the array as well.

The rotateLeft() method loop over the array and shift each element towards the first index like towards left.

Since the first element will be lost by this, we store it into a temporary variable before start with shifting. Later we put that element at the end of the array. The same process is repeated as many times required by numberOfRoatation.

The rotateRight() method is very similar to rotateLeft() method with the only difference that here elements are moved towards the last index i.e. towards the right.

The last element is stored in a temporary variable and later put back into the first position, which completes the rotation.

Here is the complete Java program:

###

##

The time complexity of this solution is O(n*k) where n is the number of elements in the array and k is the number of rotation.

If k=n then the solution will be of O(n^2). This is because in each rotation we shift all array elements and we need to repeat rotation k times.

The space complexity of this solution is O(1) because we have not used any additional array. The space allocated for a temporary variable is not counted.

If you are not confident in calculating time and space complexity of the algorithm, I suggest you join a good data structure and algorithm course like

That's all about

Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

Data Structures in Java 9 by Heinz Kabutz

Cracking the Coding Interview - 189 Questions and Solutions

Other

**rotating an array by left or right by a given number**. For example, suppose an integer array {1, 2, 3} is given and it was asked to rate this array to the left by 3 then the result array will look like {2, 3, 1} because it was rotated twice on left. Similarly,*if you are asked to rotate the same array twice*by right then you'll get {1, 2, 3}, the same array is back. This is an interesting problem and it's quite easy to solve but I have seen many programmers struggle with this one as well. So, a little bit of practice and learning will not hurt.##
__Problem:__

Suppose, you were given an integer array [1, 2, 3, 4, 5, 6, 7, 8] and asked to rotate left by 4 and then rotate right by 4. Write a program to accomplish array rotation by left and right.input: [1, 2, 3, 4, 5, 6, 7, 8]

first output: [5, 6, 7, 8, 1, 2, 3, 4]

second output: [1, 2, 3, 4, 5, 6, 7, 8]

It's also very different from the String rotation problem we have seen earlier, where we had to check if two strings are the rotation of each other or not. Here

*we are not checking if two arrays are the rotation of each other,*but we need to rotate the array itself.##
__Solution:__

The solution to this problem is simple, but you need **what is the meaning of rotating an array to left and right**. For that sake let's take an example of an integer array with three elements like [10, 20, 30].If we rotate this to left by 1 then every element will move towards the start of the array (index zero) by 1 place and in this course the first element, 10 will be moved from the first index to the last index. The rotate array will now look like [20, 30, 10].

Similarly,

**to rotate an array by right, we need to shift all elements towards the end of the array**, which means the last element will end up with the first position.For example, if take [20, 30, 10] and rotate this array to right by 1 place it will look like [10, 20, 30], which is same as the original array.

Btw, if you are not familiar with array and other essential data structure like list, binary tree, stack, queue, etc, Please refer

**Data Structures and Algorithms: Deep Dive Using Java**, an excellent course to master essential data structure.##
__Code:__

Here is the sample Java program to rotate arrays in Java. We have created two methods here rotateLeft() and rotateRight(), both method takes array and numberOfRotations as a parameter.Even though I have added length to capture the length of input array it's optional because you can always get that from the array as well.

The rotateLeft() method loop over the array and shift each element towards the first index like towards left.

Since the first element will be lost by this, we store it into a temporary variable before start with shifting. Later we put that element at the end of the array. The same process is repeated as many times required by numberOfRoatation.

The rotateRight() method is very similar to rotateLeft() method with the only difference that here elements are moved towards the last index i.e. towards the right.

The last element is stored in a temporary variable and later put back into the first position, which completes the rotation.

Here is the complete Java program:

###
__Java Program to Rotate an Array by Given Number__

__Java Program to Rotate an Array by Given Number__

package tool; import java.util.Arrays; /** * * A simple Java Program to rotate an array by left and right by given number. */ public class Hello { public static void main(String[] args) { int[] input = { 1, 2, 3, 4, 5, 6, 7, 8 }; int k = 4; System.out.println("Rotate given array " + Arrays.toString(input) + " by 4 places to the left."); int[] rotatedArray = rotateLeft(input, input.length, k); System.out.println("Rotated array: " + Arrays.toString(rotatedArray)); System.out.println("Rotate given array " + Arrays.toString(input) + " by 4 places to the right."); rotatedArray = rotateRight(rotatedArray, rotatedArray.length, k); System.out.println("Rotated array: " + Arrays.toString(rotatedArray)); } /** * Java method to rotate a given array to the left specified by numOfRotations * times * * @param input * @param length * @param numOfRotations * @return rotated array */ private static int[] rotateLeft(int[] input, int length, int numOfRotations) { for (int i = 0; i < numOfRotations; i++) { // take out the first element int temp = input[0]; for (int j = 0; j < length - 1; j++) { // shift array elements towards left by 1 place input[j] = input[j + 1]; } input[length - 1] = temp; } return input; } /** * Java method to rotate a given array to the right specified by * numOfRotations times * * @param input * @param length * @param numOfRotations * @return rotated array */ private static int[] rotateRight(int[] input, int length, int numOfRotations) { for (int i = 0; i < numOfRotations; i++) { // take out the last element int temp = input[length - 1]; for (int j = length - 1; j > 0; j--) { // shift array elements towards right by one place input[j] = input[j - 1]; } input[0] = temp; } return input; } } Output Rotate given array [1, 2, 3, 4, 5, 6, 7, 8] by 4 places to the left. Rotated array: [5, 6, 7, 8, 1, 2, 3, 4] Rotate given array [5, 6, 7, 8, 1, 2, 3, 4] by 4 places to the right. Rotated array: [1, 2, 3, 4, 5, 6, 7, 8]

##
__Analysis:__

The time complexity of this solution is O(n*k) where n is the number of elements in the array and k is the number of rotation.If k=n then the solution will be of O(n^2). This is because in each rotation we shift all array elements and we need to repeat rotation k times.

The space complexity of this solution is O(1) because we have not used any additional array. The space allocated for a temporary variable is not counted.

If you are not confident in calculating time and space complexity of the algorithm, I suggest you join a good data structure and algorithm course like

**Algorithms and Data Structures in-depth**, which covers algorithm complexity in depth.That's all about

**how to rotate a given array to left and right by given number in Java.**This is a simple but interesting array-based coding interview question which you will often find in software engineering interviews. The key to solving this problem is knowing what does array rotation means and how to rotate an array of left and right which is nothing but shifting elements towards the start and end position.**Further Learning**Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

Data Structures in Java 9 by Heinz Kabutz

Cracking the Coding Interview - 189 Questions and Solutions

Other

**Array and Data Structure Coding Problems**you may like- How to check if an array contains a particular value? (solution)
- How to remove an element from an array in Java? (solution)
- How to find one missing number in a sorted array? (solution)
- 50+ Data Structure and Algorithms Questions from Interviews (questions)
- How to find the largest and smallest number in an array without sorting? (solution)
- How to find all pairs in an array whose sum is equal to k (solution)
- Top 20 String Coding Problems from Interivews (questions)
- 10 Courses to Learn Data Structure and Algorithms for Interivews (courses)
- How to find duplicates from an unsorted array in Java? (solution)
- How to remove duplicates from an array in Java? (solution)
- How to sort an array in place in Java? (solution)
- 75 Programming Questions to Crack Any Coding Interview (list)
- Binary Search Algorithm without Recursion (algorithm)
- Prime Number Generation Algorithms - Sieve of Eratosthenes (algorithm)

**P.S.**If you are looking for some free resources, then you can also check out this list of**Free Data Structure and Algorithm courses**for programmers. The list contains a lot of useful online courses to learn algorithms from scratch for both beginners and intermediate programmers.
## No comments:

## Post a Comment