Description:
Given an m x n matrix, return all elements of the matrix in spiral order.
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]Solution in Python:
To solve the problem of returning all elements of a matrix in spiral order in Python, we can use an iterative approach to traverse the matrix layer by layer.
Python
from typing import List
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
result = [] # This will store the elements in spiral order
if not matrix: # Check if the matrix is empty
return result
top, bottom = 0, len(matrix) - 1 # Initialize the top and bottom boundaries
left, right = 0, len(matrix[0]) - 1 # Initialize the left and right boundaries
while top <= bottom and left <= right:
# Traverse from left to right along the top row
for i in range(left, right + 1):
result.append(matrix[top][i])
top += 1 # Move the top boundary down
# Traverse from top to bottom along the right column
for i in range(top, bottom + 1):
result.append(matrix[i][right])
right -= 1 # Move the right boundary to the left
if top <= bottom:
# Traverse from right to left along the bottom row
for i in range(right, left - 1, -1):
result.append(matrix[bottom][i])
bottom -= 1 # Move the bottom boundary up
if left <= right:
# Traverse from bottom to top along the left column
for i in range(bottom, top - 1, -1):
result.append(matrix[i][left])
left += 1 # Move the left boundary to the right
return resultExplanation:
- Initialization:
resultis an empty list where the elements in spiral order will be stored.topandbottomare initialized to the first and last row indices, respectively.leftandrightare initialized to the first and last column indices, respectively.
- Loop Until Boundaries Meet:
- The main loop continues as long as
top <= bottomandleft <= right.
- The main loop continues as long as
- Traverse the Top Row:
- Move from the
leftboundary to therightboundary along thetoprow, appending elements toresult. - Increment the
topboundary to move it downwards.
- Move from the
- Traverse the Right Column:
- Move from the
topboundary to thebottomboundary along therightcolumn, appending elements toresult. - Decrement the
rightboundary to move it leftwards.
- Move from the
- Check and Traverse the Bottom Row:
- If
top <= bottom, move from therightboundary to theleftboundary along thebottomrow, appending elements toresult. - Decrement the
bottomboundary to move it upwards.
- If
- Check and Traverse the Left Column:
- If
left <= right, move from thebottomboundary to thetopboundary along theleftcolumn, appending elements toresult. - Increment the
leftboundary to move it rightwards.
- If
- Return the Result:
- After the loop completes, return the
resultlist containing the elements in spiral order.
- After the loop completes, return the
This approach ensures that we traverse the matrix layer by layer in a spiral order, adjusting the boundaries accordingly. The solution works for any valid matrix dimensions within the given constraints.
Solution in Javascript:
JavaScript
/**
* @param {number[][]} matrix
* @return {number[]}
*/
var spiralOrder = function(matrix) {
let result = []; // This will store the elements in spiral order
if (matrix.length === 0) { // Check if the matrix is empty
return result;
}
let top = 0, bottom = matrix.length - 1; // Initialize the top and bottom boundaries
let left = 0, right = matrix[0].length - 1; // Initialize the left and right boundaries
while (top <= bottom && left <= right) {
// Traverse from left to right along the top row
for (let i = left; i <= right; i++) {
result.push(matrix[top][i]);
}
top++; // Move the top boundary down
// Traverse from top to bottom along the right column
for (let i = top; i <= bottom; i++) {
result.push(matrix[i][right]);
}
right--; // Move the right boundary to the left
if (top <= bottom) {
// Traverse from right to left along the bottom row
for (let i = right; i >= left; i--) {
result.push(matrix[bottom][i]);
}
bottom--; // Move the bottom boundary up
}
if (left <= right) {
// Traverse from bottom to top along the left column
for (let i = bottom; i >= top; i--) {
result.push(matrix[i][left]);
}
left++; // Move the left boundary to the right
}
}
return result;
};Solution in Java:
Java
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new ArrayList<>(); // This will store the elements in spiral order
if (matrix == null || matrix.length == 0) { // Check if the matrix is empty or null
return result;
}
int top = 0, bottom = matrix.length - 1; // Initialize the top and bottom boundaries
int left = 0, right = matrix[0].length - 1; // Initialize the left and right boundaries
while (top <= bottom && left <= right) {
// Traverse from left to right along the top row
for (int i = left; i <= right; i++) {
result.add(matrix[top][i]);
}
top++; // Move the top boundary down
// Traverse from top to bottom along the right column
for (int i = top; i <= bottom; i++) {
result.add(matrix[i][right]);
}
right--; // Move the right boundary to the left
if (top <= bottom) {
// Traverse from right to left along the bottom row
for (int i = right; i >= left; i--) {
result.add(matrix[bottom][i]);
}
bottom--; // Move the bottom boundary up
}
if (left <= right) {
// Traverse from bottom to top along the left column
for (int i = bottom; i >= top; i--) {
result.add(matrix[i][left]);
}
left++; // Move the left boundary to the right
}
}
return result;
}
}Solution in C#:
C#
using System.Collections.Generic;
public class Solution {
public IList<int> SpiralOrder(int[][] matrix) {
List<int> result = new List<int>(); // This will store the elements in spiral order
if (matrix == null || matrix.Length == 0) { // Check if the matrix is empty or null
return result;
}
int top = 0, bottom = matrix.Length - 1; // Initialize the top and bottom boundaries
int left = 0, right = matrix[0].Length - 1; // Initialize the left and right boundaries
while (top <= bottom && left <= right) {
// Traverse from left to right along the top row
for (int i = left; i <= right; i++) {
result.Add(matrix[top][i]);
}
top++; // Move the top boundary down
// Traverse from top to bottom along the right column
for (int i = top; i <= bottom; i++) {
result.Add(matrix[i][right]);
}
right--; // Move the right boundary to the left
if (top <= bottom) {
// Traverse from right to left along the bottom row
for (int i = right; i >= left; i--) {
result.Add(matrix[bottom][i]);
}
bottom--; // Move the bottom boundary up
}
if (left <= right) {
// Traverse from bottom to top along the left column
for (int i = bottom; i >= top; i--) {
result.Add(matrix[i][left]);
}
left++; // Move the left boundary to the right
}
}
return result;
}
}