Spiral Matrix 🧠

LeetCode Link: Spiral Matrix

Difficulty: Medium

Problem Explanation 📝

Problem: LeetCode 54 - Spiral Matrix

Description: Given an m x n matrix, return all elements of the matrix in spiral order.

Intuition: We can traverse the matrix in a spiral order by simulating the movement in four directions: right, down, left, and up. To keep track of the visited elements, we can maintain four boundaries: top, bottom, left, and right.

Approach:

1. Initialize four variables: top = 0, bottom = m - 1, left = 0, right = n - 1.
2. Loop until top <= bottom and left <= right:

• Traverse from left to right along the top boundary and increment top.
• Traverse from top to bottom along the right boundary and decrement right.
• Traverse from right to left along the bottom boundary and decrement bottom.
• Traverse from bottom to top along the left boundary and increment left.

3. Keep adding the elements encountered during the traversal to the result vector.

⌛ Time Complexity: The time complexity of this approach is O(m * n), where m is the number of rows and n is the number of columns in the matrix.

💾 Space Complexity: The space complexity is O(1) as we are not using any additional space.

Solutions 💡

Cpp 💻

class Solution {
  public:
    vector<int> spiralOrder(vector<vector<int>> &matrix) {
        vector<int> result;

        if (matrix.empty()) {
            return result;
        }

        int m = matrix.size();
        int n = matrix[0].size();
        int top = 0, bottom = m - 1, left = 0, right = n - 1;

        while (top <= bottom && left <= right) {
            // Traverse from left to right along the top boundary
            for (int i = left; i <= right; i++) {
                result.push_back(matrix[top][i]);
            }

            top++;

            // Traverse from top to bottom along the right boundary
            for (int i = top; i <= bottom; i++) {
                result.push_back(matrix[i][right]);
            }

            right--;

            // Traverse from right to left along the bottom boundary
            if (top <= bottom) {
                for (int i = right; i >= left; i--) {
                    result.push_back(matrix[bottom][i]);
                }

                bottom--;
            }

            // Traverse from bottom to top along the left boundary
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    result.push_back(matrix[i][left]);
                }

                left++;
            }
        }

        return result;
    }
};

Python 🐍

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix:
            return []

        rows, cols = len(matrix), len(matrix[0])
        result = []

        # Define the boundaries of the current layer
        top, bottom, left, right = 0, rows - 1, 0, cols - 1

        while top <= bottom and left <= right:
            # Traverse the top row
            for j in range(left, right + 1):
                result.append(matrix[top][j])
            top += 1

            # Traverse the right column
            for i in range(top, bottom + 1):
                result.append(matrix[i][right])
            right -= 1

            # Traverse the bottom row
            if top <= bottom:  # Avoid duplicate traversal
                for j in range(right, left - 1, -1):
                    result.append(matrix[bottom][j])
                bottom -= 1

            # Traverse the left column
            if left <= right:  # Avoid duplicate traversal
                for i in range(bottom, top - 1, -1):
                    result.append(matrix[i][left])
                left += 1

        return result