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;
        }    
    }
}

Mock interview (4th practice): Matrix Spiral Print

March 16, 2016

Problem statement

Given a 2D array (matrix) named M, print all items of M in a spiral order, clockwise.

For example:

M  =  1    2    3    4   5
         6    7    8    9  10
       11  12  13  14  15
       16  17  18  19  20

The clockwise spiral print is:  1 2 3 4 5 10 15 20 19 18 17 16 11 6 7 8 9 14 13 12

Mock interview practice

I had a mock interview recently and my algorithm is Spiral matrix. The code I wrote in mock interview using C# is here.

Let us take a look at evaluation from the mock interviewer, as a matter of fact the peer gave me the honest feedback, I have to figure out how to work on the improvement:

Code review

After the mock interview, I thought about more how to improve the solution. I do not have good idea to solve the problem. Based on my mathematics background and I tried to define how many variables in the problem.

Let us look at one variable, let us call it layer, using variable name row, value is from 0 to (N+1) / 2, where N is how many columns in the matrix. So, the spiral matrix output is to follow the order of clockwise starting from (0,0). 

N - how many columns

M - how many rows

Four corners are left-top, right-top, bottom-right, bottom-left, abbreviation using four variables: LT, RT, BR, BL

   LT     coordinates:   ( row,             row )    

   RT    coordinates:   ( row,             N - 1 - row)  

   BR    coordinates:   ( M - 1 - row,  N -1 - row)

   BL     coordinates:   ( M - 1 - row,  row)

private static void leftToRight(Coordinate[] A)

TopToDown, RightToLeft, and DownToUp 

  

           row

            0     1       2

            -------------->

           1    2     3   4   5

            6    7     8   9  10

           11  12  13  14  15

           16  17  18  19  20

The above case, LT = (0, 0), RT = (0, 4), BR = (3, 4), BL = (3, 0)

C# practice code based on the above idea is here.  

Continue to improve the idea. 

LT, BR those two pointers should be checked on the conditions, M – 1 - row >= row, N – 1 - row >= row; in other words, left top pointer is above the bottom right pointer, therefore it should be row <= Math.Min((M - 1)/ 2, (N - 1)/ 2).

It is true that the idea I came out just after the mock interview was not so good. But the hard work spirit is good, and also it is very good to write down the idea and review later on.

Issues found in mock interview

I like to write down a few issues in my practice. 

1. Jagged array initialization

Julia spent more than 5 minutes to look up the internet. 

2. Try another idea. Use one variable instead of two variables. 

Assuming that N rows and M columns, how many layers of spiral? Use the variable i to denote the number. 

It should be from 0 to (N+1)/2, but it is hard to figure out correct answer first time, it should be 0 to Math.Min((M-1)/2, (N-1)/2). 

Julia spent more than 20 minutes to debug in the practice. 

Spiral matrix practice in 2015

I practice once in 2015 on Leetcode 54 Spiral matrix algorithm. I found the blog and it is very interesting to read the code I wrote back in 2015 June. Here is the blog about the practice. 

Follow up 

May 23, 2017

It is such great experience to compare the current practice to the one in 2016. Julia learned that she made such great improvement on coding readability, and she starts to know how important it is to document and track the progress. 

After considering a few of options, it is much easy to write a while loop to track the total visited nodes in the original array. 

Instead of using i, j, use variable row and col because it is more meaningful. 

Do not run the code and depend on the compiler; 

Test the code by yourself. 

C# practice is here. 

In order to make sure that the code is working, Julia used the same idea to write a solution for Leetcode 54. The solution failed to pass one row test case [1, 2, 3]. 

The C# code is fixed to add one row and one column checking. The code is here.