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:
- Understand the design of four variables (top, bottom, left, right) to mark the boudary of spiral matrix, four corners;
- Increment/ decrement those four variables (top, bottom, left, right) while changing directions;
- Introduce one variable (total) to track how many nodes to visit in the matrix, one variable (index);
- Introduce directions variable to track four directions, toRight, down, toLeft, up;
- 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;
}
}
}
