
Problem Statement
In this task, you are provided with an m x n
matrix which you need to parse and return all its elements in a "spiral order." Spiral order traversal means navigating through all the elements of the matrix in an outwardly spiraling way. This navigation starts from the top-left corner of the matrix, goes towards the top-right, then moves downward on the right side, towards the left on the bottom side, and moving upward on the left side, continually looping toward the center.
Examples
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]
Constraints
m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100
Approach and Intuition
Spiral Traversal Approach
Navigating through a matrix in a spiral order can be approached systematically. Here's a step-by-step method to achieve this:
Initialize Boundaries:
Set up four boundary variables:
top = 0
bottom = m - 1
left = 0
right = n - 1
Spiral Traversal Logic:
While
top <= bottom
andleft <= right
, perform the following in sequence:- Left to Right: Traverse from
left
toright
across thetop
row, then incrementtop
. - Top to Bottom: Traverse from
top
tobottom
down theright
column, then decrementright
. - Right to Left: If
top <= bottom
, traverse fromright
toleft
across thebottom
row, then decrementbottom
. - Bottom to Top: If
left <= right
, traverse frombottom
totop
up theleft
column, then incrementleft
.
- Left to Right: Traverse from
Termination:
- The loop continues narrowing the traversal area until all elements have been visited, ensuring each is included once.
This method provides a clear and efficient way to collect all values in spiral order while adhering to the input constraints.
Solutions
- C++
- Java
- C
- JavaScript
- Python
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, anddirection_changes
to track changes in movement direction (to detect if spiral traversal is complete). - Setup initial positions
x
andy
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.
No comments yet.