LeetCode 54 Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example, Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1, 2, 3, 6, 9, 8, 7, 4, 5].

Difficulty
Medium

Related Problems
[LeetCode 48] Rotate Image [LeetCode 59] Spiral Matrix II

Analysis

This is similar to Rotate Image, except here m is not necessary equal to n. the number of rings is decided by min(m, n) / 2, when min(m, n) is odd, the most inner ring has only one line.

example:

OOO    OOOO   OOO      OOOOOOOO
OXO    OXXO   OXO      OAAAAAAO
OOO    OOOO   OXO      OAXXXXAO
              OOO      OAAAAAAO
                       OOOOOOOO

Let's take this fashion

----|
|   |
|----

Since the rings are rectangle, it has first_row, last_row, first_column, last_column.

last_row : m - i - 1
last_column : n - i - 1

While we processing each ring using index i, we can get info about the above four edges of the rectangle.

e.g. When i == last_row or i == last_column, we know this ring has only one line(edge). Else, it has 4 edges, we add the numbers to our result in clockwise.

Solutions

1. Cpp solution

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

        int rings = (min(m, n) + 1) / 2;
        for(int i = 0; i < rings; i++){

            int lastRow = m - i - 1;
            int lastCol = n - i - 1;

            if(i == lastRow){
                for(int j = i; j <= lastCol; j++){
                    res.push_back(matrix[i][j]);
                }
            } else if(i == lastCol){
                for(int j = i; j <= lastRow; j++){
                    res.push_back(matrix[j][i]);
                }
            } else {
                for(int j = i; j < lastCol; j++){
                    res.push_back(matrix[i][j]);
                }

                for(int j = i; j < lastRow; j++){
                    res.push_back(matrix[j][lastCol]);
                }

                for(int j = lastCol; j > i; j--){
                    res.push_back(matrix[lastRow][j]);
                }

                for(int j = lastRow; j > i; j--){
                    res.push_back(matrix[j][i]);
                }
            }
        }
        return res;
    }
};

1. Go solution

func spiralOrder(matrix [][]int) []int {
    m := len(matrix)
    if m == 0 {
        return nil
    }
    n := len(matrix[0])
    if n == 0 {
        return nil
    }

    rings := (min(m, n) + 1) / 2

    res := make([]int, 0, m*n)
    for i := 0; i < rings; i++ {
        last_row, last_column := m-i-1, n-i-1
        if i == last_row {
            for j := i; j <= last_column; j++ {
                res = append(res, matrix[i][j])
            }
        } else if i == last_column {
            for j := i; j <= last_row; j++ {
                res = append(res, matrix[j][i])
            }
        } else {
            for j := i; j < last_column; j++ { // first row
                res = append(res, matrix[i][j])
            }
            for j := i; j < last_row; j++ { // last column
                res = append(res, matrix[j][last_column])
            }
            for j := last_column; j > i; j-- {
                res = append(res, matrix[last_row][j]) // last row
            }
            for j := last_row; j > i; j-- { // first column
                res = append(res, matrix[j][i])
            }
        }
    }

    return res
}

func min(a, b int) int {
    return int(math.Min(float64(a), float64(b)))
}

Reference