Skip to main content

Arrays Hands-On: Warming Up

Traversals - 4

Rotate Array (once)

Explained in simpler words, the problem basically says that given an array of integers, our target is to shift each element to the position just next to it (on the right side).

Now, you may think that it probably makes sense for all the other elements, but where will the last element go? It should come to the first position. Please refer to the diagram below for a better explanation.

How to solve it?

One way could be to create a new array, and try to set the elements in such a manner, that the newly created array is the rotated version of the given array.

Now, after being done with the new array, we can just copy paste the elements from the new array to the original array, and we're done.

Let's explore this way first.

Idea

Let's call the newly created array ans and the original given array, arr.

Now, since all the elements are shifted right once, that simply means that, ans[1] = arr[0], ans[2] = arr[1], .. ans[n-1] = arr[n-2]. In general, what I basically mean to say is that ans[i] = arr[i-1].

The above holds true for all the indices except the index 0. The value of ans[0] will be equal to arr[n-1]. Please look at the above diagram carefully to be able to understand this.

I think that enough idea about the solution has been given above, let's dive right into implementing the approach given above. Once again, please try it yourself first.

Implementation 
void rotate(int arr[], int n)
{
    // Declaring a new vector/array
    vector<int> ans(n);
    
    // Handling the general cases
    for(int i = 1; i < n; ++i)
        ans[i] = arr[i-1];
        
    // Handling the corner case.
    ans[0] = arr[n-1];
    
    // Copying the elements to arr.
    for(int i = 0; i < n; ++i)
        arr[i] = ans[i];
}

How to solve it without using extra space?

Now, what we're going to try to do is make some changes in the given array itself, to rotate it, without any involvement of a second array. This process of not involving a new array and doing things in the given input array is sometimes referred to as doing something in-place.

Trial 1

Code 
void rotate(int arr[], int n)
{   
    // Handling the general cases
    for(int i = 1; i < n; ++i)
        arr[i] = arr[i-1];
        
    // Handling the corner case.
    arr[0] = arr[n-1];
}
What's wrong with trial 1?

What's wrong is that we're saying that arr[i] = arr[i-1] but arr[i-1] would've already been updated because we're iterating from left to right.

To break it down, let's try to dry-run the code line-by-line for the input [1, 2, 3, 4]:

  1. In the first iteration: i = 1, therefore arr[1] will become equal to arr[0]. Hence, arr[1] = 1.
  2. In the second iteration: i = 2, therefore arr[2] will become equal to arr[1]. Hence, arr[2] = 1.
  3. I hope you get the picture, everything will become equal to 1..

A learning

A learning from this trial that'll be useful is that always keep this in check that if you're shifting around different values in a data structure, make sure that you do it in such a manner that you do have the initial original values when required.

Hope the above explanation makes sense. If it doesn't, please use the feedback form to let me know.

Trial 2

Idea

What we did in the above trial was that by the time we used arr[i] to shift it, it was already updated.

So, instead of iterating from left to right, what we iterate from right to left? Think about it.

Code 
void rotate(int arr[], int n)
{   
    // Handling the general cases
    for(int i = n - 1; i >= 1; --i)
        arr[i] = arr[i-1];
        
    // Handling the corner case.
    arr[0] = arr[n-1];
}
Is there anything wrong? The answer is that we're almost there, there's just a small thing. Try to find the bug before moving on?
The Bug

The bug is in the corner case. If you notice the general case, the problem with trial 1 is solved now, because now arr[i] is made equal to arr[i-1], and because we're iterating in reverse order, arr[i-1] wouldn't have been touched when we're dealing with arr[i].

In the corner case, the problem is that arr[n-1] has already been updated and is going to be equal to arr[n-2], let's quickly fix the bug, and we're done.

Final Implementation

Code 
void rotate(int arr[], int n)
{   
	int last_element = arr[n - 1];

    // Handling the general cases
    for(int i = n - 1; i >= 1; --i)
        arr[i] = arr[i-1];
        
    // Handling the corner case.
    arr[0] = last_element;
}
Time and Space Complexity
  • Time Complexity: O(N)
  • Space Complexity: O(1)