A concise C++ implementation based on Directions


  • 85
    S

    When traversing the matrix in the spiral order, at any time we follow one out of the following four directions: RIGHT DOWN LEFT UP. Suppose we are working on a 5 x 3 matrix as such:

    0 1 2 3 4 5
    6 7 8 9 10
    11 12 13 14 15

    Imagine a cursor starts off at (0, -1), i.e. the position at '0', then we can achieve the spiral order by doing the following:

    1. Go right 5 times
    2. Go down 2 times
    3. Go left 4 times
    4. Go up 1 times.
    5. Go right 3 times
    6. Go down 0 times -> quit

    Notice that the directions we choose always follow the order 'right->down->left->up', and for horizontal movements, the number of shifts follows:{5, 4, 3}, and vertical movements follows {2, 1, 0}.

    Thus, we can make use of a direction matrix that records the offset for all directions, then an array of two elements that stores the number of shifts for horizontal and vertical movements, respectively. This way, we really just need one for loop instead of four.

    Another good thing about this implementation is that: If later we decided to do spiral traversal on a different direction (e.g. Counterclockwise), then we only need to change the Direction matrix; the main loop does not need to be touched.

    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<vector<int> > dirs{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        vector<int> res;
        int nr = matrix.size();     if (nr == 0) return res;
        int nc = matrix[0].size();  if (nc == 0) return res;
        
        vector<int> nSteps{nc, nr-1};
        
        int iDir = 0;   // index of direction.
        int ir = 0, ic = -1;    // initial position
        while (nSteps[iDir%2]) {
            for (int i = 0; i < nSteps[iDir%2]; ++i) {
                ir += dirs[iDir][0]; ic += dirs[iDir][1];
                res.push_back(matrix[ir][ic]);
            }
            nSteps[iDir%2]--;
            iDir = (iDir + 1) % 4;
        }
        return res;
    }

  • -1
    L

    Hi stellari,
    Do you know how to get the index of the kth element in spiral order of a 2D m x n array in O(1) time?
    such as 3 x 3 array

    int A[3][3] = {
                 {1, 2, 3},
                 {8, 9, 4},
                 {7, 6, 5}
    }
    

    For the 4th element, the index is (1,2), 9th index is (1, 1)

    Thanks!


  • 1
    S

    Hi, stellari, this is the cleanest version I have ever seen. from 1p3a.


  • 1
    H

    brilliant solution.


  • 0
    B

    This is really good.


  • 0
    Y

    vector<int> nSteps{nc, nr-1} and nSteps[iDir%2]-- is the key observation. Concise, Clean, Great.


  • 0

    Very beautiful solution, thanks for sharing!


  • 0

    There is an equation for your question:

    2(m+n)+4-8r

    the r here is the rth of the spiral, you can map the top-left corner of the spiral by this equation and then get the index pair in constant time.


  • 0
    P

    @stellari : This is such a great answer!! It took me so long to write my own answer. Your approach makes it look so easy. I just want to point out that you don't really need this line:

    if (nc == 0) return res;
    

    because if row is 0, then column check is not needed coz if row is non zero, column can never be zero. Just something i wanted to share as it struck me while writing one of my programs.


  • 1
    S

    @pb1771 Thank you for your compliment. I intentionally put "if (nc == 0) return res;" there so that this line stays visually symmetrical with the previous line. For me, aesthetics matters as much as practicality :)
    Also, the reason why "nc == 0" is indeed not necessary here, is not because this situation does not happen, but because when it happens, it can be automagically handled by the while loop. Since the matrix is represented as a vector of vectors, it is entirely possible that we may get a vector of a bunch of EMPTY vectors. Our code must be robust to this case; Another reason is that empty matrix may have a non-zero dimension. if you have worked with mathematical software like MATLAB, you will see something like "10 by 0 matrix". So it is better we can get that covered.


  • 0
    P

    @stellari Wow!! I am so glad that that i wrote that comment. Thank you so much for pointing this out. I will keep this in mind next time I write my code. Keep posting awesome answers :)


  • 0
    J

    awesome!!! very clean


  • 5
    C

    thank you so much for sharing, here is a Java version:

    public class Solution {
        public List<Integer> spiralOrder(int[][] matrix) {
            List<Integer> res = new ArrayList<Integer>();
            //
            int m = matrix.length;
            if(m == 0) return res;
            int n = matrix[0].length;
            if(n == 0) return res;
            //
            int[][] dirMatrix = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
            int[] range = {n, m-1};
            int dir = 0;           // index of dirMatrix, 0: right, 1: down, 2: left, 3: up
            int row = 0, col = -1; // initial position
            
            while(range[dir%2] != 0){
                for(int i = 0; i < range[dir%2]; i += 1){
                    row += dirMatrix[dir][0];
                    col += dirMatrix[dir][1];
                    res.add(matrix[row][col]);
                }
                
                range[dir%2] -= 1;
                dir = (dir + 1) % 4;
            }
            
            return res;
            
        }
    }
    

  • 0
    C

    Elegant, concise, readable, generic ! Super !


  • 1

    Great solution. I used a similar idea but closing in the walls instead of using a step pattern. Here it is in JavaScript:

    var spiralOrder = function(matrix) {
        if (!matrix.length) return [];
        const res = [];
        let dir, dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]];
        const walls = [-1, matrix[0].length, matrix.length, -1];
        for (let i = 0, d = 0, r = 0, c = 0, len = matrix.length * matrix[0].length; i < len; i++, r += dir[0], c += dir[1]) {
            res.push(matrix[r][c]);
            dir = dirs[d % 4];
            let w = [0, 1, 2, 3].find(j => j % 2 === 0 && r + dir[0] === walls[j] || j % 2 && c + dir[1] === walls[j]);
            if (w !== undefined) {
                walls[(w + 3) % 4] += w < 2 ? 1 : -1;
                dir = dirs[++d % 4];
            }
        }
        return res;
    };
    

    I like yours better, @stellari .


  • 0
    S

    A not so concise but straightforward one:

    enum class Direction
    {
        Up,
        Down,
        Left,
        Right
    };
    class Solution {
    public:
        vector<int> spiralOrder(vector<vector<int>>& matrix) {
            if (matrix.empty() || matrix[0].empty())
                return std::vector<int>();
            int minRow = 0, minCol = 0;
            int maxCol = (int)matrix[0].size() - 1, maxRow = (int)matrix.size() - 1;
            Direction dir = Direction::Right;
            int row = 0, col = 0;
            std::vector<int> spiral;
            while (maxRow >= minRow && maxCol >= minCol){
                spiral.push_back(matrix[row][col]);
                // determine next valid position according to current direction and position
                switch(dir){
                    case Direction::Right:
                        if (col == maxCol){
                            dir = Direction::Down;
                            row++;
                            minRow++;
                        }else{
                            col++;
                        }
                        break;
                    case Direction::Down:
                        if (row == maxRow){
                            dir = Direction::Left;
                            col--;
                            maxCol--;
                        }else{
                            row++;
                        }
                        break;
                    case Direction::Left:
                        if (col == minCol){
                            dir = Direction::Up;
                            row--;
                            maxRow--;
                        }else{
                            col--;
                        }
                        break;
                    case Direction::Up:
                        if (row == minRow){
                            dir = Direction::Right;
                            col++;
                            minCol++;
                        }else{
                            row--;
                        }
                        break;
                }
            }
            
            return spiral;
        }
    };

  • 0
    A

    We could just use two variables to track how many rows and columns are left, instead of using an extra list/vector.
    My code is in C#

    public class Solution {
        public IList<int> SpiralOrder(int[,] matrix) {
            if(matrix == null) { return null; }
            IList<int> nums = new List<int>();
            int m = matrix.GetLength(0), n = matrix.GetLength(1);
            int[,] dirts = new int[,] { {0, 1}, {1, 0}, {0, -1}, {-1, 0}};  // four possible directions
            int dirt = 0, x = 0, y = -1, count = n;  // initial direction, position, count
                for (int i=0; i<count; i++){
                    x += dirts[dirt, 0];
                    y += dirts[dirt, 1];
                    nums.Add(matrix[x, y]);   
                }
                count = dirt%2==0 ? --m : --n;  // if even number then one row was done, otherwise a column
                dirt = (dirt+1)%4;  // change direction
            }
            return nums;
        }
    }
    

  • 0
    F

    Love the solution. I rewrote it in Python (and gave it some sane variable names):

    class Solution(object):
        def spiralOrder(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: List[int]
            """
            result = []
            if not matrix or not matrix[0]:
                return result
            compass = ((0, 1), (1, 0), (0, -1), (-1, 0))
            direction = 0
            steps = [len(matrix[0]), len(matrix) - 1]
            row, col = 0, -1
            while steps[direction%2]:
                for i in range(steps[direction%2]):
                    row += compass[direction][0]
                    col += compass[direction][1]
                    result.append(matrix[row][col])
                steps[direction%2] -= 1
                direction = (direction + 1) % 4
            return result
    

  • 0
    N

    I like the idea since this is really simple and concise. In comparison with other solutions, this feels like more compact


  • 0
    M
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.