Skip to main content

Shift row elements in a matrix

The problem is to shift the row elements of a given matrix by a given size K. For each row, we need to rotate the elements in a circular manner so that the elements at the end of the row move to the beginning. The shifting is performed 'K' times for each row. The size 'K' can be greater than the number of elements in a row, so it needs to be handled accordingly.

Problem Statement and Example

Consider the following matrix:

1  2  3  4
5  6  7  8
9  10 11 12
13 14 15 16

If we shift each row by a size of '2', the new matrix will be:

3  4  1  2
7  8  5  6
11 12 9  10
15 16 13 14

Idea to Solve the Problem

To shift the row elements in a matrix, we can follow the following approach:

  1. For each row in the matrix, perform the shifting 'K' times.
  2. In each iteration, keep the last element of the row in a variable 'data'.
  3. Traverse the row from the first element to the last element and shift each element to the right by one position, except for the last element.
  4. Replace the first element of the row with 'data'.
  5. After completing 'K' iterations for a row, move to the next row and repeat the process.
  6. Handle the case when 'K' is greater than the number of elements in a row by performing 'K % number_of_elements_in_a_row' shifts.

Pseudocode

shift_elements(matrix, row, k):
    if row >= 0:
        data = last element of matrix[row]
        for i from 0 to number_of_columns_in_matrix:
            temp = matrix[row][i]
            matrix[row][i] = data
            data = temp
        shift_elements(matrix, row-1, k)
    else if k > 1:
        shift_elements(matrix, number_of_rows_in_matrix - 1, k-1)

Algorithm Explanation

  1. The 'shift_elements' function takes the 2D matrix 'matrix', the current row 'row', and the number of shifts 'k' as inputs.
  2. If the current row 'row' is greater than or equal to 0, it means there are still rows to process. Perform the shifting 'k' times for the current row.
  3. Initialize 'data' as the last element of the row.
  4. Traverse the row from the first element to the last element and shift each element to the right by one position, except for the last element.
  5. Replace the first element of the row with 'data' and continue shifting for the remaining 'k-1' times.
  6. If the current row 'row' becomes negative (i.e., all rows have been processed), but 'k' is greater than 1, then there are still more shifts to perform. So, set 'row' to the last row of the matrix and reduce 'k' by 1.
  7. Repeat the process until 'k' becomes 1 and all rows have been shifted.

Code Solution

//C Program 
//Shift the row elements of given size K in matrix
#include<stdio.h>

//Matrix size
#define ROW 4
#define COL 4


void shift_elements(int arr[][COL],int row,int k)
{
 
 if(row >= 0)
 {
  int temp,data = arr[row][COL-1];

  for (int i = 0; i < COL; ++i)
  {
    //Swap element value
    temp = arr[row][i];
    arr[row][i] = data;
    data = temp;
  }
  shift_elements(arr,row-1,k);
 }
 else if(k>1)
 {
   shift_elements(arr,ROW-1,k-1);
 }
}
//Display matrix elements
void show_data(int arr[][COL])
{
  for (int i = 0; i < ROW; ++i)
  {
    for (int j = 0; j < COL; ++j)
    {
      printf("%3d",arr[i][j] );
    }
    printf("\n");
  }
  printf("\n");
}
int main()
{

  //Define matrix element
  int arr[][COL]={
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12},
    {13, 14, 15, 16}
  };

  int k=2;

  show_data(arr);

  shift_elements(arr,ROW-1,k);

  show_data(arr);

  return 0;
}

Output

  1  2  3  4
  5  6  7  8
  9 10 11 12
 13 14 15 16

  3  4  1  2
  7  8  5  6
 11 12  9 10
 15 16 13 14

/*
 C++ Program
 Shift the row elements of given size K in matrix
*/
#include<iostream>
//Matrix size
#define ROW 4
#define COL 4
using namespace std;

class MyMatrix {
	public:
	int rows;
	int cols;
	MyMatrix() {
		//Get the size of matrix
		this->rows = ROW;
		this->cols = COL;
	}
	void shift_elements(int matrix[][COL], int row, int k) {
		if (row >= 0) {
			int temp, data = matrix[row][this->cols - 1];
			for (int i = 0; i < this->cols; ++i) {
				//Swap element value
				temp = matrix[row][i];
				matrix[row][i] = data;
				data = temp;
			}
			this->shift_elements(matrix, row - 1, k);
		} else
		if (k > 1) {
			this->shift_elements(matrix, this->rows - 1, k - 1);
		}
	}
	//Display matrix elements
	void show_data(int matrix[][COL]) {
		for (int i = 0; i < this->rows; ++i) {
			for (int j = 0; j < this->cols; ++j) {
				cout << " " << matrix[i][j];
			}
			cout << "\n";
		}
		cout << "\n";
	}
};
int main() {
	int matrix[][COL] = {
		{
			1,
			2,
			3,
			4
		},
		{
			5,
			6,
			7,
			8
		},
		{
			9,
			10,
			11,
			12
		},
		{
			13,
			14,
			15,
			16
		}
	};
	MyMatrix obj;
	int k = 2;
	obj.show_data(matrix);
	obj.shift_elements(matrix, obj.rows - 1, k);
	obj.show_data(matrix);
	return 0;
}

Output

 1 2 3 4
 5 6 7 8
 9 10 11 12
 13 14 15 16

 3 4 1 2
 7 8 5 6
 11 12 9 10
 15 16 13 14

/*
  Java Program
  Shift the row elements of given size K in matrix
*/
public class MyMatrix {

  public int rows;
  public int cols;
  public MyMatrix(int [][]matrix)
  {
    //Get the size of matrix
    rows = matrix.length;
    cols = matrix[0].length;
  }
 
  public void shift_elements(int [][]matrix,int row,int k)
  {
   
    if(row >= 0)
    {
      int temp,data = matrix[row][cols-1];

      for (int i = 0; i < cols; ++i)
      {
        //Swap element value
        temp = matrix[row][i];
        matrix[row][i] = data;
        data = temp;
      }
      shift_elements(matrix,row-1,k);
    }
    else if(k>1)
    {
      shift_elements(matrix,rows-1,k-1);
    }
  }
  //Display matrix elements
  public void show_data(int [][]matrix)
  {
    for (int i = 0; i < rows; ++i)
    {
      for (int j = 0; j < cols; ++j)
      {
        System.out.print("  "+matrix[i][j] );
      }
      System.out.print("\n");
    }
    System.out.print("\n");
  }

  public static void main(String[] args) {
    
    //Define matrix 
    int [][]matrix = {
      {1, 2, 3, 4},
      {5, 6, 7, 8},
      {9, 10, 11, 12},
      {13, 14, 15, 16}
    };
    MyMatrix obj = new MyMatrix(matrix);
    int k=2;

    obj.show_data(matrix);

    obj.shift_elements(matrix,obj.rows-1,k);

    obj.show_data(matrix);
  }
}

Output

 1 2 3 4
 5 6 7 8
 9 10 11 12
 13 14 15 16

 3 4 1 2
 7 8 5 6
 11 12 9 10
 15 16 13 14

using System;
/*
  C# Program
  Shift the row elements of given size K in matrix
*/

public class MyMatrix {
	int rows;
	int cols;
	MyMatrix(int[,] matrix) {
		//Get the size of matrix
		rows = matrix.GetLength(0);
		cols = matrix.GetLength(1);
	}
	public void shift_elements(int[,] matrix, int row, int k) {
		if (row >= 0) {
			int temp, data = matrix[row,cols - 1];
			for (int i = 0; i < cols; ++i) {
				//Swap element value
				temp = matrix[row,i];
				matrix[row,i] = data;
				data = temp;
			}
			shift_elements(matrix, row - 1, k);
		} else
		if (k > 1) {
			shift_elements(matrix, rows - 1, k - 1);
		}
	}
	//Display matrix elements
	public void show_data(int[,] matrix) {
		for (int i = 0; i < rows; ++i) {
			for (int j = 0; j < cols; ++j) {
				Console.Write(" " + matrix[i,j]);
			}
			Console.Write("\n");
		}
		Console.Write("\n");
	}
	public static void Main(String[] args) {
		int[,]
		//Define matrix 
		matrix = {
			{
				1,
				2,
				3,
				4
			},
			{
				5,
				6,
				7,
				8
			},
			{
				9,
				10,
				11,
				12
			},
			{
				13,
				14,
				15,
				16
			}
		};
		MyMatrix obj = new MyMatrix(matrix);
		int k = 2;
		obj.show_data(matrix);
		obj.shift_elements(matrix, obj.rows - 1, k);
		obj.show_data(matrix);
	}
}

Output

 1 2 3 4
 5 6 7 8
 9 10 11 12
 13 14 15 16

 3 4 1 2
 7 8 5 6
 11 12 9 10
 15 16 13 14

<?php
/*
  Php Program
  Shift the row elements of given size K in matrix
*/
class MyMatrix {
	public $rows;
	public $cols;

	function __construct($matrix) {
		//Get the size of matrix
		$this->rows = count($matrix);
		$this->cols = count($matrix[0]);
	}
	public 	function shift_elements(&$matrix, $row, $k) {
		if ($row >= 0) {
			$temp;
			$data = $matrix[$row][$this->cols - 1];
			for ($i = 0; $i < $this->cols; ++$i) {
				//Swap element value
				$temp = $matrix[$row][$i];
				$matrix[$row][$i] = $data;
				$data = $temp;
			}
			$this->shift_elements($matrix, $row - 1, $k);
		} 
      	else if ($k > 1) {
			$this->shift_elements($matrix, $this->rows - 1, $k - 1);
		}
	}
	//Display matrix elements

	public 	function show_data($matrix) {
		for ($i = 0; $i < $this->rows; ++$i) {
			for ($j = 0; $j < $this->cols; ++$j) {
				echo(" ". $matrix[$i][$j]);
			}
			echo("\n");
		}
		echo("\n");
	}
};

function main() {
	//Define matrix 
	$matrix = array(array(1, 2, 3, 4), array(5, 6, 7, 8), array(9, 10, 11, 12), array(13, 14, 15, 16));
	$obj = new MyMatrix($matrix);
	$k = 2;
	$obj->show_data($matrix);
	$obj->shift_elements($matrix, $obj->rows - 1, $k);
	$obj->show_data($matrix);

}
main();

Output

 1 2 3 4
 5 6 7 8
 9 10 11 12
 13 14 15 16

 3 4 1 2
 7 8 5 6
 11 12 9 10
 15 16 13 14

/*
 Node Js Program
 Shift the row elements of given size K in matrix
*/
class MyMatrix {
	;;
	constructor(matrix) {
		//Get the size of matrix
		this.rows = matrix.length;
		this.cols = matrix[0].length;
	}
	shift_elements(matrix, row, k) {
		if (row >= 0) {
			var temp;
			var data = matrix[row][this.cols - 1];
			for (var i = 0; i < this.cols; ++i) {
				//Swap element value
				temp = matrix[row][i];
				matrix[row][i] = data;
				data = temp;
			}
			this.shift_elements(matrix, row - 1, k);
		} else
		if (k > 1) {
			this.shift_elements(matrix, this.rows - 1, k - 1);
		}
	}

	//Display matrix elements
	show_data(matrix) {
		for (var i = 0; i < this.rows; ++i) {
			for (var j = 0; j < this.cols; ++j) {
				process.stdout.write(" " + matrix[i][j]);
			}

			process.stdout.write("\n");
		}

		process.stdout.write("\n");
	}
}

function main(args) {
	//Define matrix 
	var matrix = [
		[1, 2, 3, 4],
		[5, 6, 7, 8],
		[9, 10, 11, 12],
		[13, 14, 15, 16]
	];
	var obj = new MyMatrix(matrix);
	var k = 2;
	obj.show_data(matrix);
	obj.shift_elements(matrix, obj.rows - 1, k);
	obj.show_data(matrix);
}
main();

Output

 1 2 3 4
 5 6 7 8
 9 10 11 12
 13 14 15 16

 3 4 1 2
 7 8 5 6
 11 12 9 10
 15 16 13 14

# Python 3 Program
# Shift the row elements of given size K in matrix
class MyMatrix :
	
	def __init__(self, matrix) :
		# Get the size of matrix
		self.rows = len(matrix)
		self.cols = len(matrix[0])
	
	def shift_elements(self, matrix, row, k) :
		if (row >= 0) :
			temp = 0
			data = matrix[row][self.cols - 1]
			i = 0
			while (i < self.cols) :
				# Swap element value
				temp = matrix[row][i]
				matrix[row][i] = data
				data = temp
				i += 1
			
			self.shift_elements(matrix, row - 1, k)
		elif (k > 1) :
			self.shift_elements(matrix, self.rows - 1, k - 1)
		
	
	# Display matrix elements
	def show_data(self, matrix) :
		i = 0
		while (i < self.rows) :
			j = 0
			while (j < self.cols) :
				print(" ", matrix[i][j], end = "")
				j += 1
			
			print("\n", end = "")
			i += 1
		
		print("\n", end = "")
	

def main() :
	matrix = [
		[1, 2, 3, 4],
		[5, 6, 7, 8],
		[9, 10, 11, 12],
		[13, 14, 15, 16]
	]
	obj = MyMatrix(matrix)
	k = 2
	obj.show_data(matrix)
	obj.shift_elements(matrix, obj.rows - 1, k)
	obj.show_data(matrix)


if __name__ == "__main__":
	main()

Output

  1  2  3  4
  5  6  7  8
  9  10  11  12
  13  14  15  16

  3  4  1  2
  7  8  5  6
  11  12  9  10
  15  16  13  14

# Ruby Program 
# Shift the row elements of given size K in matrix
class MyMatrix 
	# Define the accessor and reader of class MyMatrix
    attr_reader :rows, :cols
    attr_accessor :rows, :cols
	def initialize(matrix) 
		# Get the size of matrix
		@rows = matrix.length
		@cols = matrix[0].length
	end
	def shift_elements(matrix, row, k) 
		if (row >= 0) 
			temp = 0
			data = matrix[row][@cols - 1]
			i = 0
			while (i < @cols) 
				# Swap element value
				temp = matrix[row][i]
				matrix[row][i] = data
				data = temp
				i += 1
			end
			self.shift_elements(matrix, row - 1, k)
		elsif (k > 1) 
			self.shift_elements(matrix, @rows - 1, k - 1)
		end
	end
	# Display matrix elements
	def show_data(matrix) 
		i = 0
		while (i < @rows) 
			j = 0
			while (j < @cols) 
				print(" ", matrix[i][j])
				j += 1
			end
			print("\n")
			i += 1
		end
		print("\n")
	end
end
def main() 
	matrix = [
		[1, 2, 3, 4],
		[5, 6, 7, 8],
		[9, 10, 11, 12],
		[13, 14, 15, 16]
	]
	obj = MyMatrix.new(matrix)
	k = 2
	obj.show_data(matrix)
	obj.shift_elements(matrix, obj.rows - 1, k)
	obj.show_data(matrix)
end


main()

Output

 1 2 3 4
 5 6 7 8
 9 10 11 12
 13 14 15 16

 3 4 1 2
 7 8 5 6
 11 12 9 10
 15 16 13 14


/*
 Scala Program
 Shift the row elements of given size K in matrix
*/
class MyMatrix(var rows: Int,var cols: Int) {


	def this(matrix: Array[Array[Int]]) {
		//Get the size of matrix
		this(matrix.length,matrix(0).length);
	}
	def shift_elements(matrix: Array[Array[Int]], row: Int, k: Int): Unit = {
		if (row >= 0) {
			var temp: Int = 0;
			var data: Int = matrix(row)(this.cols - 1);
			var i: Int = 0;
			while (i < this.cols) {
				//Swap element value
				temp = matrix(row)(i);
				matrix(row)(i) = data;
				data = temp;
				i += 1;
			}
			this.shift_elements(matrix, row - 1, k);
		} else
		if (k > 1) {
			this.shift_elements(matrix, this.rows - 1, k - 1);
		}
	}
	//Display matrix elements
	def show_data(matrix: Array[Array[Int]]): Unit = {
		var i: Int = 0;
		while (i < this.rows) {
			var j: Int = 0;
			while (j < this.cols) {
				print(" " + matrix(i)(j));
				j += 1;
			}
			print("\n");
			i += 1;
		}
		print("\n");
	}
}
object Main {
	def main(args: Array[String]): Unit = {
		val matrix: Array[Array[Int]] = Array(
			Array(1, 2, 3, 4),
			Array(5, 6, 7, 8),
			Array(9, 10, 11, 12),
			Array(13, 14, 15, 16));
		val obj: MyMatrix = new MyMatrix(matrix);
		val k: Int = 2;
		obj.show_data(matrix);
		obj.shift_elements(matrix, obj.rows - 1, k);
		obj.show_data(matrix);
	}
}

Output

 1 2 3 4
 5 6 7 8
 9 10 11 12
 13 14 15 16

 3 4 1 2
 7 8 5 6
 11 12 9 10
 15 16 13 14

/*
  Swift 4 Program
  Shift the row elements of given size K in matrix
*/
class MyMatrix {
	var rows : Int;
	var cols : Int;
	init(_ matrix: [[Int]]) {
		//Get the size of matrix
		self.rows = matrix.count;
		self.cols = matrix[0].count;
	}
	func shift_elements(_ matrix: inout [[Int]], _ row: Int, _ k: Int) {
		if (row >= 0) {
			var temp: Int = 0;
			var data: Int = matrix[row][self.cols - 1];
			var i: Int = 0;
			while (i < self.cols) {
				//Swap element value
				temp = matrix[row][i];
				matrix[row][i] = data;
				data = temp;
				i += 1;
			}
			self.shift_elements(&matrix, row - 1, k);
		} else
		if (k > 1) {
			self.shift_elements(&matrix, self.rows - 1, k - 1);
		}
	}
	//Display matrix elements
	func show_data(_ matrix: [
		[Int]
	]) {
		var i: Int = 0;
		while (i < self.rows) {
			var j: Int = 0;
			while (j < self.cols) {
				print(" ", matrix[i][j], terminator: "");
				j += 1;
			}
			print("\n", terminator: "");
			i += 1;
		}
		print("\n", terminator: "");
	}
}
func main() {
	var matrix: [
		[Int]
	] = [
		[1, 2, 3, 4],
		[5, 6, 7, 8],
		[9, 10, 11, 12],
		[13, 14, 15, 16]
	];
	let obj: MyMatrix = MyMatrix(matrix);
	let k: Int = 2;
	obj.show_data(matrix);
	obj.shift_elements(&matrix, obj.rows - 1, k);
	obj.show_data(matrix);
}
main();

Output

  1  2  3  4
  5  6  7  8
  9  10  11  12
  13  14  15  16

  3  4  1  2
  7  8  5  6
  11  12  9  10
  15  16  13  14

Output Explanation

The given code defines a 'MyMatrix' class that shifts the row elements of a matrix and displays the result. The output displays the matrix before and after the shifting as follows:

Before Shifting:

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

After Shifting each row by '2':

3 4 1 2
7 8 5 6
11 12 9 10
15 16 13 14

Time Complexity

The time complexity of the provided solution depends on the number of elements in the matrix. Suppose the matrix has 'm' rows and 'n' columns. The time complexity for shifting each row 'K' times is O(K * n). The overall time complexity of shifting all rows 'K' times is O(K * m * n). The primary operations involve shifting elements in each row, which takes linear time based on the number of elements in each row. The overall time complexity is linear with respect to the size of the input matrix and the number of shifts 'K'.

Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment