Leetcode Study Day 17

Spiral Matrix

Given an m x n matrix, return all elements of the matrix in spiral order.

Example 1:


Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:


Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
 

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100

Solution

The solution is actually easy to understand. Firstly, we found the width and the height of the matrix:

int width = matrix[0].size();
int height = matrix.size();
int count = width * height;

Then we initialise four pointers for this matrix, which is up, right, down and left. We also initialise a vector to store the answer.

int left = 0, right = width - 1, up = 0, down = height - 1;
vector<int> answer;

Then we use a while loop to iterate through the matrix. We use four for loops to iterate through the matrix. The first for loop is to iterate through the top row, the second for loop is to iterate through the right column, the third for loop is to iterate through the bottom row and the last for loop is to iterate through the left column. After each for loop, we need to check if the size of the answer array is greater than the total size, if it is, we break the while loop.

while (answer.size() < count){
        for (int i = left; i <= right && answer.size() < count ; i++){
            answer.push_back(matrix[up][i]);
        }
        for (int i = up + 1; i <= down - 1 && answer.size() < count; i++){
            answer.push_back(matrix[i][right]);
        }
        for (int i = right; i >= left && answer.size() < count; i--){
            answer.push_back(matrix[down][i]);
        }
        for (int i = down - 1; i >= up + 1 && answer.size() < count; i--){
            answer.push_back(matrix[i][left]);
        }            
        left ++;
        right --;
        up ++;
        down --;
    }

Finally, we return our answer array.

Full code

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int width = matrix[0].size();
        int height = matrix.size();
        int count = width * height;
        int left = 0, right = width - 1, up = 0, down = height - 1;
        vector<int> answer;
        while (answer.size() < count){
            for (int i = left; i <= right && answer.size() < count ; i++){
                answer.push_back(matrix[up][i]);
            }
            for (int i = up + 1; i <= down - 1 && answer.size() < count; i++){
                answer.push_back(matrix[i][right]);
            }
            for (int i = right; i >= left && answer.size() < count; i--){
                answer.push_back(matrix[down][i]);
            }
            for (int i = down - 1; i >= up + 1 && answer.size() < count; i--){
                answer.push_back(matrix[i][left]);
            }            
            left ++;
            right --;
            up ++;
            down --;
        }
        return answer;
    }
};