54. Spiral Matrix – Leetcode Solutions

June 17, 2024

Table of Contents

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 result

Explanation:

Initialization:
- result is an empty list where the elements in spiral order will be stored.
- top and bottom are initialized to the first and last row indices, respectively.
- left and right are initialized to the first and last column indices, respectively.
Loop Until Boundaries Meet:
- The main loop continues as long as top <= bottom and left <= right.
Traverse the Top Row:
- Move from the left boundary to the right boundary along the top row, appending elements to result.
- Increment the top boundary to move it downwards.
Traverse the Right Column:
- Move from the top boundary to the bottom boundary along the right column, appending elements to result.
- Decrement the right boundary to move it leftwards.
Check and Traverse the Bottom Row:
- If top <= bottom, move from the right boundary to the left boundary along the bottom row, appending elements to result.
- Decrement the bottom boundary to move it upwards.
Check and Traverse the Left Column:
- If left <= right, move from the bottom boundary to the top boundary along the left column, appending elements to result.
- Increment the left boundary to move it rightwards.
Return the Result:
- After the loop completes, return the result list containing the elements in spiral order.

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;
    }
}

54. Spiral Matrix – Leetcode Solutions

Description:

Solution in Python:

Solution in Javascript:

Solution in Java:

Solution in C#:

Popular

384. Shuffle an Array – Leetcode Solutions

122. Best Time to Buy and Sell Stock II – Leetcode Solutions

382. Linked List Random Node – Leetcode Solutions

235. Lowest Common Ancestor of a Binary Search Tree – Leetcode Solutions

67. Add Binary – Leetcode Solutions

312. Burst Balloons – Leetcode Solutions

100. Same Tree – Leetcode Solutions

54. Spiral Matrix – Leetcode Solutions

Description:

Solution in Python:

Solution in Javascript:

Solution in Java:

Solution in C#:

Related Post

Popular