Interview Classic 150 Questions P54 Spiral Matrix

---

Timeline

Timeline

2025-11-16

init

Matrix

---

Problem:

P54 Spiral Matrix

https://leetcode.cn/problems/spiral-matrix/description/?envType=study-plan-v2&envId=top-interview-150

Note that if you don’t use the comparison between cnt and total to determine whether to end, duplicates will be added when there is only one row or only one column.

#include <vector>
using std::vector;

class Solution {
    public:
	bool spiral_edge(vector<vector<int> > &matrix, vector<int> &res, int curr_m, int curr_n, int start_i,
			 int start_j)
	{
		int i = start_i, j = start_j;
		int cnt = 0, total = curr_m * curr_n;

		if (curr_m <= 0 || curr_n <= 0) {
			return false;
		}
		// From (start_i,start_j) start, length curr_m,curr_n
		for (i = start_i, j = start_j; j < start_j + curr_n; j++) {
			res.push_back(matrix[i][j]);
			cnt++;
		}
		if (cnt == total) {
			return true;
		}
		for (i = start_i + 1, j = start_j + curr_n - 1; i < start_i + curr_m - 1; i++) {
			res.push_back(matrix[i][j]);
			cnt++;
		}
		if (cnt == total) {
			return true;
		}
		for (i = start_i + curr_m - 1, j = start_j + curr_n - 1; j >= start_j; j--) {
			res.push_back(matrix[i][j]);
			cnt++;
		}
		if (cnt == total) {
			return true;
		}
		for (i = start_i + curr_m - 2, j = start_j; i > start_i; i--) {
			res.push_back(matrix[i][j]);
			cnt++;
		}
		return true;
	}
	vector<int> spiralOrder(vector<vector<int> > &matrix)
	{
		int m = matrix.size();
		int n = matrix[0].size();
		vector<int> res;
		int curr_m = m, curr_n = n;
		int start_i = 0, start_j = 0;

		while (spiral_edge(matrix, res, curr_m, curr_n, start_i, start_j)) {
			curr_m -= 2;
			curr_n -= 2;
			start_i += 1;
			start_j += 1;
		}

		return res;
	}
};
int main()
{
	vector<vector<int> > matrix = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
	Solution S;
	S.spiralOrder(matrix);
}

leetcode hot 100 rewrite:

#include <vector>
using std::vector;

class Solution {
    public:
        vector<int> spiralOrder(vector<vector<int> > &matrix)
        {
                // 1 <= m, n <= 10
                int i, j, m = matrix.size(), n = matrix[0].size();
                vector<int> ret;
                int start_i = 0, start_j = 0;

                while (m > 0 && n > 0) {
                        if (start_j >= start_j + n)
                                break;
                        for (j = start_j; j < start_j + n; j++)
                                ret.push_back(matrix[start_i][j]);
                        j--;

                        if (start_i + 1 >= start_i + m)
                                break;
                        for (i = start_i + 1; i < start_i + m; i++)
                                ret.push_back(matrix[i][j]);
                        i--;

                        if (j - 1 < start_j)
                                break;
                        for (j = j - 1; j >= start_j; j--)
                                ret.push_back(matrix[i][j]);
                        j++;

                        if (i - 1 <= start_i)
                                break;
                        for (i = i - 1; i > start_i; i--)
                                ret.push_back(matrix[i][j]);
                        i++;

                        m -= 2;
                        n -= 2;
                        start_i++;
                        start_j++;
                }

                return ret;
        }
};

#include <stdio.h>
int main()
{
        // vector<vector<int> > matrix = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
        vector<vector<int> > matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } };
        Solution S;
        vector<int> ret = S.spiralOrder(matrix);
        for (int val : ret)
                printf("%d ", val);
}