Spiral Matrix

class Solution {
public:
    vector<int> get_spiral_order(vector<vector<int>>& grid) {
        const int MARKED = 101;
        int numRows = grid.size(), numCols = grid[0].size();
        vector<vector<int>> moves = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // right, down, left, up
        int directionIndex = 0;
        int turnCount = 0;
        int x = 0, y = 0;
        vector<int> output = {grid[0][0]};
        grid[0][0] = MARKED;
        while (turnCount < 2) {
            while (x + moves[directionIndex][0] >= 0 &&
                   x + moves[directionIndex][0] < numRows &&
                   y + moves[directionIndex][1] >= 0 &&
                   y + moves[directionIndex][1] < numCols &&
                   grid[x + moves[directionIndex][0]][y + moves[directionIndex][1]] != MARKED) {
                turnCount = 0;
                x += moves[directionIndex][0];
                y += moves[directionIndex][1];
                output.push_back(grid[x][y]);
                grid[x][y] = MARKED;
            }
            directionIndex = (directionIndex + 1) % 4; 
            turnCount++;
        }
        return output;
    }
};

The provided C++ solution is designed to fetch all elements from a 2D matrix in a spiral order. Here’s a breakdown of how the solution operates:

• Initialize a constant to mark visited cells.
• Get the total number of rows and columns in the matrix.
• Define the movement directions (right, down, left, and up) with a vector of vectors named moves.
• Start from the top left of the matrix, marking the element as visited and adding it to the output vector.
• Use a loop to move through the matrix in the current direction, checking boundaries and whether the next cell has been visited.
• If moving in the current direction is no longer possible (either out of bounds or the target cell is visited), change direction. This is handled by a modulo operation on directionIndex.
• If a direction change occurs and it is still not feasible to move, increment a counter (turnCount) that tracks consecutive failed attempts to proceed in a new direction.
• The loop exits after two consecutive turns indicating that all accessible elements are visited.

Ensure grid elements are retrieved without modifying the original matrix structure except for marking elements as temporarily visited using a custom marker defined in the code. The output is a vector of integers representing the spiral-ordered elements of the input matrix.

class Solution {
    public List<Integer> traverseSpirally(int[][] grid) {
        int MARKED = 101;
        int totalRows = grid.length;
        int totalCols = grid[0].length;
        int[][] move = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
        int dirIndex = 0;
        int turns = 0;
        int r = 0;
        int c = 0;
        List<Integer> spiralResult = new ArrayList<>();
        spiralResult.add(grid[0][0]);
        grid[0][0] = MARKED;
        while (turns < 2) {
            while (
                r + move[dirIndex][0] >= 0 &&
                r + move[dirIndex][0] < totalRows &&
                c + move[dirIndex][1] >= 0 &&
                c + move[dirIndex][1] < totalCols &&
                grid[r + move[dirIndex][0]][c + move[dirIndex][1]] != MARKED
            ) {
                turns = 0;
                r += move[dirIndex][0];
                c += move[dirIndex][1];
                spiralResult.add(grid[r][c]);
                grid[r][c] = MARKED;
            }
            dirIndex = (dirIndex + 1) % 4;
            turns++;
        }
        return spiralResult;
    }
}

This solution provides a method to traverse a 2D grid in a spiral order using Java. The function traverseSpirally takes a 2D integer array grid as input and returns a list of integers representing the elements of the grid visited in a spiral sequence.

• The process begins by initializing variables to track the direction of movement and when to change direction. A 2D move array is defined to streamline the transitions between right, down, left, and up movements.
• The spiral traversal is controlled using a loop that continues until the direction has been changed twice without moving, which is a condition tracked by the turns variable.
• During each iteration of the loop, the current position is checked against boundary conditions and whether the next cell has already been visited (marked). If valid, the position updates to the next cell, the cell value is added to the result list, and the cell is marked as visited.
• The direction is adjusted after an unsuccessful move, ensuring spiral movement by using modulo operation with the dirIndex.
• Finally, the list spiralResult containing the grid values in spiral order is returned, representing a successful traverse of the matrix.

The use of marking visited cells directly in the provided grid with a value outside the typical range of the grid (101 in this case) avoids the necessity of an additional data structure for tracking visits, making the method memory efficient. Ensure to handle different sizes of input matrices properly, including edge cases like single column or single row matrices.

typedef struct {
    int dx, dy;
} Move;
    
int* extractSpiral(int** grid, int gridRows, int* gridCols, int* outSize) {
    if (gridRows == 0 || gridCols[0] == 0) {
        *outSize = 0;
        return NULL;
    }
        
    const int MARKED = 101;
    int totalRows = gridRows, totalCols = gridCols[0];
    Move moves[] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int dirIndex = 0;
    int r = 0, c = 0;
    *outSize = totalRows * totalCols;
    int* output = (int*)malloc((*outSize) * sizeof(int));
    output[0] = grid[0][0];
    grid[0][0] = MARKED;
        
    for (int n = 1; n < *outSize;) {
        while (r + moves[dirIndex].dx >= 0 &&
               r + moves[dirIndex].dx < totalRows &&
               c + moves[dirIndex].dy >= 0 &&
               c + moves[dirIndex].dy < totalCols &&
               grid[r + moves[dirIndex].dx][c + moves[dirIndex].dy] != MARKED) {
            r += moves[dirIndex].dx;
            c += moves[dirIndex].dy;
            output[n++] = grid[r][c];
            grid[r][c] = MARKED;
        }
        dirIndex = (dirIndex + 1) % 4;
    }
    return output;
}

This solution involves extracting elements from a 2D array grid in a spiral order. The approach utilizes a Move structure to control the directions of the spiral traversal: right, down, left, and up. Start at the top-left corner of the matrix, marking each visited cell to avoid revisits, and change direction when the next cell is either out of bounds or already marked.

Here's a broad overview of the steps involved in the function extractSpiral:

• Initial Checks: If the grid or its first row is empty, set the output size to 0 and return NULL.
• Set Up Movement Directions and Variables: Define an array of Move structures to represent directions to move within the matrix. Use two indices, r (for rows) and c (for columns), to track the current position.
• Prepare Output Array: Allocate memory for the output array, which holds the spiral order of elements. The size of this array is equal to the number of elements in the grid.
• Traversal and Marking: Start at the first cell, mark it, and store its value in the output array. Then, move in the spirally defined order by updating row and column indices based on the current direction. After moving, mark the newly visited cell. Change direction when necessary — which is if the next cell is out of bounds or marked. This directional change moves cyclically through the moves array.
• Returning the Result: Once every element is visited and marked, the spiral order is complete in the output array, which is then returned.

Ensure that necessary headers such as <stdlib.h> are included to handle dynamic memory management with malloc. The handling of dynamic memory and boundary conditions in this matrix traversal is critical for correct function operation.

var matrixSpiralTraversal = function(m) {
    const FLAG = 101;
    let rowCount = m.length,
        colCount = m[0].length;
    let path = [m[0][0]];
    m[0][0] = FLAG;
    let move = [
        [0, 1], // right
        [1, 0], // down
        [0, -1], // left
        [-1, 0] // up
    ];
    let directionIdx = 0;
    let directionChangeCount = 0;
    let r = 0,
        c = 0;
    while (directionChangeCount < 2) {
        while (
            r + move[directionIdx][0] >= 0 &&
            r + move[directionIdx][0] < rowCount &&
            c + move[directionIdx][1] >= 0 &&
            c + move[directionIdx][1] < colCount &&
            m[r + move[directionIdx][0]][c + move[directionIdx][1]] != FLAG
        ) {
            directionChangeCount = 0;
            r += move[directionIdx][0];
            c += move[directionIdx][1];
            path.push(m[r][c]);
            m[r][c] = FLAG;
        }
        directionIdx = (directionIdx + 1) % 4;
        directionChangeCount++;
    }
    return path;
};

The JavaScript function matrixSpiralTraversal efficiently performs a spiral traversal of a given 2D matrix. This traversal involves moving through the matrix in a spiral sequence — right, down, left, and up — until all elements are visited.

• The function starts by initializing a path list and setting the first element of the matrix to a flag indicating that this cell has been visited.
• The movement directions are defined in a move array. Each sub-array represents a direction in the order of right, down, left, and up.
• The traversal uses nested loops to determine valid movement within the matrix bounds and checks if the cell has already been visited.
• Direction changes are monitored by a directionChangeCount variable which resets only when a valid move is made in the current direction. If no valid moves are available in the current direction, the direction is changed.
• The process ends when it's not possible to make two consecutive direction changes, indicating that there is no unvisited adjacent cell left.

This function returns the list path, representing the order in which the matrix cells are visited during the spiral traversal.

class Solution:
    def traverse_spiral(self, grid: List[List[int]]) -> List[int]:
        MARKED = 101
        total_rows, total_cols = len(grid), len(grid[0])
        path_directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        direction_index = 0
        direction_changes = 0
        x = y = 0
        output = [grid[0][0]]
        grid[0][0] = MARKED
    
        while direction_changes < 2:
            while True:
                next_x = x + path_directions[direction_index][0]
                next_y = y + path_directions[direction_index][1]
    
                if not (0 <= next_x < total_rows and 0 <= next_y < total_cols):
                    break
                if grid[next_x][next_y] == MARKED:
                    break
    
                direction_changes = 0
                x, y = next_x, next_y
                output.append(grid[x][y])
                grid[x][y] = MARKED
    
            direction_index = (direction_index + 1) % 4
            direction_changes += 1
    
        return output

The provided Python code defines a function, traverse_spiral, for retrieving elements from a 2D grid in a spiral order. This function belongs to a class named Solution.

• Initialize a constant MARKED with a value of 101 to represent cells that have been visited.
• Extract the total number of rows (total_rows) and columns (total_cols) from the grid.
• Define the possible directions for spiral movement: right, down, left, and up (in this specific order).
• Use direction_index to manage the current direction of movement, and direction_changes to track changes in movement direction (to detect if spiral traversal is complete).
• Setup initial positions x and y at (0,0) and an output list containing the element at (0,0), marking it as visited.
• Continue the traversal using a nested while loop until the spiral traversal stops (when all possible directions are blocked or already visited, tracked by the direction_changes).
  • Calculate the next position in the current direction.
  • Check boundary conditions and whether the next cell is marked.
  • On finding a valid next cell, move to that position, append the current cell value to the output list, and mark it.
  • On encountering a boundary or marked cell, change the direction, and increment the direction change counter.
• Return the output list containing elements of the grid in spiral order.

This approach efficiently handles spiral traversal with the control of direction and checks for visited nodes to ensure each element is processed exactly once. The use of mod operation (% 4) on direction_index supports continuous cyclic adjustment of directions.