Leetcode 54. Spiral matrix

Oct. 18, 2019

It is my favorite algorithm. I wrote a C# solution again to warmup the idea. Here is the post.

C# Using direction array and no extra space for visit marking practice in 2018

Oct. 18, 2019

It is the time for me to review the algorithm again. With the experience of Amazon and Facebook onsite in August 2019, I learned that I have to work on algorithms and make sure that I can come out optimal time and space complexity in practice.

The argument is that optimal space complexity can lead to a solution with simplicity; simplicity =>Write and implement in less than 10 minutes.

I also spent time to review the question I asked on stackexchange.com back in February 2018. At that time, I was not sure how to push myself hard to practice the algorithm with this optimal space complexity solution as well. Here is the question I asked in February, 2018.

Here are highlights:

1. Understand the design of four variables (top, bottom, left, right) to mark the boudary of spiral matrix, four corners;
2. Increment/ decrement those four variables (top, bottom, left, right) while changing directions;
3. Introduce one variable (total) to track how many nodes to visit in the matrix, one variable (index);
4. Introduce directions variable to track four directions, toRight, down, toLeft, up;
5. Overall six variables, one direction array can easily be used to solve problem with optimal space and easy to write.

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

namespace _54_Spiral_matrix___2019_Warmup
{
    class Program
    {
        static void Main(string[] args)
        {
            RunTestcase();
        }

        public static void RunTestcase()
        {
            var matrix = new int[3][];
            matrix[0] = new int[] { 1, 2, 3 };
            matrix[1] = new int[] { 8, 9, 4 };
            matrix[2] = new int[] { 7, 6, 5 };

            var spiral = SpiralOrder(matrix);

            Debug.Assert(String.Join("", spiral).CompareTo("123456789") == 0);
        }

        /// <summary>
        /// warm up practice in Oct. 2019
        /// https://leetcode.com/problems/spiral-matrix/discuss/407992/C-Using-direction-array-and-no-extra-space-for-visit-marking-practice-in-2018
        /// </summary>
        /// <param name="matrix"></param>
        /// <returns></returns>
        public static IList<int> SpiralOrder(int[][] matrix)
        {
            if (matrix == null || matrix.Length == 0 || matrix[0].Length == 0)
            {
                return new int[0];
            }

            int rows = matrix.Length;
            int columns = matrix[0].Length;

            var spiral = new int[rows * columns];
            //                               Right    down    left      up 
            var directions = new int[4, 2] { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

            // define four corners of matrix and increment/ decrement when changing directions
            int firstRow = 0;
            int lastRow = rows - 1;
            int firstColumn = 0;
            int lastColumn = columns - 1;

            int total = rows * columns;
            int index = 0;

            // visit node
            int row = 0;
            int column = 0;

            int direction = 0;

            while (index < total)
            {
                spiral[index] = matrix[row][column];
                index++;

                var nextRow = row + directions[direction, 0];
                var nextCol = column + directions[direction, 1];

                // not in range of spiral matrix 
                if (!(nextRow >= firstRow && nextRow <= lastRow && nextCol >= firstColumn && nextCol <= lastColumn))
                {
                    // change direction - increment/ decrement four corners
                    switch (direction)
                    {
                        case 0:
                            firstRow++;
                            break;
                        case 1:
                            lastColumn--;
                            break;
                        case 2:
                            lastRow--;
                            break;
                        case 3:
                            firstColumn++;
                            break;
                    }

                    direction = (direction + 1) % 4;
                }

                // reset row, column
                row += directions[direction, 0];
                column += directions[direction, 1];
            }

            return spiral;
        } 
    }
}

54. Spiral Matrix - practice in 2015

Here is my sharing on Leetcode.com.

It is tough job to write a C# solution to go over spiral array to print out all elements in the matrix. I wrote C# solution but I failed multiple test cases, I learned that it is easy to make mistake to count same element twice. Compare to use extra space to mark visit, the solution is prone to the bug for duplicated output.

Also back in 2015, I also need to learn C# better to write more readable code.

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

namespace _54_Spiral_matrix_2015_June
{
    class Program
    {
        static void Main(string[] args)
        {
        }

        /// <summary>
        /// code written in June 12, 2015
        /// </summary>
        /// <param name="matrix"></param>
        /// <returns></returns>
        public IList<int> SpiralOrder(int[,] matrix)
        {
            IList<int> list = new List<int>();

            int len1 = matrix.GetLength(0);
            int len2 = matrix.GetLength(1);

            int[][] matrix_input = new int[len1][];

            for (int i = 0; i < len1; i++)
                matrix_input[i] = new int[len2];

            for (int i = 0; i < len1; i++)
                for (int j = 0; j < len2; j++)
                {
                    matrix_input[i][j] = matrix[i, j];
                }

            ArrayList al = spiralOrder_2(matrix_input);

            foreach (object s in al)
            {
                list.Add((int)s);
            }
            return list;
        }

        public ArrayList spiralOrder_2(int[][] matrix)
        {
            if (matrix == null || matrix.Length == 0 || matrix[0].Length == 0)
                return new ArrayList();
            return spiralOrder_3(matrix, 0, 0, matrix.Length, matrix[0].Length);
        }

        /**
         * Latest update: June 12, 2015 
         * Leetcode: spiral array
         * http://gongxuns.blogspot.ca/2012/12/leetcode-spiral-matrix.html
         * Test case: 
         * 1. empty array 
         * 2. one element:           1 -
         * 2B. one row : 1 2 --
         * 3. one column : 1 |
         *                 2 |
         * 4. more than 1 row, 
         *    or more than 1 column   
         *     1 2
         *     3 4
         *     output: 1 2 4 3 
         * 5. 3 rows, 3 columns
         *    1 2 3
         *    4 5 6
         *    7 8 9
         *    output: 1 2 3 6 9 8 7 4 5 
         * 
         */
        public ArrayList spiralOrder_3(int[][] matrix, int x, int y, int m, int n)
        {
            ArrayList res = new ArrayList();
            // test case: empty array
            if (m <= 0 || n <= 0) return res;

            // test case 2: one row and one column
            if (m == 1 && n == 1)
            {
                res.Add(matrix[x][y]);
                return res;
            }

            //  row, from left to right 
            for (int i = 0; i < n - 1; i++)
            {
                res.Add(matrix[x][y++]);
            }

            //  column, from top to down
            for (int i = 0; i < m - 1; i++)
            {
                res.Add(matrix[x++][y]);
            }

            // conditional: second row, from right to left 
            if (m > 1)
            {
                for (int i = 0; i < n - 1; i++)
                {
                    res.Add(matrix[x][y--]);
                }
            }

            // conditional: second column, from bottom to top
            if (n > 1)
            {
                for (int i = 0; i < m - 1; i++)
                {
                    res.Add(matrix[x--][y]);
                }
            }

            // test case: one row, 1 2 3, where 1 2 is procesed above and 3 is left for next round 
            // one column:
            if (m == 1 || n == 1)
            {
                ArrayList l = spiralOrder_3(matrix, x, y, 1, 1);

                foreach (object val in l)
                    res.Add((int)val);
            }
            else
            {
                ArrayList l = spiralOrder_3(matrix, x + 1, y + 1, m - 2, n - 2);
                foreach (object val in l)
                    res.Add((int)val);
            }

            return res;
        }    
    }
}

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