Leetcode 54. Spiral matrix

Oct. 18, 2019

Introduction

I worked on the algorithm more than 10 times. And then I started to work on a better solution, learned to use direction array and visited array to help. The idea is to simplify the detail of each edge in the matrix, encapsulate the direction information in the direction array, and also mark the visited element in the matrix to avoid duplication.

My practice

Here is my practice in 2018.

C# a few ideas to expedite the problem solving

April 12, 2019
To master the algorithm, I have practiced over a few ideas to go through the spiral process. One of ideas is to write the code to treat all four directions encapsulated in the array, using visited array extra space to help to determine to change the direction.

Here are the highlights of implementation.

1. Use direction array to encapsulate four direction using two arrays. Go right, go down, go left and go up are four direction to form one spiral;
2. Set start point as outside the matrix first row left to the first element in the matrix;
3. Design a while loop to make sure all elements in matrix will be iterated;
4. Design a conditional statement to determine if the change of direction is needed.
5. Change of direction can be expressed in (direction + 1) % 4;
6. Add the element to the list, mark visit
7. Prepare for next iteration, set startRow, startCol two variables.

public class Solution {
    /// online code screen - mock interview 4/12/2019
    public IList<int> SpiralOrder(int[][] matrix) {
        if(matrix == null || matrix.Length == 0 ||  matrix[0].Length == 0)
            return new List<int>(); 
        
        var rows    = matrix.Length; 
        var columns = matrix[0].Length; 
        
        // right, down, left, up
        var directionX = new int[]{0, 1, 0, -1};
        var directionY = new int[]{1, 0, -1, 0};
        
        var visited = new bool[rows, columns];
        
        var direction = 0; 
        var startRow = 0; 
        var startCol = -1; 
        
        var list = new List<int>(); 
        
        int index = 0; 
        while(index < rows * columns)
        {
            var nextRow = startRow + directionX[direction];
            var nextCol = startCol + directionY[direction];
            
            if(nextRow < 0 || nextRow >= rows || nextCol < 0 || nextCol >= columns || visited[nextRow, nextCol])
            {
                direction = (direction + 1) % 4; 
                continue; 
            }
            
            list.Add(matrix[nextRow][nextCol]);
            visited[nextRow, nextCol] = true; 
            
            startRow = nextRow;
            startCol = nextCol;
            
            index++; 
        }
        
        return list; 
    }
}