LeetCode problem 54. Spiral Matrix

Link to problem statement

Given an m x n matrix, return all elements of the matrix in spiral order.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

Example 2:

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Solution in C++

PSEUDICODE:


Input: matrix
Output: result

rowStart, rowEnd
colStart, colEnd

while rowStart <= rowEnd && colStart <= colEnd:
    for i in [colStart to colEnd]:
        add matrix[rowStart][i] to result
    increment rowStart

    for i in [rowStart to rowEnd]:
        add matrix[i][colEnd] to result
    decrement colEnd
    

    if rowStart <= RowEnd:
        for i in [colEnd to colStart]
            add matrix[rowEnd][i] to result
        decrement colEnd  

    if colStart <= colEnd:
        for i in [rowEnd to rowStart]
            add matrix[rowStart][i] to result
        increment colStart

vector<int> spiralOrder(vector<vector<int>> &matrix)
{
  // array to store the result
  // once an element is read from the matrix, it is pushed to the vector result
  vector<int> result;

  /*
    [rowStart,colStart    ..... ....  ...... rowStart,colEnd]
    [.... .... .... ..... .... .... .... ..... .... .... ...]
    [.... .... .... ..... .... .... .... ..... .... .... ...]
    [.... .... .... ..... .... .... .... ..... .... .... ...]
    [rowEnd,colStart ..... ...... ..... ...... rowEnd,colEnd]
  */

  /*
    - set the starting and end points of rows and columns,
    - following are the starting and end points at the beginning of our first loop,
    - we update these variables in each iteration of outer(while) loop
        - for example: once we reach the end of first row, we increment the
          starting row (rowStart)
        - once we reach the end of the last column, we decrement 
          the end of column (colEnd)
  */
  int rowStart = 0;
  int rowEnd = matrix.size() - 1; // at first, we go till the end of row

  int colStart = 0;
  int colEnd = matrix[0].size() - 1;

  /*
    - iterating at the following loop invarant
      we will be changing our starting and end points,
    - in each while loop we print rightwards, downwards, leftwards, and upwards
  */
  while (rowStart <= rowEnd && colStart <= colEnd)
  {
    // rightwards (same row, column is incremented)
    for (int i = colStart; i <= colEnd; i++)
    {
      result.push_back(matrix[rowStart][i]);
    }
    rowStart++;


    // downwards (same column, row is incremented)
    for (int i = rowStart; i <= rowEnd; i++)
    {
      result.push_back(matrix[i][colEnd]);
    }
    colEnd--;


    // leftwards (same row, col is decremented)
    if (rowStart <= rowEnd)
    {
      for (int i = colEnd; i >= colStart; i--)
      {
        result.push_back(matrix[rowEnd][i]);
      }
      rowEnd--;
    }


    // upwards (same col, row is decremented)
    if (colStart <= colEnd)
    {
      for (int i = rowEnd; i >= rowStart; i--)
      {
        result.push_back(matrix[i][colStart]);
      }
      colStart++;
    }
  }

  return result;
};