C++ easy to understand solution with comments. 0ms O(n) with recursion


  • 0
    S

    The idea is to read the rectangular edge first and then call same function for the smaller inner rectangle.
    the edge reader does 4 steps:

    1. read top line from left to right
    2. read right edge but skip top line and bottom
    3. read bottom edge from right to left. skip if its the only line
    4. read left edge but skip bottom and top line. skip if its the only column
        /*
          Matrix samples and reading order
          3x3 (3 right, 1 down, 3 left, 1 up)
          -- -- ->
          /\    \/
          <- -- --
          
          2x2 (2 right, 2 left)
          -- ->
          <- --
          
          1x1 (1 right)
          -->
          
          1x3 (3 right)
          -- -- ->
          
          3x1 (1 right, 1 down, 1 left)
          ->
          \/
          <-
        */
        void readEdge(vector<vector<int>> &matrix, int top, int bottom, int left, int right, vector<int> &numbers)
        {
            if (top > bottom || left > right)
                return;
                
            // go over the top edge
            for (int i=left; i<=right; ++i)
                numbers.push_back(matrix[top][i]);
            
            // right edge
            for (int i=top+1; i<=(bottom-1); ++i)
                numbers.push_back(matrix[i][right]);
            
            // bottom edge
            // additional check is when we have only one row
            if (top != bottom)
                for (int i=right; i>=left; --i)
                    numbers.push_back(matrix[bottom][i]);
            
            // left edge
            // additional check is when we have only one column
            if (left != right)
                for (int i=(bottom-1); i>=(top+1); --i)
                    numbers.push_back(matrix[i][left]);
            
            readEdge(matrix, top+1, bottom-1, left+1, right-1, numbers);
        }
        
        vector<int> spiralOrder(vector<vector<int>>& matrix)
        {
            vector<int> numbers;
    
            // if matrix is empty
            if (matrix.empty() || matrix[0].empty())
                return numbers;
    
            readEdge(matrix, 0, matrix.size()-1, 0, matrix[0].size()-1, numbers);
            
            return numbers;
        }
    

Log in to reply
 

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