trjhtr

Problem statement

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].

My introduction of algorithm

This is medium level algorithm on Leetcode.com. I have practiced over ten times from March 2017 to Jan. 2018. I wrote the algorithm in mock interview five times and also watched five peers to work on the algorithm. I experienced the pain to write a for loop inside a while loop four times, I wrote the code with a bug to print one row matrix twice, duplicate the output on last row and first column. And also I watched a few times the peer to struggle with so many bugs. Overall it is an algorithm with a lot of fun to play with.

How to write bug free solution in mock interview?

First time I had a mock interview on another mock interview platform on Jan. 23, 2018, and it is anonymous one.

The interviewer asked me if I can write the solution only using one loop instead of four for loops inside one while loop whereas two for loops to iterate on row, either top or bottom row; two for loops to iterate on last column or first column.

I had worked on the algorithm over 10 times on mock interview, but I never come out the completed idea based on limited time concern and buggy for loops. None of my peers came out the idea and wrote the similar ideas, and I only had discussion with one peer before. As an interviewer or interviewee, I did thought about four for loops are problematic as well.

One time I complained to the peer in mock interview when I worked on the four for loop of this spiral matrix problem. I told the peer that I like to use extra array to mark visit, so that my four for loop can always go from 0 to rows - 1 or 0 to cols - 1. The code will take extra time to iterate on visited elements but definitely no worry to define the start and end position. The peer's advice is not to be a hacker in mock interview, you should always follow the interviewer's hint or advice. That is only time I made very close to this new idea.

It is helpful to review all past practices through the code blogs. Here is one of blogs about the practice on spiral matrix algorithm.

Analysis of the algorithm

One thing I like to do is to write down some analysis of the algorithm before I write any code in mock interview. And it is also very helpful for me to go over various ideas to find the optimal one.

I also like to practice this approach when I ask a question on this site.

Here are some keywords for the spiral matrix algorithm.

Direction - There are four directions. Change direction if need, in the order of clockwise, starting from top left corner (0,0).
Range - Stay inside the array
Visit - visit each element in the array only once. Do not visit more than once.
Order - follow the order of clockwise, start from (0,0).

Quick solution with readable code

I wrote a C# solution and use extra space to declare an array to mark the element in the matrix is visited or not. To change direction, if the current row and column is out of boundary of matrix or it is visited before. I wrote the solution after the mock interview, I could not believe that I need so many hints in the mock interview after so many practice, one hint for four directions, one hint using extra array for visited array.

Here is C# solution.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace MatrixSpiralPrint

 class Program
 
 /// <summary>
 /// Leetcode Spiral Matrix
 /// https://leetcode.com/problems/spiral-matrix/description/
 /// </summary>
 /// <param name="args"></param>
 static void Main(string args)
 
 var spiral = MatrixSpiralPrint(new int[,] 1, 2, 3 , 8, 9, 4 , 7, 6, 5 );
 Debug.Assert(String.Join(",", spiral).CompareTo("123456789") == 0);
 

 /// <summary>
 /// Navigate the direction automatically by checking boudary and checking 
 /// the status of element visited status. 
 /// Only one loop, perfect idea to fit in mock interview or interview 
 /// 20 minutes setting 
 /// </summary>
 /// <param name="array"></param>
 /// <returns></returns>
 public static int MatrixSpiralPrint(int[,] array)
 
 if (array == null 
 

Why use integer for on/off status?

The values in visited are either 0 or 1.
A boolean matrix would be a natural choice for the purpose.

Do you really need the extra storage?

Using the visited array makes the implementation somewhat simpler.
Another way, without extra storage would be keeping track of the number of steps to do in the current direction.
Think about the correct values and observe the pattern:

• Top: columns
  


• Right: rows - 1
  


• Bottom: columns - 1
  


• Left: rows - 2
  


• Top: columns - 2
  


• Right: rows - 3
  


• Bottom: columns - 3
  


• Left: rows - 4
  


• ...

Basically, alternating the column and row counts, decreasing by 1 on every direction change. When the next number of steps is 0, it's time to stop.
A bit more tricky to write, but using constant extra storage.

Handling special cases

The case of 0 rows or 0 columns doesn't need special treatment.
The result array will be created empty,
and the main loop will not do any steps.

The case of null value for the array is non-sense input.
If that ever happens, it looks suspiciously as a malfunction in the caller.
It would be better to signal that there is a problem by throwing an explicit exception.

Naming

fourDirections contains 4 directions.
Don't name a collection by its size.
Just directions would be better.