Rotating a column along with a matrix

Write a program that performs a circular right and left rotation on 1-D and 2-D arrays.

Let’s discuss first what is circular left and right rotation.

Circular right rotation

The first element will be placed with the last element, and the rest of the elements will shift to the right.

Circular left rotation

The last element will be placed with the first element, and the rest of the elements will shift to the left.

Let’s discuss first how we can perform circular rotation in a 1-D array.

Single-dimensional right rotation

Write a program that performs right circular rotation in a 1-D array.

Sample input

1 2 3 4 5 6 7

Sample output

7 1 2 3 4 5 6

As we have seen above, the animation of right circular rotation in a 1-D array. Let’s discuss 2 solutions.

Solution 1: Shifting using an extra variable

The animation has a 1-D array that iterates from left to right. We shift all values in the right direction in each iteration except the last one. The last value should be placed at the first value.

Look at the code below for right shifting:

Press + to interact
#include <iostream>
using namespace std;
void rightShift(int A[], int size)
{              
    for(int i=0; i < size; i++)
    {
        A[i+1]=A[i];          // Exercise: correct the logical error
    }
    A[0] = A[size-1];              
}
void leftShift(int A[], int size)
{   // Exercise: To solve       
    // Write your code here              
}
void print1D(const char MSG[], int A[], int size)
{   
    cout << MSG<<": {";
    for(int i=0; i<size; i++)
    {
        cout<<A[i];
        if(i!=size-1)
            cout<<",";
    }                  
    cout<< "}";  
}
int main()
{
    const int capacity=100;
    int size=7;
    int Array[capacity]={1,2,3,4,5,6,7};
    print1D("Before right shift A[]", Array, size);
    rightShift(Array, size);
    print1D("\n After right shift A[]", Array, size);
    
    return 0;
}

Circular right rotation

Question 1

The above solution has a logical error. What is it?

Show Answer
Question 2

Is the boundary condition valid?

Show Answer

When A[i+1]=A[i], the A[0] value moves to A[1] but the previous value, A[1], is replaced. What can we do not to lose A[1]? Think about that.

We’ll have to update the rightShift() function by removing the logical mistakes.

In case you are stuck, go through the solution below.

Solution 2: Another shifting approach

Let’s look at another way to solve the above problem.

  • Pick the last element and swap with previous elements until the last element reaches the first place.

Look at the animation below in which we are swapping the last element, 7, with the previous element until it reaches the place of first element.

Implementation details

  • We need to make a loop that iterates from the last column to the first column.
  • In the first iteration, we swap the last column with the second last column.
  • In the second iteration, we swap the second last column with the third last column.
  • In each iteration, we need to swap the two columns till the first column.

Exercise: Rotate left

Write the code for rotating left in an array.

Instruction: Write the code in the above playground.

2-D matrix rotation

Write a program that circularly right-rotates the 2-D array.

Sample input

Matrix:
                  4  3  2  1  5
                  5  2  5  4  6
                  1  2  3  5  7
                  8  9  6  3  2
                  1  3  5  7  9

Sample output

Rotate Matrix by Column:
                  5  4  3  2  1
                  6  5  2  5  4
                  7  1  2  3  5
                  2  8  9  6  3
                  9  1  3  5  7

The idea to solve the problem is the following:

  • Swap the last column with the second last column, then swap the second last column with the third last column. We will repeat this step until the last column reaches the first column. Note that this is the exact same idea as a 1-D array (the only difference is that, instead of swapping two values, we are swapping two columns).

Look at the animation below:

Implementation details

To swap a column, let’s create a function, swapCols(), that takes a matrix, two-column index with row size as a parameter. Inside the function, we just swap the two columns based on column numbers.

Look at the code below:

Press + to interact
void swapCols(int Array[][maxCols], int c1, int c2, int rows)
{
	for (int ri = 0; ri < rows; ri++)
	{
		int t = Array[ri][c1];
		Array[ri][c1] = Array[ri][c2];
		Array[ri][c2] = t;
	}
}

As we have done with one swap of columns. But now, we want to perform the right rotation on the 2-D matrix. How can we implement it?

Let’s make another function, rotate2DArrayByCols(), that calls the above swapCols() function for each rotation. Inside the function, we will do the following:

  • We have a loop that iterates from the last column to the first column.
  • In the first iteration, we swap the last column with the second last column.
  • In the second iteration, we swap the second last column with the third last.
  • In each iteration, we need to swap the two columns till the first column.
  • When the loop terminates, we will have a right-rotated 2-D matrix.
Press + to interact
void rotateRight2DArrayByCols(int Matrix[][maxCols], int rows, int cols)
{
	for (int c = cols - 1; c > 0; c--)
	{
		swapCols(Matrix, c, c - 1, rows);
	}
}

Let’s execute the complete code below:

5 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
Rotate 2D array by column

Exercise: Rotate left

Write the code to left-rotate a matrix.

Sample input

Original matrix:
                  4  3  2  1  5
                  5  2  5  4  6
                  1  2  3  5  7
                  8  9  6  3  2
                  1  3  5  7  9

Sample output

Rotated left matrix:
                  3  2  1  5  4
                  2  5  4  6  5
                  2  3  5  7  1
                  9  6  3  2  8
                  3  5  7  9  1

Exercise: Rotate down

We rotated the above 2-D matrix column-wise. Now, just for your practice, you need to solve the same problem using row-wise rotation.

Sample input

Matrix:
                  4  3  2  1  5
                  5  2  5  4  6
                  1  2  3  5  7
                  8  9  6  3  2
                  1  3  5  7  9

Sample output

Rotate matrix downward (row-wise):
                  1  3  5  7  9
                  4  3  2  1  5
                  5  2  5  4  6
                  1  2  3  5  7
                  8  9  6  3  2

Exercise: Rotate up

Here you need to rotate the same problem using row-wise rotation upwards.

Sample input

Matrix:
                  4  3  2  1  5
                  5  2  5  4  6
                  1  2  3  5  7
                  8  9  6  3  2
                  1  3  5  7  9

Sample output

Rotate matrix upward (row-wise):
                  5  2  5  4  6
                  1  2  3  5  7
                  8  9  6  3  2
                  1  3  5  7  9
                  4  3  2  1  5