Example 1: Input: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] Output: [1,2,3,6,9,8,7,4,5]
The Solution is very simple.
As shown in the image above,
- We traverse right
- We traverse down
- We traverse left
- We traverse up
To achieve this, we take 4 variables:
rowStart = 0; rowEnd = matrix.size()-1; colStart = 0; colEnd = matrix[0].size() - 1;
In our example: rowStart = 0 rowEnd = 2 colStart = 0 colEnd = 2 To traverse right we use below code: for (int i = colStart; i <= colEnd; i ++) // print variable matrix[rowStart][i] rowStart++; To traverse down we use below code: for (int i = rowStart; i <= rowEnd; i ++) // print variable matrix[i][colEnd] colEnd--; To traverse left we use below code: for (int i = colEnd; i >= colStart; i --) // print variable matrix[rowEnd][i] rowEnd--; To traverse up we use below code: for (int i = rowEnd; i >= rowStart; i --) // print variable matrix[i][colStart] colStart ++; we run the loop untill "rowStart <= rowEnd && colStart <= colEnd"
At the end of pass 1 below elements will be entered into the result vector 1 2 3
At the end of pass 2 below elements will be entered into the result vector 1 2 3 6 9
At the end of pass 3 below elements will be entered into the result vector 1 2 3 6 9 8 7
At the end of pass 4 below elements will be entered into the result vector 1 2 3 6 9 8 7 4
At the end of pass 5 below elements will be entered into the result vector. Hence our required result. 1 2 3 6 9 8 7 4 5
#include<iostream> #include<vector> using namespace std; vector<int> get_spiral(vector<vector<int> > &matrix) { vector<int> result; int rowStart = 0; int rowEnd = matrix.size()-1; int colStart = 0; int colEnd = matrix[0].size() - 1; int dir = 1; int j = 1; while (rowStart <= rowEnd && colStart <= colEnd) { if (dir == 1) { // left to right for (int i = colStart; i <= colEnd; ++i) { result.push_back(matrix[rowStart][i]); } ++rowStart; dir = 2; } else if (dir == 2) { // top to bottom for (int i = rowStart; i <= rowEnd; ++i) { result.push_back(matrix[i][colEnd]); } --colEnd; dir = 3; } else if (dir == 3) { // right to left for (int i = colEnd; i >= colStart; --i) { result.push_back(matrix[rowEnd][i]); } --rowEnd; dir = 4; } else if (dir == 4) { // bottom to up for (int i = rowEnd; i >= rowStart; --i) { result.push_back(matrix[i][colStart]); } ++colStart; dir = 1; } j++; } return result; } int main() { //Declare a 2d array vector<vector<int> > myMatrix; int row = 3; int column = 3; std::vector<int > result; int temp = 1; // variable to put the values in to vector //populate the array for(int i=0; i < row; i++) { //create a temp vector, it will act as a row vector<int> temp_vector; for(int i=0; i<column; i++) { temp_vector.push_back(temp); temp++; } // push the content of temp vector to the main vector myMatrix.push_back(temp_vector); } cout<< "Entered vector is : "<<endl; for (int i = 0; i < row; i++) { for (int j = 0; j < column; j++) cout << myMatrix[i][j] << ' '; cout << endl; } result = get_spiral(myMatrix); cout<< "The matrix in spiral order is : "<<endl; for (int i = 0; i < result.size(); i++) { cout << result[i] << ' '; } cout<<endl; return 0; }
Output:
Entered vector is : 1 2 3 4 5 6 7 8 9 The matrix in spiral order is : 1 2 3 6 9 8 7 4 5
No Responses