Blog

54. Spiral Matrix – Solution [Brute-Force to Best]

Here’s the question link on LeetCode 54. Spiral Matrix:

https://leetcode.com/problems/spiral-matrix/description

Brute Force [Space – O(m × n)]

My first thought is pretty straightforward.

I can start from the top-left corner and move right. Once I reach the boundary, I turn down, then left, then up.

But how do I know whether I’ve already visited an element?

I can maintain another matrix of the same size to keep track of visited elements.

Whenever I visit an element, I mark it as visited.

If the next position is either outside the matrix or already visited, I simply change direction.

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();

        vector<vector<bool>> vis(m, vector<bool>(n, false));

        vector<int> ans;

        // Right, Down, Left, Up
        int dr[] = {0, 1, 0, -1};
        int dc[] = {1, 0, -1, 0};

        int r = 0, c = 0, dir = 0;

        for(int i = 0; i < m * n; i++) {
            ans.push_back(matrix[r][c]);
            vis[r][c] = true;

            int nr = r + dr[dir];
            int nc = c + dc[dir];

            if(nr < 0 || nr >= m || nc < 0 || nc >= n || vis[nr][nc]) {
                dir = (dir + 1) % 4;
            }

            r += dr[dir];
            c += dc[dir];
        }

        return ans;
    }
};
54. Spiral Matrix solution brute force space

Wait a minute. Do we really need another matrix just to track visited elements?

Think about it.

Instead of checking whether we’ve visited an element, we can simply maintain four boundaries:

  • top = first unvisited row.
  • bottom = last unvisited row.
  • left = first unvisited column.
  • right = last unvisited column.

Initially, these boundaries cover the entire matrix.

Now we just need to traverse one boundary at a time.

Optimal [Space – O(1)]

Wait a minute. Do we really need another matrix just to track visited elements?

Think about it.

Instead of checking whether we’ve visited an element, we can simply maintain four boundaries:

  • top = first unvisited row.
  • bottom = last unvisited row.
  • left = first unvisited column.
  • right = last unvisited column.

Initially, these boundaries cover the entire matrix.

Now we just need to traverse one boundary at a time.

  1. Traverse the top row from left to right. Then move top down.
  2. Traverse the right column from top to bottom. Then move right left.
  3. Traverse the bottom row from right to left. Then move bottom up.
  4. Traverse the left column from bottom to top. Then move left right.

Repeat!

Notice that after every complete round, our boundaries shrink and we move towards the center.

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();

        int top = 0, bottom = m - 1;
        int left = 0, right = n - 1;

        vector<int> ans;

        while(top <= bottom && left <= right) {

            // Left to right
            for(int i = left; i <= right; i++)
                ans.push_back(matrix[top][i]);
            top++;

            // Top to bottom
            for(int i = top; i <= bottom; i++)
                ans.push_back(matrix[i][right]);
            right--;

            // Right to left
            if(top <= bottom) {
                for(int i = right; i >= left; i--)
                    ans.push_back(matrix[bottom][i]);
                bottom--;
            }

            // Bottom to top
            if(left <= right) {
                for(int i = bottom; i >= top; i--)
                    ans.push_back(matrix[i][left]);
                left++;
            }
        }

        return ans;
    }
};
54. Spiral Matrix solution optimal space

That’s it; see you in the next one.

Leave a Reply