Spiral Matrix medium

Problem Statement

Given an m x n matrix, return all elements of the matrix in spiral order.

Example 1

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

Example 2

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]

Steps

1. Initialization: Define variables to track the boundaries of the unvisited portion of the matrix: top, bottom, left, and right. Initialize them to 0, matrix.Length -1, 0, and matrix[0].Length - 1 respectively. Also, initialize a list result to store the spiral order traversal.

2. Iteration: While there are still unvisited elements (top <= bottom and left <= right):

   • Traverse Right: Iterate from left to right, adding each element matrix[top][i] to result. Increment top.
   • Traverse Down: If top <= bottom, iterate from top to bottom, adding each element matrix[i][right] to result. Decrement right.
   • Traverse Left: If top <= bottom and left <= right, iterate from right to left (in reverse), adding each element matrix[bottom][i] to result. Decrement bottom.
   • Traverse Up: If top <= bottom and left <= right, iterate from bottom to top (in reverse), adding each element matrix[i][left] to result. Increment left.

3. Return Result: Return the result list.

Explanation

The algorithm systematically explores the matrix layer by layer. In each iteration, it traverses one layer (a perimeter) of the matrix in clockwise order. The boundary variables (top, bottom, left, right) shrink inward with each iteration, effectively peeling away the outer layer until the entire matrix is traversed. The conditional checks (top <= bottom and left <= right) ensure that the algorithm stops when all elements have been visited.

Code

using System;
using System.Collections.Generic;

public class Solution {
    public IList<int> SpiralOrder(int[][] matrix) {
        List<int> result = new List<int>();
        if (matrix == null || matrix.Length == 0) return result;

        int top = 0, bottom = matrix.Length - 1, left = 0, right = matrix[0].Length - 1;

        while (top <= bottom && left <= right) {
            // Traverse Right
            for (int i = left; i <= right; i++) {
                result.Add(matrix[top][i]);
            }
            top++;

            // Traverse Down
            if (top <= bottom) {
                for (int i = top; i <= bottom; i++) {
                    result.Add(matrix[i][right]);
                }
                right--;
            }

            // Traverse Left
            if (top <= bottom && left <= right) {
                for (int i = right; i >= left; i--) {
                    result.Add(matrix[bottom][i]);
                }
                bottom--;
            }

            // Traverse Up
            if (top <= bottom && left <= right) {
                for (int i = bottom; i >= top; i--) {
                    result.Add(matrix[i][left]);
                }
                left++;
            }
        }

        return result;
    }
}

Complexity

• Time Complexity: O(m * n), where 'm' and 'n' are the dimensions of the matrix. We visit each element exactly once.
• Space Complexity: O(1) if we ignore the space used to store the result list. The auxiliary space used by the algorithm itself is constant. If we include the result list, the space complexity becomes O(m * n) in the worst case (when the matrix is entirely filled).