StackExchange | Code Review | Leetcode 54: Spiral Matrix

Here is the link.

7

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 || array.GetLength(0) == 0 || array.GetLength(1) == 0)
            {

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.

Share

Edit

answered Jan 30, 2018 at 21:08

janos

110k1414 gold badges150150 silver badges383383 bronze badges

• Extra storage is not necessary. I agree with your advise on this. 

  – Jianmin Chen

   Jan 30, 2018 at 21:15   
• I got complaint about memorizing the solution in mock interview. Since I choose to work on same 30 algorithms again and again on mock interview, I know all the common solutions and mistakes. But exploring new ideas are challenging still in the mock interview, I try to write simple code. Four variables to replace visited array are easy to make mistakes in interview, I think. 

  – Jianmin Chen

   Jan 30, 2018 at 21:34   
• 2
  @JianminChen the purpose of programming interviews should not be to find perfect solutions, but to see your thought process, ability to split larger problems to smaller ones, and building up something that works through iteration. So rather than perfecting the solution to a small set of specific problems, I recommend to solve a wide range of problems. 

  – janos

   Jan 30, 2018 at 21:44
• I agree with you on this. It is not good to be opportunistic. But one popular saying is to write production ready code in interview, I also ask myself which one is more production ready code? More space less buggy or optimal space with more buggy variables? 

  – Jianmin Chen

   Jan 30, 2018 at 22:40   
• I had a mock interview as an interviewer on Jan. 30, 2018, so I asked the peer to solve the algorithm; he gave exactly the same idea you advise, using direction array and also use four variables instead of visited array, he wrote 10 minutes but code has a few issues like grammar errors. Here is C# code I completed based on his code after the mock interview: gist.github.com/jianminchen/fca45bb38410b59f580f88a0051ae2a8 

  – Jianmin Chen

   Feb 2, 2018 at 6:24   
• I continuously studied and then I found exactly same idea advised by janos. Here is the leetcode discussion link: discuss.leetcode.com/topic/15558/… 

  – Jianmin Chen

   Feb 10, 2018 at 23:40   
• I wrote the implementation of the idea advised by janos. I did not really understand quickly about the idea by reading the above code review until I wrote the C# code based on Leetcode discussion, and then I found that the idea is exactly the same. Here is the C# code integerated all the above code review advices and avoid using extra array visited. gist.github.com/jianminchen/1adcda667cc22247df154a40fcc57d2c 

  – Jianmin Chen

   Feb 10, 2018 at 23:43   
• I wrote C# solution with optimal space O(1), using direction array to adjust direction automatically. Here is the link: leetcode.com/problems/spiral-matrix/discuss/407992/… 

  – Jianmin Chen

   Dec 7, 2019 at 1:47