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 || array.GetLength(0) == 0 || array.GetLength(1) == 0)
{
return new int[0];
}
int rows = array.GetLength(0);
int columns = array.GetLength(1);
var visited = new int[rows, columns];
int index = 0;
int totalNumbers = rows * columns;
var fourDirections = new List<int[]>();
fourDirections.Add(new int[] { 0, 1 }); // left to right - top row
fourDirections.Add(new int[] { 1, 0 }); // top to down - last column
fourDirections.Add(new int[] { 0, -1 }); // right to left - bottom row
fourDirections.Add(new int[] { -1, 0 }); // bottom up - first row
int direction = 0;
int row = 0;
int col = 0;
var spiral = new int[totalNumbers];
while (index < totalNumbers)
{
var current = array[row, col];
spiral[index++] = current;
visited[row, col] = 1; // mark visit
var nextRow = row + fourDirections[direction][0];
var nextCol = col + fourDirections[direction][1];
var isOutArrayBoundary = nextRow < 0 || nextRow >= rows || nextCol < 0 || nextCol >= columns;
if (isOutArrayBoundary || visited[nextRow, nextCol] == 1) // change the direction
{
direction = (direction + 1) % 4; // map to 0 to 3
}
row += fourDirections[direction][0];
col += fourDirections[direction][1];
}
return spiral;
}
}
}
