Problem
Given an M x N matrix, shift all its elements by 1 in spiral order
Sample Input
{
{ 1, 2, 3, 4, 5},
{16, 17, 18, 19, 6},
{15, 24, 25, 20, 7}
}
Sample Output
19 1 2 3 4 15 16 17 18 5 24 25 20 7 6
Approach
We can traverse through the matrix in a spiral manner and replace each element with its previous one. This problem largely resembles the “Print Matrix in Spiral Form” problem. The time complexity of this problem would be O( M x N ).
C++
#include<bits/stdc++.h>
usingnamespacestd;
// Function to shift all matrix elements by 1 in spiral order
voidsolve(int matrix[3][5], int row, int column)
{
int top = 0, bottom = row - 1;
int left = 0, right = column - 1;
int prev = matrix[0][0];
while (true)
{
if (left > right) {
break;
}
// shift top row
for (int i = left; i <= right; i++) {
swap(matrix[top][i], prev);
}
top++;
if (top > bottom) {
break;
}
// shift right column
for (int i = top; i <= bottom; i++) {
swap(matrix[i][right], prev);
}
right--;
if (left > right) {
break;
}
// shift bottom row
for (int i = right; i >= left; i--) {
swap(matrix[bottom][i], prev);
}
bottom--;
if (top > bottom) {
break;
}
// shift left column
for (int i = bottom; i >= top; i--) {
swap(matrix[i][left], prev);
}
left++;
}
// the first element of the matrix will be the last element replaced
matrix[0][0] = prev;
}
intmain()
{
int matrix[3][5] =
{
{ 1, 2, 3, 4, 5},
{16, 17, 18, 19, 6},
{15, 24, 25, 20, 7}
};
int row = 3;
int column = 5;
solve(matrix, row, column);
for (int i=0; i<row; i++) {
for (int j=0; j<column; j++) {
cout << matrix[i][j]<<" ";
}
cout << "\n";
}
return0;
}
Output
19 1 2 3 4 15 16 17 18 5 24 25 20 7 6
C
#include<stdio.h>
voidswap(int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}
// Function to shift all matrix elements by 1 in spiral order
voidsolve(int matrix[3][5], int row, int column)
{
int top = 0, bottom = row - 1;
int left = 0, right = column - 1;
int prev = matrix[0][0];
while (1)
{
if (left > right) {
break;
}
// shift top row
for (int i = left; i <= right; i++) {
swap(&matrix[top][i], &prev);
}
top++;
if (top > bottom) {
break;
}
// shift right column
for (int i = top; i <= bottom; i++) {
swap(&matrix[i][right], &prev);
}
right--;
if (left > right) {
break;
}
// change bottom row
for (int i = right; i >= left; i--) {
swap(&matrix[bottom][i], &prev);
}
bottom--;
if (top > bottom) {
break;
}
// shift left column
for (int i = bottom; i >= top; i--) {
swap(&matrix[i][left], &prev);
}
left++;
}
// the first element of the matrix will be the last element replaced
matrix[0][0] = prev;
}
intmain()
{
int matrix[3][5] =
{
{ 1, 2, 3, 4, 5},
{16, 17, 18, 19, 6},
{15, 24, 25, 20, 7}
};
int row = 3;
int column = 5;
solve(matrix, row, column);
for (int i=0; i<row; i++) {
for (int j=0; j<column; j++) {
printf("%d ",matrix[i][j]);
}
printf("\n");
}
return0;
}
Output
19 1 2 3 4 15 16 17 18 5 24 25 20 7 6
Python
defsolve(matrix): top = 0 bottom = len(matrix) - 1 left = 0 right = len(matrix[0]) - 1 prev = matrix[0][0] whileTrue: if left > right: break # shift top row for i in range(left, right + 1): temp = matrix[top][i] matrix[top][i] = prev prev = temp top = top + 1 if top > bottom: break # shift right column for i in range(top, bottom + 1): temp = matrix[i][right] matrix[i][right] = prev prev = temp right = right - 1 if left > right: break # shift bottom row for i in range(right, left - 1, -1): temp = matrix[bottom][i] matrix[bottom][i] = prev prev = temp bottom = bottom - 1 if top > bottom: break # shift left column for i in range(bottom, top - 1, -1): temp = matrix[i][left] matrix[i][left] = prev prev = temp left = left + 1 # first element of the matrix will be the last element replaced matrix[0][0] = prev matrix = [ [ 1, 2, 3, 4, 5], [16, 17, 18, 19, 6], [15, 24, 25, 20, 7] ] solve(matrix) print(matrix)
Output
[[19, 1, 2, 3, 4], [15, 16, 17, 18, 5], [24, 25, 20, 7, 6]]
People are also reading:
Leave a Comment on this Post