Fun with array rotations

Essentially, we remove the first element of the array and we place it in the end and we shift all of the remaining elements one step to the left. This is an example of left rotation.

Similarly we can have right rotation.

Number of Rotations?

The diagrams above make it pretty clear. Whether we have left rotation or right rotation, for an array of N elements, we will have N possible rotated arrays (including self).

Time Complexity of Rotation?

Essentially what we do when we rotate an array is we remove the first element (considering we are talking about left rotation) and we shift all of the remaining elements one place to the left and finally we insert the element we removed from the first location at the very end of the array.

Since every time we have to do a rotation step, be it left or right rotation, the remaining N-1 elements have to be shifted as well to accommodate the rotation, the time complexity of this operation is O(N).

Python Magic! 🧙‍

There are many ways we can go about this. We will only showcase methods for doing left rotation and the right rotation can be achieved in similar ways. So that is left as an exercise for the reader.

This is the most basic way of implementing one step of left rotation on a given array. We simply place the first element in the very end and before we do that we shift each of the remaining elements i.e. starting index 1 (for a 0 based indexing of the array), one step to the left.

This approach actually ends up modifying the underlying array. A lot of times we are only interested in the rotated version of the array or we are interested in all of the rotations of the given array, however, we don’t really want to modify the underlying array. You can say that the given array is a read only data structure.

If you notice carefully, in order to do left rotation for the Nth time, you would need the result of the previous rotation. So, for e.g. if the original array given to us was [1,2,3,4,5] and you follow the method listed above, after one rotation this would become [2,3,4,5,1] and then we can perform one more left rotation on this and get [3,4,5,1,2] .

By following the above method, it’s really difficult to obtain the array that remains after N left rotations.

Let’s look at an interesting way using which we can achieve this.

The trick here is the modulo operation. If you notice the rotated arrays, its like the starting point for the rotated array is actually some index i in the original array. This index i can be determined by the number N which represents the number of rotations we want to perform on the given array and then return the result.

Also, as you can imagine, N can be large as well. It can be larger than the length of the original array. However, after a certain point of time, the rotated array start to repeat itself. So, for an array of size N, after N-1 rotations, the next rotated array we get is the original one.

To understand why the modulo operation here works, have a look at the diagram below which shows a few rotations.

Hope this diagram gives you enough clarity as to why we can simply do the modulo operation and we can directly get the array after N rotations have been performed on it.

Instead of writing the code like it has been shown in the code snippet earlier, we can also have a one liner for this in Python.

Now that we have a sense of rotations and we know how to play around with our array, we can finally look at some interesting problems centered around the concept of rotating an array.

Rotate Strings

Rotate String - LeetCode_We are given two strings, A and B. A shift on A consists of taking string A and moving the leftmost character to the…_leetcode.com

Let’s see what this question asks us to do.

It says that we are given two strings A and B, which may or may not be of equal lengths 😛 (did you miss this ?), and we are to return true if any specific rotation of the string A can give us the string B.

In the diagram below we consider two strings A = abcde and B = cdeab and after two rotations the string A becomes equal to the string B. So in this case we return True

A simple check that will definitely return False is if the lengths of the two strings are different. In this case no matter what rotations we do, the strings can never be equal.

A very naive way of solving this problem is to find out all the rotations and then do string matching with the string B to see if the two strings become equal. We’ll look at the solution first, then we’ll see it’s complexity analysis and finally we will look at how well it fares among other solutions on the leetcode platform.

Time Complexity: O(N²) because for every rotation we do a string matching of two strings of length N which takes O(N) and we have O(N) rotations in all.

Space Complexity: O(N) because we create a new list per rotation.

On the leetcode platform this solution performs poorly as expected.

It turns out that we can do better than this.

The idea here is to append the string A to itself and then check if the string B is a substring of this extended string A + A

Why do we do this you might ask?

Well, it turns out that if we append a given array / string to itself, the resultant array or string covers all of the rotations of the original array. Let’s have a look at the diagram below to understand how this concatenation operation effectively yields all possible rotations. The string we will consider for this diagram below is abcde and so after concatenating this string with itself we get abcdeabcde

Figure showing all possible rotations for string “abcde” covered by “abcdeabcde”

Now if the string A or any rotation of A does in fact equal the string B, then the string B would be a substring of this enlarged string 2A.

Time Complexity: O(N) because all we are doing is string matching between a string of size N and another one which is 2N.

Space Complexity: O(N) because we have to create a new string of size 2N to accommodate this enlarged version of the string A.

This algorithm is much faster than the previous one and much shorter to implement as well. It’s a one liner in Python 🙈.

I’d say that’s fast enough!

Let’s move on to another interesting problem that seems simple enough but has a bunch of caveats to consider before we get the perfect solution.

Minimum in Rotated Sorted Array

Find Minimum in Rotated Sorted Array - LeetCode_Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7]…_leetcode.com

Before moving on, I would like to thank Divya Godayal for contributing this section of the article. Cheers!

So the question simply asks us to find an element in an array that is

• sorted,
• rotated and apparently
• doesn’t contain any duplicate elements.

A very brute way of solving this question is to search the entire array and find the minimum element. This approach would simply ignore the fact that the given array is sorted and this is the naive approach to solve this problem. So first let us look at a simple linear search based solution for this problem.

Time Complexity: O(N) if there are N elements in the given array.

Space Complexity: O(1)

This is actually interesting. An O(N) solution gives us the best execution time on leetcode. However, it turns out that we can do way better than this as far as the asymptotic complexity is concerned.

The face that the given array is sorted is a huge hint in itself. Since the array is sorted and we are to find an element in the array, we can use the binary search paradigm.

However, the array is rotated. So simply applying the binary search won’t work here.

In this question we would essentially apply a modified version of binary search where the condition that decides the search direction would be different than in a standard binary search.

In a standard binary search algorithm we do the following

1. while left <= right2. mid = (left + right) / 23. if element == middle element:4. return mid5. elif element < middle element:6. move to the left i.e. [left, mid - 1]7. else:8. move to the right i.e. [mid + 1, right].

Since the given array is sorted, we can definitely apply the binary search algorithm to search for the element. The only thing is, that the elements have been rotated and that is something we have to account for.

How do we check if the array is even rotated or not in the first place?

If the array is not rotated and the array is sorted in ascending order, then

last_element > first_element

In the above example 7 > 2. This means that the array does not have any rotation. In this case we can simply return the first element of the array as that would be the minimum element.

However, if the array is in fact rotated, then there would be a heartbeat formation happening somewhere in the array. Let’s look at what we mean by a heartbeat formation.

If you look at the elements of the array above, they are in increasing order as expected (because the array is sorted in ascending order). However, after the element 7, there’s a sudden drop and then the values start to increase again. This is the heartbeat structure we are talking about.

In the array given above 3 < 4. Hence the array is rotated. This happens because the array was initially [2, 3 ,4 ,5 ,6 ,7]. But after the rotation the smaller elements[2,3] go at the back. i.e. [4, 5, 6, 7, 2, 3]. Because of this the first element [4] in the rotated array becomes greater than the last element.

The heartbeat structure that is evident from the question means there is a point in the array at which you would notice a change. This is the point which would help us in this question. We call this the Inflection Point.

An important property of the inflection point that would be critical in solving this question is:

* All the elements to the left of inflection point > first element of the array.* All the elements to the right of inflection point < first element of the array.

Let us now look at the algorithm to solve this question before looking at the implementation.

1. Find the mid element of the array.
2. If mid element > first element of array this means that we need to look for the inflection point on the right of mid.
3. If mid element < first element of array this that we need to look for the inflection point on the left of mid.

We stop our search when we find the inflection point, when either of the two conditions is satisfied:

→ nums[mid] > nums[mid + 1] Hence, mid+1 is the smallest.

→ nums[mid - 1] > nums[mid] Hence, mid is the smallest.

Time Complexity: O(logN) because all we are doing here is relying on our good friend, binary search and thus making use of the sorted nature of the original array.

Space Complexity: O(1)

Can’t do better than that now, can we ? 😉

The big catch in this problem is that there are no duplicate elements in the array. What if there are duplicate elements in the array ? Can we still follow a similar approach to solve the problem?

The answer to this question is yes and no. The same concepts that we discussed above apply to the this modified version of the problem as well. However, the time complexity is no longer guaranteed to be O(logN). Look at the following examples.

The two cases mentioned below are easier to solve because the middle element is different from the first and the last elements and can help direct the binary search (although you’d get stuck with a 4 as the mid point further down the binary search).

The point being is that since duplicate elements are allowed here, it is possible to have a scenario where:

leftmost element == middle element == rightmost element

and when this scenario takes place, how do we decide what direction we need to move towards. There is no possible way for us to know the direction that can be ignored by the binary search algorithm. So, we would have to try and consider both as possible candidates and process them and in case all of the elements are the same in our array i.e. [4,4,4,4,4,4,4,4] then we would eventually end up processing each of the elements one by one.

Therefore, with a heavy heart 😢 we have to conclude that there is just no way to get a guaranteed O(logN) complexity algorithm on this question. The worst case time complexity of a modified version of the binary search algorithm we looked at above would be O(N).

Let us move on to the final question for this article and it is going to be a blockbuster one. Trust me!

Orderly Queue

Orderly Queue - LeetCode_A string S of lowercase letters is given. Then, we may make any number of moves. In each move, we choose one of the…_leetcode.com

Let’s look at some of the possible string rotations first before getting to the solution. The string we will consider is baaca and K = 3 that means we can select any of the first three characters and then remove it from its location, add it to the very end and finally shift all the characters one position to the left to accommodate this new element in the end.

Assume the string has the following characters: a[0], a[1], a[2] … a[n-1] and we want to swap some position i (i >= 0 && i < n — 1) with position i+1, or swap a[i] and a[i+1]. The claim is that we can achieve this for any two adjacent elements in the string by using rotations on the string. e.g.:- Say the string consists of 5 characters and we want to swap a[2] and a[3] , here’s how we can achieve this with array rotations.

a[0], a[1], a[2], a[3], a[4], a[5] ROTATE around first element

a[1], a[2], a[3], a[4], a[5], a[0] ROTATE around first element

a[2], a[3], a[4], a[5], a[0], a[1] ROTATE around second element

a[2], a[4], a[5], a[0], a[1], a[3] ROTATE around first element

a[5], a[0], a[1], a[3], a[2], a[4] ROTATE around first element

a[0], a[1], a[3], a[2], a[4], a[5] ROTATE around first element

You can try playing around with this idea, but essentially we can swap any two adjacent elements in the given string by performing multiple rotations in the manner shown above.

Since we can swap any two elements, we can perform Bubble Sort!

The bubble sort algorithm essentially involves comparison amongst adjacent elements for the purpose of bubbling up/down elements to their respective positions in the array.

Thus we have achieved swapping of chars a[2] and a[3] without disturbing ordering of other characters (similarly this can be done for any pair of adjacent indices).

Therefore, if K > 1 in the question, we can essentially perform the bubble sort algorithm by using rotations and eventually the smallest lexicographic string that we would get would be the original string sorted in ascending order.

What about when K = 1?

In this case we don’t get that much freedom in “choosing” which element to move to the back of the array. In this case we have to look at all of the possible rotations of the original string and return the one that is lexicographically the smallest one.

If you remember correctly, the number of rotations for a string of size N are N. So, when K = 1, we would have to look at all of the array’s rotations (remember the mod method or concat methods we discussed in the article to get all rotations?) and obtain the smallest one lexicographically.

Let’s look at the implementation even though it is a very small one.

Time Complexity: O(NlogN) because we are sorting the string for K > 1

Space Complexity: O(N) because if K = 1, then we create S+S which is O(N) space allocation.

That’s it for this article. Hope you had a fun time learning rotations in arrays and I hope you were able to grasp all of the concepts that we discussed here.

All Hail Coding…