Spiral matrix - discussion of the algorithm - change design using direction array.

Spiral matrix discussion of algorithm design using directions

January 23, 2018 Mock interview transcript:

Spiral Matrix:
Print a m*n matrix in spiral order.

Input:

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

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

Time: O(m*n)
Space: O(m*n)

int rows = 
int cols = 

int startRow = 0;
int startCol = 0; 
int EndRow = rows - 1; 
int EndCol = cols - 1; 

while(startRow <= endRow && startCol <= EndCol
{
   // iterate on startRow from left to right, startCol to lastCol, for examle, 1, 2, 3
   for()
   
   // iterate on lastCol from startRow + 1 to EndRow, visit 6, 9
   
   // iterate on lastRow if lastRow != firstRow, from EndCol - 1 to startCol, visit 8, 7
   
   // iterate on first col from lastRow - 1 to startRow + 1 if firstCol < lastCol, visit 4
   
   prepare for next iteration:   
   
   Hint 1: 
   dr = [0,1,0,-1]
   dc = [1,0,-1,0]
     top row -> dr[0] = 0, dc[0] = 1         
     
   direction = 0  -> top row 
   visited - extra space [][] for marking visit 1 
   row
   col
   loop:
      row = row + dr[direction]
      col = col + dc[direction]
      
      var visited = visited[row][col] == 1
      if(visited)
        continue;
      
      visted[row][col] == 1
      
      spiral[index++] = arr[row][col]
      
      Hint 2: check if row and column is in range:
      if(row >= rows || row < 0 || col >= cols || col < 0 || visted[row][col]) {
         change direction
 
 Ask question how to define the change of direction using examples:
 
      1  2   3  4 *
      -------->
      5  6   7  8 
      10 11 12  13
      14 15 16 17
      
      1 2 3 4 8 13 17 16 15 14 10 5 -> 6 7 ( direction = 0 )
      }
      
      https://codereview.stackexchange.com/users/123986/jianmin-chen
      
      mock interview / nervous / communication 
      
      if( *direction == 0* && ((col == cols -1) || visited[row][col + 1] == 1) // last column
      {
        direction++; 
        
        direction = direction % 4 // map to 0 - 3
      }       
   
   https://gist.github.com/jianminchen/d9b257d9882bed9cee55a9d8c75db4be   
      
   
   how to define the iteration
   /*
    if (topRow == bottomRow)   // added after the mocking, 5/23/2017
            {
                continue; 
            }
*/
            for (int col = rightCol - 1; col >= leftCol && topRow < bottomRow; col--)
            {
                var current = matrix[bottomRow][col];
                spiral[index++] = current;
            }                         
}