Spiral Matrix: Traversing 2D Arrays in a Spiral Pattern

The "Spiral Matrix" problem involves traversing a 2D matrix in a spiral order, starting from the top-left corner and moving clockwise.

Problem Statement

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

Example

• Input: Matrix

[
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]

• Output:

[1, 2, 3, 6, 9, 8, 7, 4, 5]

Solution Approach (typescript)

function spiralOrder(matrix: number[][]): number[] {
  if (matrix.length === 0) return [];

  let result: number[] = [];
  let left = 0,
    right = matrix[0].length - 1;
  let top = 0,
    bottom = matrix.length - 1;

  while (left <= right && top <= bottom) {
    for (let i = left; i <= right; i++) result.push(matrix[top][i]);
    top++;

    for (let i = top; i <= bottom; i++) result.push(matrix[i][right]);
    right--;

    if (top <= bottom) {
      for (let i = right; i >= left; i--) result.push(matrix[bottom][i]);
      bottom--;
    }

    if (left <= right) {
      for (let i = bottom; i >= top; i--) result.push(matrix[i][left]);
      left++;
    }
  }

  return result;
}

Breaking Down the Solution

• Initialize Boundaries: Start with boundaries (left, right, top, bottom) for the matrix.
• Traverse in Spiral: Move right across the top row, down the rightmost column, left across the bottom row, and up the leftmost column, adjusting boundaries each time.
• Continue Inward: Repeat the process for each layer of the spiral until all elements are covered.

Solution Approach (go)

package main

import (
	"fmt"
)

func spiralOrder(matrix [][]int) []int {
	if len(matrix) == 0 {
		return []int{}
	}

	result := make([]int, 0)
	top, bottom := 0, len(matrix)-1
	left, right := 0, len(matrix[0])-1

	for left <= right && top <= bottom {
		// Move right
		for i := left; i <= right; i++ {
			result = append(result, matrix[top][i])
		}
		top++

		// Move down
		for i := top; i <= bottom; i++ {
			result = append(result, matrix[i][right])
		}
		right--

		if top <= bottom {
			// Move left
			for i := right; i >= left; i-- {
				result = append(result, matrix[bottom][i])
			}
			bottom--
		}

		if left <= right {
			// Move up
			for i := bottom; i >= top; i-- {
				result = append(result, matrix[i][left])
			}
			left++
		}
	}

	return result
}

func main() {
	matrix := [][]int{
		{1, 2, 3},
		{4, 5, 6},
		{7, 8, 9},
	}
	fmt.Println(spiralOrder(matrix)) // Output: [1 2 3 6 9 8 7 4 5]
}

In this Go solution:

• The function spiralOrder takes a 2D integer slice (matrix) and returns a slice with the elements in spiral order.
• The variables top, bottom, left, and right define the boundaries of the current layer of the spiral.
• The spiral traversal is performed by moving right, down, left, and up, adjusting the boundaries after each direction change.
• The loop continues until all elements are traversed, shrinking the spiral layer by layer.

#include <iostream>
#include <vector>

std::vector<int> spiralOrder(std::vector<std::vector<int>>& matrix) {
    std::vector<int> result;
    if (matrix.empty()) return result;

    int top = 0, bottom = matrix.size() - 1;
    int left = 0, right = matrix[0].size() - 1;

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

        // Move down
        for (int i = top; i <= bottom; i++) {
            result.push_back(matrix[i][right]);
        }
        right--;

        if (top <= bottom) {
            // Move left
            for (int i = right; i >= left; i--) {
                result.push_back(matrix[bottom][i]);
            }
            bottom--;
        }

        if (left <= right) {
            // Move up
            for (int i = bottom; i >= top; i--) {
                result.push_back(matrix[i][left]);
            }
            left++;
        }
    }

    return result;
}

int main() {
    std::vector<std::vector<int>> matrix = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };

    std::vector<int> result = spiralOrder(matrix);
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

In this C++ solution:

• The function spiralOrder takes a reference to a 2D vector (matrix) and returns a vector with the elements in spiral order.
• The variables top, bottom, left, and right define the current spiral layer's boundaries.
• The spiral traversal includes moving right, down, left, and up, with each direction bounded by the current layer's limits.
• The loop continues until all layers are traversed, reducing the spiral layer by layer.

Solution Approach (rust)

fn spiral_order(matrix: Vec<Vec<i32>>) -> Vec<i32> {
    if matrix.is_empty() {
        return Vec::new();
    }

    let mut result = Vec::new();
    let (mut top, mut bottom) = (0, matrix.len() - 1);
    let (mut left, mut right) = (0, matrix[0].len() - 1);

    while left <= right && top <= bottom {
        // Move right
        for i in left..=right {
            result.push(matrix[top][i]);
        }
        top += 1;

        // Move down
        for i in top..=bottom {
            result.push(matrix[i][right]);
        }
        if right > 0 {
            right -= 1;
        }

        // Move left
        if top <= bottom {
            for i in (left..=right).rev() {
                result.push(matrix[bottom][i]);
            }
            bottom = bottom.saturating_sub(1);
        }

        // Move up
        if left <= right {
            for i in (top..=bottom).rev() {
                result.push(matrix[i][left]);
            }
            left += 1;
        }
    }

    result
}

fn main() {
    let matrix = vec![
        vec![1, 2, 3],
        vec![4, 5, 6],
        vec![7, 8, 9],
    ];

    let result = spiral_order(matrix);
    println!("{:?}", result); // Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]
}

In this Rust solution:

• The spiral_order function takes a matrix (a Vec<Vec<i32>>) and returns a vector containing the elements in spiral order.
• The top, bottom, left, and right variables define the boundaries of the current spiral layer.
• The code performs spiral traversal, moving right, down, left, and up within the boundaries of the current layer. It decreases the layer size after each direction.
• The saturating_sub function is used to prevent underflow when decrementing bottom.
• Rust's range syntax (..=) and its ability to reverse ranges (rev()) are used to iterate over rows and columns.

Conclusion

The Spiral Matrix problem is a fascinating challenge that requires careful manipulation of array indices and boundaries. It is a popular question in technical interviews, testing understanding of 2D arrays and iterative traversals.