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:
- For each row in the matrix, perform the shifting 'K' times.
- In each iteration, keep the last element of the row in a variable 'data'.
- 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.
- Replace the first element of the row with 'data'.
- After completing 'K' iterations for a row, move to the next row and repeat the process.
- 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
- The 'shift_elements' function takes the 2D matrix 'matrix', the current row 'row', and the number of shifts 'k' as inputs.
- 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.
- Initialize 'data' as the last element of the row.
- 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.
- Replace the first element of the row with 'data' and continue shifting for the remaining 'k-1' times.
- 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.
- 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'.
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