Arrays: Left Rotation - Hacker Rank Solution

Arrays: Left Rotation - Hacker Rank Solution

Check out the resources on the page's right side to learn more about arrays. The video tutorial is by Gayle Laakmann McDowell, author of the best-selling interview book 

Cracking the Coding Interview.

A left rotation operation on an array shifts each of the array's elements  unit to the left. For example, if  left rotations are performed on array , then the array would become .

Given an array  of  integers and a number, , perform  left rotations on the array. Return the updated array to be printed as a single line of space-separated integers.

Function Description

Complete the function rotLeft in the editor below. It should return the resulting array of integers.

rotLeft has the following parameter(s):

• An array of integers .
• An integer , the number of rotations.

Input Format

The first line contains two space-separated integers  and , the size of  and the number of left rotations you must perform.
The second line contains  space-separated integers .

Constraints

Output Format

Print a single line of  space-separated integers denoting the final state of the array after performing  left rotations.

Sample Input

5 4
1 2 3 4 5

Sample Output

5 1 2 3 4

Arrays: Left Rotation - Hacker Rank Solution

To solve this challenge, we perform the following basic steps:

1. Create a new -element (where  is the length of ) array named  to hold the rotated items.
2. Copy the contents of  over to the new array in two parts:
   • The -element contiguous segment from  to  must be copied over to the contiguous segment starting at .
   • The -element contiguous segment from  to  must be copied over to the contiguous segment starting at .
3. Reassign the reference to  so that it points to  instead.

This is implemented by the following Java code:

public static int[] rotateArray(int[] arr, int d){
    // Because the constraints state d < n, we need not concern ourselves with shifting > n units.
    int n = arr.length;

    // Create new array for rotated elements:
    int[] rotated = new int[n]; 

    // Copy segments of shifted elements to rotated array:
    System.arraycopy(arr, d, rotated, 0, n - d);
    System.arraycopy(arr, 0, rotated, n - d, d);

    return rotated;
}

In Python, we can implement the function in one line with array slicing:

def solve(a, d):
 return(a[d:]+a[:d])

We can also create a more general function that does account for  cases by adding a modulo division.

Each time the rotation equals the length of the array, the array appears unchanged. Thus, the final rotation for d is same as the rotation for  and we use that for our slice index. Here it is, implemented in python:

# Complete the solve function below.
def solve(a, d):
 i = d%len(a)
 return(a[i:]+a[:i])

Problem Tester's code:

Java

import java.util.*;
import java.lang.System;

public class Solution {
    
    public static int[] rotateArray(int[] arr, int d){
        // Because the constraints state d < n, we need not concern ourselves with shifting > n units.
        int n = arr.length;
        
        // Create new array for rotated elements:
        int[] rotated = new int[n]; 
        
        // Copy segments of shifted elements to rotated array:
        System.arraycopy(arr, d, rotated, 0, n - d);
        System.arraycopy(arr, 0, rotated, n - d, d);

        return rotated;
    }
    
    public static void main(String[] args) {
        
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int d = scanner.nextInt();
        int[] numbers = new int[n];
        
        // Fill initial array:
        for(int i = 0; i < n; i++){
            numbers[i] = scanner.nextInt();
        }
        scanner.close();
        
        // Rotate array by d elements:
        numbers = rotateArray(numbers, d);
        
        // Print array's elements as a single line of space-separated values:
        for(int i : numbers) {
            System.out.print(i + " ");
        }
        System.out.println();
    } 
        
}