This post is based on the HackerRank Interview Preparation Kit Arrays: Left Rotation question. HackerRank provides programming challenges that can be solved in the web browser in a variety of programming languages, and give real-time feedback on your solution’s success.
HackerRank Problem – Array Left Rotation
A left rotation operation on an array shifts each of the array’s elements 1 unit to the left. For example, if 2 left rotations are performed on array [1,2,3,4,5], then the array would become [3,4,5,1,2]. Note that the lowest index item moves to the highest index in a rotation. This is called a circular array.
Given an array a of n integers and a number, d, perform d 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.
rotLeft has the following parameter(s):
- int a[n]: the array to rotate
- int d: the number of rotations
Returns
- int a'[n]: the rotated array
Input Format
The first line contains two space-separated integers n and d, the size of a and the number of left rotations.
The second line contains n space-separated integers, each an a[i].
Constraints
- 1 <=
n<= 10^5 - 1 <=
d<=n - 1 <=
a[i]<= 10^6
HackerRank Example
Sample Input
5 4 1 2 3 4 5
Sample Output
5 1 2 3 4
Explanation
When we perform d = 4 left rotations, the array undergoes the following sequence of changes:
[1,2,3,4,5] => [2,3,4,5,1] => [3,4,5,1,2] => [4,5,1,2,3] => [5,1,2,3,4]
Method to Complete
class Result
{
/*
* Complete the 'rotLeft' function below.
*
* The function is expected to return an INTEGER_ARRAY.
* The function accepts following parameters:
* 1. INTEGER_ARRAY a
* 2. INTEGER d
*/
public static List<int> rotLeft(List<int> a, int d)
{
}
}
Exploring the HackerRank Constraints
Constraint 1
The first constraint is 1 <= n <= 10^5. This means that the number of elements in the array can be up to 100,000.
It is important to understand that iterating over this many elements on a modern computer is very fast. If the number of elements in the collection was large, then we would need to be very careful about how many times we iterated over the collection. For this reason, we will not need to consider a space-time complexity tradeoff.
Constraint 2
The second constraint is 1 <= d <= n. This means that the number of rotations can be 1 through to 100,000.
It is important to understand that if d == n that no rotation is required.
Constraint 3
The third constraint is 1 <= a[i] <= 10^6. This means that any element in the array can have a value between 1 and 1,000,000.
The worst-case memory complexity for this problem would be an array of 100,000 elements, with each element being the value 1,000,000. This is not a worryingly large amount of memory. This means that we do not have to be overly concerned about creating a solution that makes copies of data. If the memory constraints were large, we may need to consider performing in-place rotations, which would potentially produce a more complex solution.
HackerRank Array Left Rotation Solution 1
The first solution is a procedural approach, erring on brute force. It focuses on a single iteration over the collection and consumes additional memory in the form of two new collections.
public static List<int> rotLeft(List<int> a, int d)
{
var numberOfElements = a.Count();
if (d == numberOfElements)
{
return a;
}
var newEndElements = new List<int>();
var newStartElements = new List<int>();
for(int i = 0; i < numberOfElements; i++)
{
if (i < d)
{
newEndElements.Add(a[i]);
}
else
{
newStartElements.Add(a[i]);
}
}
return newStartElements.Concat(newEndElements).ToList();
}
The first if statement case supports early termination. If the number of requested rotations is equal to the array’s length, then we do not need to perform any rotations and can return early using the original collection.
We then create two new collections. One will hold the elements that are currently at the start of the provided collection a, and need to be returned from the end of the collection. The second collection will then be used to hold the rest of the collection.
To complete the method, we return the collection of new starting elements concatenated with the collection of previously starting elements at the end.
This approach can be adjusted to consume less memory by removing the newStartElements collection, and simply removing each newEndElement as we iterate over it. However, it modifies the collection that we have been provided. By making this tradeoff, we only need to iterate over the first d elements of the collection.
public static List<int> rotLeft(List<int> a, int d)
{
if (d == a.Count())
{
return a;
}
var newEndElements = new List<int>();
for (int i = 0; i < d; i ++){
newEndElements.Add(a[0]);
a.RemoveAt(0);
}
return a.Concat(newEndElements).ToList();
}
HackerRank Array Left Rotation Solution 2
This solution uses .Net syntactic sugar for System.Range.
public static List<int> rotLeft(List<int> a, int d)
{
if (d == a.Count())
{
return a;
}
return a[d..]
.Concat(a[..d])
.ToList();
}
A collection supporting Range semantics can be accessed with the .. operator.
In this example, a[d..] uses the range operator to create a new List<int> containing elements starting at index d, to the end of the collection.
In the simplest case, if d = 1, the new first element will start at position 2 of the list, which is index 1. The range operator works on a zero-based index.
a[..d] will provide a Range that returns a List<int> containing elements ending at the index d. This is non-inclusive, so if d = 1, we will only take the element at index 0.
Sloth Summary
There we have it! A few different solutions to complete the HackerRank Arrays: Left Rotation challenge.
It’s always important to take a look at the given constraints. Generally as the questions become harder, these constraints can be a critical part of passing all test cases, as they will typically indicate the type of solution that is required.
Happy Code Slothing! 🦥
