Wednesday, May 6, 2015

[Microsoft Question][Google Question] Spiral order traversal of a matrix

Problem: Given a 2D array, print it in spiral form.

Example:
Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]


Approach: Nothing to explain, just for loops. Have a look at implementation directly.


Implementation in C#:

    public IList<int> SpiralOrder(int[][] matrix) 
    {
        List<int> result = new List<int>();
        
        if (matrix?.Length == 0)
        {
            return result;
        }
        
        int rowBegin = 0, colBegin = 0, rowEnd = matrix.Length - 1, colEnd = matrix[0].Length - 1;
        
        while (rowBegin <= rowEnd && colBegin <= colEnd)
        {
            for (int i = colBegin; i <= colEnd; ++i)
            {
                result.Add(matrix[rowBegin][i]);
            }
            
            for (int i = rowBegin + 1; i <= rowEnd; ++i)
            {
                result.Add(matrix[i][colEnd]);
            }
            
            
            if (rowBegin < rowEnd && colBegin < colEnd)
            {
                for (int i = colEnd - 1; i >= colBegin; --i)
                {
                    result.Add(matrix[rowEnd][i]);
                }

                for (int i = rowEnd - 1; i >= rowBegin + 1; --i)
                {
                    result.Add(matrix[i][colBegin]);
                }
            }
            
            ++rowBegin;
            ++colBegin;
            --rowEnd;
            --colEnd;
        }
        
        return result;
    }


Complexity: O(row*col)

No comments:

Post a Comment