blind75

Spiral Matrix: Traversing 2D Arrays in a Spiral Pattern

Jan 13, 2024 · Exploring the solution to traverse a 2D matrix in a spiral order, covering all elements in a clockwise spiral from the outer layer to the inner.

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.

Spiral Matrix

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)

typescript

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)

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)

rust

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.

Comments (0)

Stub — comments live in your browser only (localStorage). No server round-trip yet.

No comments yet. Be the first.