Amazon Interview Question Software Engineers
Country: United States
Interview Type: Written Test
Are there any complexity constraints?
Transpose the matrix and reverse the rows, or just read the columns out backwards. Have I misunderstood what you mean by "rotate"?
When you say "length" are you referring to the entire length of the matrix when represented as an array or simply the dimension "m" of an m x m matrix?
No complexity constraints listed, but I assumed this could be done in O(n) time, O(1) space. My ideal approach is to traverse each position in the matrix, move the value in higher-order in the concentric circle relative to its own position, then stop when the original position is reached. When an element is moved, set it's position to null, temporarily save the next position's value and replace it with the moved value. When the original position is reached, there should be a null value to replace with the last popped value.
#include <iostream>
using namespace std;
void RotateMatrix(char **matrix, int length){
int swaps = length/2;
int i, j;
char temp;
// 4 way swap!
for(i = 0; i < swaps; i++)
for(j = i; j < length - 1 - i; j++) {
temp = matrix[i][j];
matrix[i][j] = matrix[length - 1 - j][i];
matrix[length - 1 - j][i] = matrix[length - 1 - i][length - 1 - j];
matrix[length - 1 - i][length - 1 - j] = matrix[j][length - 1 - i];
matrix[j][length - 1 - i] = temp;
}
}
void DisplayMatrix(char **matrix, int length){
int i, j;
for(i = 0; i < length; i++) {
for(j = 0; j < length; j++)
cout << matrix[i][j];
cout << endl;
}
cout << endl;
}
int main(){
int i;
int length;
char **matrix;
// 1) Get length
cout << "Enter length of square matrix: ";
cin >> length;
cout << endl;
// 2) Get matrix
matrix = new char*[length];
for(i = 0; i < length; i++)
matrix[i] = new char[length];
cout << "Enter the " << length << " is of the matrix: " << endl;
cin.ignore();
for(i = 0; i < length; i++) {
cin.getline(matrix[i], length + 1); // delim character will be extracted but discarded.
if(cin.gcount() < length) {
cout << "Need to enter " << length << " # characters." << endl;
i--;
}
else if( cin.fail() ){
cout << "Too many characters entered. " << endl;
cin.clear();
i--;
}
}
cout << endl;
// 3) Rotate Matrix
RotateMatrix(matrix, length);
// 4) Display Matrix
cout << "Rotated Matrix: " <<endl;
DisplayMatrix(matrix, length);
return 0;
}
#include <iostream>
using namespace std;
void RotateMatrix(char **matrix, int length){
int swaps = length/2;
int i, j;
char temp;
// 4 way swap!
for(i = 0; i < swaps; i++)
for(j = i; j < length - 1 - i; j++) {
temp = matrix[i][j];
matrix[i][j] = matrix[length - 1 - j][i];
matrix[length - 1 - j][i] = matrix[length - 1 - i][length - 1 - j];
matrix[length - 1 - i][length - 1 - j] = matrix[j][length - 1 - i];
matrix[j][length - 1 - i] = temp;
}
}
void DisplayMatrix(char **matrix, int length){
int i, j;
for(i = 0; i < length; i++) {
for(j = 0; j < length; j++)
cout << matrix[i][j];
cout << endl;
}
cout << endl;
}
int main(){
int i;
int length;
char **matrix;
// 1) Get length
cout << "Enter length of square matrix: ";
cin >> length;
cout << endl;
// 2) Get matrix
matrix = new char*[length];
for(i = 0; i < length; i++)
matrix[i] = new char[length];
cout << "Enter the " << length << " is of the matrix: " << endl;
cin.ignore();
for(i = 0; i < length; i++) {
cin.getline(matrix[i], length + 1); // delim character will be extracted but discarded.
if(cin.gcount() < length) {
cout << "Need to enter " << length << " # characters." << endl;
i--;
}
else if( cin.fail() ){
cout << "Too many characters entered. " << endl;
cin.clear();
i--;
}
}
cout << endl;
// 3) Rotate Matrix
RotateMatrix(matrix, length);
// 4) Display Matrix
cout << "Rotated Matrix: " <<endl;
DisplayMatrix(matrix, length);
return 0;
}
too complicated?
#include <iostream>
using namespace std;
void RotateMatrix(char **matrix, int length){
int circles = length/2;
int i, j;
char temp;
for(i = 0; i < circles; i++) {
// Rotate Left
temp = matrix[i][i];
for(j = i; j < length - 1 - i; j++)
matrix[j][i] = matrix[j + 1][i];
// Rotate Bottom
for(j = i; j < length - 1 - i; j++)
matrix[length - 1 - i][j] = matrix[length - 1 - i][j+1];
// Rotate Right
for(j = length - 1 - i; j > i; j--)
matrix[j][length - 1 - i] = matrix[j - 1][length - 1 - i];
// Rotate Top
for(j = length - 1 - i; j > i; j--)
matrix[i][j] = matrix[i][j - 1];
matrix[i][i + 1] = temp;
}
}
void DisplayMatrix(char **matrix, int length){
int i, j;
for(i = 0; i < length; i++) {
for(j = 0; j < length; j++)
cout << matrix[i][j];
cout << endl;
}
cout << endl;
}
int main(){
int i;
int length;
char **matrix;
// 1) Get length
cout << "Enter length of square matrix: ";
cin >> length;
cout << endl;
// 2) Get matrix
matrix = new char*[length];
for(i = 0; i < length; i++)
matrix[i] = new char[length];
cout << "Enter the " << length << " is of the matrix: " << endl;
cin.ignore();
for(i = 0; i < length; i++) {
cin.getline(matrix[i], length + 1); // delim character will be extracted but discarded.
if(cin.gcount() < length) {
cout << "Need to enter " << length << " # characters." << endl;
i--;
}
else if( cin.fail() ){
cout << "Too many characters entered. " << endl;
cin.clear();
i--;
}
}
cout << endl;
// 3) Rotate Matrix
RotateMatrix(matrix, length);
// 4) Display Matrix
cout << "Rotated Matrix: " <<endl;
DisplayMatrix(matrix, length);
return 0;
}
This simple version is O(n**2) time and space. It can also be done in-place in O(n) time.
import sys
def rotate(m):
nn = n**2
o = [0] * nn
for i in range(nn):
j = (n * i) % nn + (nn - 1 - i) // n
o[j] = m[i]
return o
if __name__ == "__main__":
matrix = []
n = int(sys.stdin.readline())
for l in range(n):
matrix.extend((int(e) for e in (sys.stdin.readline().split())))
rotate(matrix)
Now we understand the question. Time linear in the size of the matrix.
By using swaps instead this could be done in place to save the O(n) space and in linear time (3 swaps for 2x2, 7 swaps for 3x3, 14 swaps for a 4x4, 22 swaps for 5x5 ) but in an interview I'd focus on getting a working solution then making it perform better.
import sys
def rotate(m):
nn = n**2
o = [0] * nn
for x in range(nn):
i = x // n
j = x % n
if i <= j and i < (n - j - 1):
o[x + 1] = m[x]
elif j > i >= (n - j - 1):
o[x + n] = m[x]
elif i >= j and i > (n - j - 1):
o[x - 1] = m[x]
elif j < i <= (n - j - 1):
o[x - n] = m[x]
else:
o[x] = m[x]
return o
if __name__ == "__main__":
matrix = []
n = int(sys.stdin.readline())
for l in range(n):
matrix.extend((int(e) for e in (sys.stdin.readline().split())))
matrix = rotate(matrix)
for r in range(n):
print(matrix[r*n:(r + 1)*n])
public class SpiralRotation {
public static void rotate(ArrayList<ArrayList<Integer>> matrix) {
int M = matrix.size();
int N = matrix.get(0).size();
int left = 0, right = N - 1, top = 0, bottom = M - 1;
int dir = 0, temp = Integer.MIN_VALUE;
while (left <= right && top <= bottom) {
if (dir == 0) {
if (left == right) break;
temp = matrix.get(top + 1).get(left);
for (int i = left; i <= right; ++i) {
int swap = matrix.get(top).get(i);
matrix.get(top).set(i, temp);
temp = swap;
}
top++;
}
if (dir == 1) {
for (int i = top; i <= bottom; ++i) {
int swap = matrix.get(i).get(right);
matrix.get(i).set(right, temp);
temp = swap;
}
right--;
}
if (dir == 2) {
for (int i = right; i >= left; --i) {
int swap = matrix.get(bottom).get(i);
matrix.get(bottom).set(i, temp);
temp = swap;
}
bottom--;
}
if (dir == 3) {
for (int i = bottom; i >= top; --i) {
int swap = matrix.get(i).get(left);
matrix.get(i).set(left, temp);
temp = swap;
}
left++;
}
dir = (dir + 1) % 4;
}
matrix.forEach(row -> System.out.println(row));
}
}
Here's a solution in Ruby. Running time O(n), space O(1)
matrix1=[
[1, 2],
[3, 4]
]
matrix2=[
[1, 2, 3, 4],
[5, 6, 7, 8],
[1, 2, 3, 4],
[5, 6, 7, 8]
]
matrix3=[
[1,2,3],
[4,5,6],
[7,8,9]
]
def base_rotate(matrix)
return matrix if matrix.length == 0 || matrix.length == 1
nil
end
def rotate_with_sublength(matrix,sublength,circleIndex)
length=sublength
rowStart=circleIndex
colStart=circleIndex
start_position_val=matrix[rowStart][colStart]
#puts "Length: #{length}. row start: #{rowStart}. col start: #{colStart}. Start pos val: #{start_position_val}"
# right
(rowStart-length+2..rowStart).to_a.reverse.each do |rowIndex|
#puts "#{rowIndex}#{colStart}=#{rowIndex-1}#{colStart}"
matrix[rowIndex][colStart]=matrix[rowIndex-1][colStart]
end
#puts
# top
(colStart-length+2..colStart).to_a.reverse.each do |colIndex|
#puts "#{rowStart-length+1}#{colIndex}=#{rowStart-length+1}#{colIndex-1}"
matrix[rowStart-length+1][colIndex]=matrix[rowStart-length+1][colIndex-1]
end
#puts
# left
(rowStart-length+1...rowStart).each do |rowIndex|
#puts "#{rowIndex}#{colStart-length+1}=#{rowIndex+1}#{colStart-length+1}"
matrix[rowIndex][colStart-length+1]=matrix[rowIndex+1][colStart-length+1]
end
#puts
# bottom
(colStart-length+1...colStart).each do |colIndex|
#puts "#{rowStart}#{colIndex}=#{rowStart}#{colIndex+1}"
matrix[rowStart][colIndex]=matrix[rowStart][colIndex+1]
end
#puts
matrix[rowStart][colStart-1]=start_position_val
#puts
end
def rotate(matrix)
return if base_rotate(matrix)
length=matrix.length
circleIndex=length-1
while length >= 2
rotate_with_sublength(matrix,length,circleIndex)
length-=2
circleIndex-=1
end
end
def print_matrix(matrix)
matrix.each do |row|
row.each do |value|
print value.to_s+' '
end
puts
end
puts
end
puts "original matrix"
print_matrix(matrix2)
rotate(matrix2)
puts "Rotated matrix"
print_matrix(matrix2)
Output:
original matrix
1 2 3 4
5 6 7 8
1 2 3 4
5 6 7 8
Rotated matrix
5 1 2 3
1 2 6 4
5 3 7 8
6 7 8 4
/* Given a 2-dimensional square matrix, rotate the matrix clockwise.
* Imagine concentric circles. Input from stdin: first line is length,
* subsequent lines are rows of the matrix. Output the matrix to stdout.
* You have 2 hrs to complete it.
*/
#include <iostream>
#include <string>
#include <cstdlib>
#include <stdint.h>
using namespace std;
#define MAX_CIRCLE_COUNT 10
struct matrix_spec {
int circle_idx;
int array_idx;
};
template <typename T>
T **Allocate2dSquareMatrix(int size) {
T **array_2d = new T*[size]();
for (int i = 0; i < size; ++i) {
array_2d[i] = new T[size]();
}
return array_2d;
}
template <typename T>
void Deallocate2dSquareMatrix(T **array_2d, int size) {
for (int i = 0; i < size; ++i) {
delete[] array_2d[i];
}
delete[] array_2d;
}
void RotateArray(int *array, int size) {
int val_forward = array[0];
int tmp = 0;
for (int i = 0; i < size-1; ++i) {
tmp = array[i+1];
array[i+1] = val_forward;
val_forward = tmp;
}
array[0] = val_forward;
}
int main() {
// size of 2-dim square matrix.
uint32_t sq_matrix_size = 0;
cin >> sq_matrix_size;
int mid_value = 0; // needed if odd size
int mid_point = sq_matrix_size/2 + 1;
int circle_count = 0;
// allocate memory based on the size
int **circle_arrays = new int*[MAX_CIRCLE_COUNT]();
matrix_spec **sq_matrix = Allocate2dSquareMatrix<matrix_spec>(sq_matrix_size);
if (sq_matrix_size < 10) { // limit to eliminate human error.
// determine number of circle.
int tmp_size = sq_matrix_size;
while (true) {
if (tmp_size == 1) {
circle_arrays[circle_count] = &mid_value;
sq_matrix[mid_point][mid_point].circle_idx = 100;
break;
} else if (tmp_size < 1) {
break;
}
// allocate circle array
int array_size = tmp_size*2 + ((tmp_size-2)*2);
circle_arrays[circle_count] = new int[array_size]();
int array_idx_count = 0;
int row = 0, col = 0;
for (int i = 0; i < array_size; ++i) {
sq_matrix[(row+circle_count)][(col+circle_count)].circle_idx = circle_count;
sq_matrix[(row+circle_count)][(col+circle_count)].array_idx = array_idx_count++;
//cout << "[ row: " << row << ", col: " << col << ", array:" << circle_count << ", index:" << array_idx_count-1 << "]" << endl;
if (row == 0 && col < (tmp_size-1)) {
col++;
} else if (col == (tmp_size-1) && row < (tmp_size-1)) {
row++;
} else if (row == (tmp_size-1) && col > 0) {
col--;
} else if (col == 0 && row > 0) {
row--;
}
}
cout << endl;
tmp_size -= 2;
circle_count++;
}
}
// Fill up the allocated memory with user's input.
int user_in = 0;
for (int i = 0; i < sq_matrix_size; ++i) {
for (int j = 0; j < sq_matrix_size; ++j) {
cin >> user_in;
int *array = circle_arrays[sq_matrix[i][j].circle_idx];
array[sq_matrix[i][j].array_idx] = user_in;
//cout << "i:" << i << ", j: "<< j << ", array_idx:" << sq_matrix[i][j].circle_idx << ", element_idx:" << sq_matrix[i][j].array_idx << endl;
}
}
// move arrays by 1 position
for (int i = 0; i < circle_count; ++i) {
int tmp_size = sq_matrix_size - (2*i);
int array_size = tmp_size*2 + ((tmp_size-2)*2);
RotateArray(circle_arrays[i], array_size);
}
// final printout
for (int i = 0; i < sq_matrix_size; ++i) {
for (int j = 0; j < sq_matrix_size; ++j) {
if (sq_matrix[i][j].circle_idx == 100) {
cout << mid_value;
} else {
int *array = circle_arrays[sq_matrix[i][j].circle_idx];
cout << array[sq_matrix[i][j].array_idx] << " ";
}
}
cout << endl;
}
// cleaning up the memory
Deallocate2dSquareMatrix<matrix_spec>(sq_matrix, sq_matrix_size);
for (int i =0 ; i < circle_count; ++i) {
delete[] circle_arrays[i];
}
return 0;
}
{
/* Given a 2-dimensional square matrix, rotate the matrix clockwise.
* Imagine concentric circles. Input from stdin: first line is length,
* subsequent lines are rows of the matrix. Output the matrix to stdout.
* You have 2 hrs to complete it.
*/
#include <iostream>
#include <string>
#include <cstdlib>
#include <stdint.h>
using namespace std;
#define MAX_CIRCLE_COUNT 10
struct matrix_spec {
int circle_idx;
int array_idx;
};
template <typename T>
T **Allocate2dSquareMatrix(int size) {
T **array_2d = new T*[size]();
for (int i = 0; i < size; ++i) {
array_2d[i] = new T[size]();
}
return array_2d;
}
template <typename T>
void Deallocate2dSquareMatrix(T **array_2d, int size) {
for (int i = 0; i < size; ++i) {
delete[] array_2d[i];
}
delete[] array_2d;
}
void RotateArray(int *array, int size) {
int val_forward = array[0];
int tmp = 0;
for (int i = 0; i < size-1; ++i) {
tmp = array[i+1];
array[i+1] = val_forward;
val_forward = tmp;
}
array[0] = val_forward;
}
int main() {
// size of 2-dim square matrix.
uint32_t sq_matrix_size = 0;
cin >> sq_matrix_size;
int mid_value = 0; // needed if odd size
int mid_point = sq_matrix_size/2 + 1;
int circle_count = 0;
// allocate memory based on the size
int **circle_arrays = new int*[MAX_CIRCLE_COUNT]();
matrix_spec **sq_matrix = Allocate2dSquareMatrix<matrix_spec>(sq_matrix_size);
if (sq_matrix_size < 10) { // limit to eliminate human error.
// determine number of circle.
int tmp_size = sq_matrix_size;
while (true) {
if (tmp_size == 1) {
circle_arrays[circle_count] = &mid_value;
sq_matrix[mid_point][mid_point].circle_idx = 100;
break;
} else if (tmp_size < 1) {
break;
}
// allocate circle array
int array_size = tmp_size*2 + ((tmp_size-2)*2);
circle_arrays[circle_count] = new int[array_size]();
int array_idx_count = 0;
int row = 0, col = 0;
for (int i = 0; i < array_size; ++i) {
sq_matrix[(row+circle_count)][(col+circle_count)].circle_idx = circle_count;
sq_matrix[(row+circle_count)][(col+circle_count)].array_idx = array_idx_count++;
//cout << "[ row: " << row << ", col: " << col << ", array:" << circle_count << ", index:" << array_idx_count-1 << "]" << endl;
if (row == 0 && col < (tmp_size-1)) {
col++;
} else if (col == (tmp_size-1) && row < (tmp_size-1)) {
row++;
} else if (row == (tmp_size-1) && col > 0) {
col--;
} else if (col == 0 && row > 0) {
row--;
}
}
cout << endl;
tmp_size -= 2;
circle_count++;
}
}
// Fill up the allocated memory with user's input.
int user_in = 0;
for (int i = 0; i < sq_matrix_size; ++i) {
for (int j = 0; j < sq_matrix_size; ++j) {
cin >> user_in;
int *array = circle_arrays[sq_matrix[i][j].circle_idx];
array[sq_matrix[i][j].array_idx] = user_in;
//cout << "i:" << i << ", j: "<< j << ", array_idx:" << sq_matrix[i][j].circle_idx << ", element_idx:" << sq_matrix[i][j].array_idx << endl;
}
}
// move arrays by 1 position
for (int i = 0; i < circle_count; ++i) {
int tmp_size = sq_matrix_size - (2*i);
int array_size = tmp_size*2 + ((tmp_size-2)*2);
RotateArray(circle_arrays[i], array_size);
}
// final printout
for (int i = 0; i < sq_matrix_size; ++i) {
for (int j = 0; j < sq_matrix_size; ++j) {
if (sq_matrix[i][j].circle_idx == 100) {
cout << mid_value;
} else {
int *array = circle_arrays[sq_matrix[i][j].circle_idx];
cout << array[sq_matrix[i][j].array_idx] << " ";
}
}
cout << endl;
}
// cleaning up the memory
Deallocate2dSquareMatrix<matrix_spec>(sq_matrix, sq_matrix_size);
for (int i =0 ; i < circle_count; ++i) {
delete[] circle_arrays[i];
}
return 0;
}
}
int main()
{
int **arr = NULL;
int temp = 0;
int len = 0;
int i = 0;
int j = 0;
int k = 0 ;
int l = 0;
printf("Enter the length of Squre array:\n");
scanf("%d",&len);
printf("matrix: %dX%d\n",len,len);
arr = (int**)malloc(sizeof(int*) * len);
if(NULL == arr)
{
printf("Unable to allocate array memory\n");
}
for(i = 0 ; i < len; i++)
{
arr[i] = (int*)malloc(sizeof(int) * len);
if(NULL == arr[i])
{
printf("Unable to allocate array column memory\n");
}
}
printf("Enter the element of Squre array:\n");
for(i= 0 ; i<len; i++)
{
for(j=0; j<len; j++)
scanf("%d",&arr[i][j]);
}
for(i= 0 ; i<len; i++)
{
for(j=0; j<len; j++)
printf("%d ",arr[i][j]);
printf("\n");
}
printf("concentric circle Squre array:\n");
int len1= len;
for(i=0;i<(len1/2);i++)
{
temp = arr[i][i];
for(k = i; k<len-1; k++)
{
arr[k][i] = arr[k+1][i];
}
for(l= i ; l<len-1; l++)
{
arr[k][l] = arr[k][l+1];
}
for(k; k > i; k--)
{
arr[k][l] = arr[k-1][l];
}
for(l; l>i;l--)
{
arr[k][l]= arr[k][l-1];
}
arr[k][l+1] = temp;
len = len-1;
}
for(i= 0 ; i<len1; i++)
{
for(j=0; j<len1; j++)
printf("%d ",arr[i][j]);
printf("\n");
}
}
#include<stdio.h>
#include<stdlib.h>
int main()
{
int **arr = NULL;
int temp = 0;
int len = 0;
int i = 0;
int j = 0;
int k = 0 ;
int l = 0;
printf("Enter the length of Squre array:\n");
scanf("%d",&len);
printf("matrix: %dX%d\n",len,len);
arr = (int**)malloc(sizeof(int*) * len);
if(NULL == arr)
{
printf("Unable to allocate array memory\n");
}
for(i = 0 ; i < len; i++)
{
arr[i] = (int*)malloc(sizeof(int) * len);
if(NULL == arr[i])
{
printf("Unable to allocate array column memory\n");
}
}
printf("Enter the element of Squre array:\n");
for(i= 0 ; i<len; i++)
{
for(j=0; j<len; j++)
scanf("%d",&arr[i][j]);
}
for(i= 0 ; i<len; i++)
{
for(j=0; j<len; j++)
printf("%d ",arr[i][j]);
printf("\n");
}
printf("concentric circle Squre array:\n");
int len1= len;
for(i=0;i<(len1/2);i++)
{
temp = arr[i][i];
for(k = i; k<len-1; k++)
{
arr[k][i] = arr[k+1][i];
}
for(l= i ; l<len-1; l++)
{
arr[k][l] = arr[k][l+1];
}
for(k; k > i; k--)
{
arr[k][l] = arr[k-1][l];
}
for(l; l>i;l--)
{
arr[k][l]= arr[k][l-1];
}
arr[k][l+1] = temp;
len = len-1;
}
for(i= 0 ; i<len1; i++)
{
for(j=0; j<len1; j++)
printf("%d ",arr[i][j]);
printf("\n");
}
}
package Amazon;
import java.util.Scanner;
public class SpiralRotateMat {
static int mat[][];
static int dim;
public static void main(String args[]){
parseInput();
System.out.println("Input matrix: ");
for(int i=0;i<dim;i++){
for(int j=0;j<dim;j++){
System.out.print(mat[i][j]+" ");
}
System.out.println();
}
rotate();
System.out.println("Rotated matrix: ");
for(int i=0;i<dim;i++){
for(int j=0;j<dim;j++){
System.out.print(mat[i][j]+" ");
}
System.out.println();
}
}
static void parseInput(){
Scanner scn = new Scanner(System.in);
System.out.print("Enter the dimension of matrix: ");
dim = scn.nextInt();
mat = new int[dim][dim];
for(int i=0;i<dim;i++){
for(int j=0;j<dim;j++){
mat[i][j]=scn.nextInt();
}
}
}
static void rotate(){
char dir = 'R';
int T=0, L=0, B=dim-1, R=dim-1;
int temp=0, prev=0, i=0, noOfRot = 1;
while(noOfRot <= dim/2){
switch(dir){
case('R'):
{
for(i=L;i<=R;i++){
temp = mat[T][i];
mat[T][i] = prev;
prev = temp;
//System.out.print(mat[T][i]+" ");
}
T=T+1;
dir = 'B';
break;
}
case('B'):
{
for(i=T;i<=B;i++){
temp = mat[i][R];
mat[i][R] = prev;
prev = temp;
// System.out.print(mat[i][R]+" ");
}
R=R-1;
dir = 'L';
break;
}
case('L'):
{
for(i=R;i>=L;i--){
temp = mat[B][i];
mat[B][i] = prev;
prev = temp;
//System.out.print(mat[B][i]+" ");
}
B=B-1;
dir = 'T';
break;
}
case('T'):
{
for(i=B;i>=T;i--){
temp = mat[i][L];
mat[i][L] = prev;
prev = temp;
//System.out.print(mat[i][L]+" ");
}
mat[i][L] = prev;
L=L+1;
noOfRot++;
dir = 'R';
break;
}
}
}
}
}
package Amazon;
import java.util.Scanner;
public class SpiralRotateMat {
static int mat[][];
static int dim;
public static void main(String args[]){
parseInput();
System.out.println("Input matrix: ");
for(int i=0;i<dim;i++){
for(int j=0;j<dim;j++){
System.out.print(mat[i][j]+" ");
}
System.out.println();
}
rotate();
System.out.println("Rotated matrix: ");
for(int i=0;i<dim;i++){
for(int j=0;j<dim;j++){
System.out.print(mat[i][j]+" ");
}
System.out.println();
}
}
static void parseInput(){
Scanner scn = new Scanner(System.in);
System.out.print("Enter the dimension of matrix: ");
dim = scn.nextInt();
mat = new int[dim][dim];
for(int i=0;i<dim;i++){
for(int j=0;j<dim;j++){
mat[i][j]=scn.nextInt();
}
}
}
static void rotate(){
char dir = 'R';
int T=0, L=0, B=dim-1, R=dim-1;
int temp=0, prev=0, i=0, noOfRot = 1;
while(noOfRot <= dim/2){
switch(dir){
case('R'):
{
for(i=L;i<=R;i++){
temp = mat[T][i];
mat[T][i] = prev;
prev = temp;
//System.out.print(mat[T][i]+" ");
}
T=T+1;
dir = 'B';
break;
}
case('B'):
{
for(i=T;i<=B;i++){
temp = mat[i][R];
mat[i][R] = prev;
prev = temp;
// System.out.print(mat[i][R]+" ");
}
R=R-1;
dir = 'L';
break;
}
case('L'):
{
for(i=R;i>=L;i--){
temp = mat[B][i];
mat[B][i] = prev;
prev = temp;
//System.out.print(mat[B][i]+" ");
}
B=B-1;
dir = 'T';
break;
}
case('T'):
{
for(i=B;i>=T;i--){
temp = mat[i][L];
mat[i][L] = prev;
prev = temp;
//System.out.print(mat[i][L]+" ");
}
mat[i][L] = prev;
L=L+1;
noOfRot++;
dir = 'R';
break;
}
}
}
}
}
int rowStart = 0;
int rowEnd = m;
int colStart = 0;
int colEnd = n;
int i ,j;
int tempRowStart , tempColStart;
int temp;
int prev;
while(rowStart < rowEnd && colStart < colEnd){
tempRowStart = rowStart;
tempColStart = colStart;
prev = a[rowStart][colStart];
for(i = colStart+1 ; i<colEnd; i++){
temp = a[rowStart][i];
a[rowStart][i] =prev;
prev = temp;
}
rowStart++;
for(j = rowStart; j < rowEnd; j++){
temp = a[j][colEnd-1];
a[j][colEnd-1] = prev;
prev = temp;
}
colEnd--;
if(rowStart <rowEnd){
for(j = colEnd -1;j>=colStart;j--){
temp = a[rowEnd -1 ][j];
a[rowEnd -1 ][j] = prev;
prev = temp;
}
rowEnd--;
}
if(colStart<colEnd){
for(i = rowEnd -1 ; i >= rowStart; i--){
temp = a[i][colStart];
a[i][colStart] = prev;
prev = temp;
}
colStart++;
}
a[tempRowStart][tempColStart] = prev;
}
int rowStart = 0;
int rowEnd = m;
int colStart = 0;
int colEnd = n;
int i ,j;
int tempRowStart , tempColStart;
int temp;
int prev;
while(rowStart < rowEnd && colStart < colEnd){
tempRowStart = rowStart;
tempColStart = colStart;
prev = a[rowStart][colStart];
for(i = colStart+1 ; i<colEnd; i++){
temp = a[rowStart][i];
a[rowStart][i] =prev;
prev = temp;
}
rowStart++;
for(j = rowStart; j < rowEnd; j++){
temp = a[j][colEnd-1];
a[j][colEnd-1] = prev;
prev = temp;
}
colEnd--;
if(rowStart <rowEnd){
for(j = colEnd -1;j>=colStart;j--){
temp = a[rowEnd -1 ][j];
a[rowEnd -1 ][j] = prev;
prev = temp;
}
rowEnd--;
}
if(colStart<colEnd){
for(i = rowEnd -1 ; i >= rowStart; i--){
temp = a[i][colStart];
a[i][colStart] = prev;
prev = temp;
}
colStart++;
}
a[tempRowStart][tempColStart] = prev;
}
public class RotateMatrix {
public static void display2DimArray(int[][] arr, int m, int n) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.print("\n");
}
}
public static void rotate2DimArray(int[][] arr, int m, int n) {
if (m != n) {
System.out.println("Not a square matrix");
return;
}
int center = m/2;
int cur = 0;
while (cur < center) {
int temp1 = arr[cur][n-1-cur];
for (int i = n-1-cur; i > cur; i--) {
arr[cur][i] = arr[cur][i-1];
}
int temp2 = arr[m-1-cur][n-1-cur];
for (int i = m-1-cur; i > 1+cur; i--) {
arr[i][n-1-cur] = arr[i-1][n-1-cur];
}
arr[cur+1][n-1-cur] = temp1;
temp1 = arr[m-1-cur][cur];
for (int i = cur; i < n-1-cur; i++) {
arr[m-1-cur][i] = arr[m-1-cur][i+1];
}
arr[m-1-cur][n-2-cur] = temp2;
for (int i = cur; i < m-2-cur; i++) {
arr[i][cur] = arr[i+1][cur];
}
arr[m-2-cur][cur] = temp1;
cur++;
}
}
public static void main(String[] args) {
// int[][] a = new int [][]{
// {1, 2},
// {3, 4}};
int[][] a = new int [][]{
{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}};
int m = a.length;
int n = a[0].length;
display2DimArray(a, m, n);
rotate2DimArray(a, m, n);
System.out.println("================");
display2DimArray(a, m, n);
rotate2DimArray(a, m, n);
System.out.println("================");
display2DimArray(a, m, n);
}
}
public class RotateMatrix {
public static void display2DimArray(int[][] arr, int m, int n) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.print("\n");
}
}
public static void rotate2DimArray(int[][] arr, int m, int n) {
if (m != n) {
System.out.println("Not a square matrix");
return;
}
int center = m/2;
int cur = 0;
while (cur < center) {
int temp1 = arr[cur][n-1-cur];
for (int i = n-1-cur; i > cur; i--) {
arr[cur][i] = arr[cur][i-1];
}
int temp2 = arr[m-1-cur][n-1-cur];
for (int i = m-1-cur; i > 1+cur; i--) {
arr[i][n-1-cur] = arr[i-1][n-1-cur];
}
arr[cur+1][n-1-cur] = temp1;
temp1 = arr[m-1-cur][cur];
for (int i = cur; i < n-1-cur; i++) {
arr[m-1-cur][i] = arr[m-1-cur][i+1];
}
arr[m-1-cur][n-2-cur] = temp2;
for (int i = cur; i < m-2-cur; i++) {
arr[i][cur] = arr[i+1][cur];
}
arr[m-2-cur][cur] = temp1;
cur++;
}
}
public static void main(String[] args) {
// int[][] a = new int [][]{
// {1, 2},
// {3, 4}};
int[][] a = new int [][]{
{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}};
int m = a.length;
int n = a[0].length;
display2DimArray(a, m, n);
rotate2DimArray(a, m, n);
System.out.println("================");
display2DimArray(a, m, n);
rotate2DimArray(a, m, n);
System.out.println("================");
display2DimArray(a, m, n);
}
}
import java.util.Scanner;
public class RotateMatrix {
public static void display2DimArray(int[][] arr, int m, int n) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.print("\n");
}
}
public static void rotate2DimArray(int[][] arr, int m, int n) {
if (m != n) {
System.out.println("Not a square matrix");
return;
}
int center = m/2;
int cur = 0;
while (cur < center) {
int temp1 = arr[cur][n-1-cur];
for (int i = n-1-cur; i > cur; i--) {
arr[cur][i] = arr[cur][i-1];
}
int temp2 = arr[m-1-cur][n-1-cur];
for (int i = m-1-cur; i > 1+cur; i--) {
arr[i][n-1-cur] = arr[i-1][n-1-cur];
}
arr[cur+1][n-1-cur] = temp1;
temp1 = arr[m-1-cur][cur];
for (int i = cur; i < n-1-cur; i++) {
arr[m-1-cur][i] = arr[m-1-cur][i+1];
}
arr[m-1-cur][n-2-cur] = temp2;
for (int i = cur; i < m-2-cur; i++) {
arr[i][cur] = arr[i+1][cur];
}
arr[m-2-cur][cur] = temp1;
cur++;
}
}
@SuppressWarnings("resource")
public static int getIntInput() {
Scanner scanner = new Scanner(System.in);
return scanner.nextInt();
}
@SuppressWarnings("resource")
public static int[] getIntArrayInput() {
Scanner scanner = new Scanner(System.in);
String input = scanner.nextLine();
String[] parts = input.split(" ");
int ret[] = new int[parts.length];
for (int i = 0; i < parts.length; i++) {
ret[i] = Integer.parseInt(parts[i]);
}
return ret;
}
public static void main(String[] args) {
int arr[][] = null;
System.out.println("Enter the length of the square matrix:");
int dimension = getIntInput();
arr = new int[dimension][];
for (int i = 0; i < dimension; i++) {
System.out.println("Enter " + (i+1) + "th row:");
arr[i] = getIntArrayInput();
}
int m = dimension;
int n = dimension;
display2DimArray(arr, m, n);
rotate2DimArray(arr, m, n);
System.out.println("================");
display2DimArray(arr, m, n);
rotate2DimArray(arr, m, n);
System.out.println("================");
display2DimArray(arr, m, n);
}
}
- MehrdadAP September 02, 2015#include <iostream> #include <vector> using namespace std; vector< vector<int> > rotate(vector< vector<int> > matrix) { int N=matrix.size(); vector< vector<int> > rotatedMatrix(N); for (int i=0;i<N;i++) rotatedMatrix[i].resize(N); for (int i=0;i<N;i++){ for (int j=0;j<N;j++){ rotatedMatrix[j][N-i-1]=matrix[i][j]; } } return rotatedMatrix; } int main() { int N; while (cin >> N){ vector< vector<int> > V(N); for (int i=0;i<N;i++){ V[i].resize(N); for (int j=0;j<N;j++) cin >> V[i][j]; } V=rotate(V); for (int i=0;i<N;i++){ for (int j=0;j<N;j++) cout << V[i][j] << " "; cout << endl; } } return 0; }