Spiral Matrix medium

Problem Statement

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

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]

Steps

The core idea is to simulate the spiral traversal using four pointers representing the boundaries of the unvisited portion of the matrix. These pointers define the top, bottom, left, and right boundaries. We iteratively traverse the edges of this unvisited rectangle, shrinking the rectangle's size with each iteration until all elements are visited.

1. Initialization: Set four pointers: top, bottom, left, and right to the boundaries of the matrix.
2. Iteration: While the left pointer is less than or equal to the right pointer, and the top pointer is less than or equal to the bottom pointer, perform the following: a. Traverse Right: Traverse from left to right, adding elements to the result vector. b. Increment Top: Increment the top pointer. c. Traverse Down: Traverse from top to bottom, adding elements to the result vector. d. Decrement Right: Decrement the right pointer. e. Check for Empty Rectangle: If left > right or top > bottom, break the loop (to avoid redundant processing if the matrix was already fully traversed). f. Traverse Left: Traverse from right to left, adding elements to the result vector. g. Decrement Bottom: Decrement the bottom pointer. h. Traverse Up: Traverse from bottom to top, adding elements to the result vector. i. Increment Left: Increment the left pointer.
3. Return: Return the result vector containing all elements in spiral order.

Explanation

The algorithm systematically reduces the size of the unvisited portion of the matrix in each iteration. It mimics the way a person would naturally traverse a matrix in a spiral pattern. By adjusting the boundary pointers after each edge traversal, the algorithm ensures that no element is missed and each element is visited exactly once.

Code

#include <vector>

using namespace std;

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<int> result;
    if (matrix.empty()) return result;

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

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

        // Traverse Down
        for (int i = top; i <= bottom; i++) {
            result.push_back(matrix[i][right]);
        }
        right--;

        if (left > right || top > bottom) break; // Check for empty rectangle

        // Traverse Left
        for (int i = right; i >= left; i--) {
            result.push_back(matrix[bottom][i]);
        }
        bottom--;

        // Traverse Up
        for (int i = bottom; i >= top; i--) {
            result.push_back(matrix[i][left]);
        }
        left++;
    }

    return result;
}

Complexity

• Time Complexity: O(m*n), where 'm' is the number of rows and 'n' is the number of columns. We visit each element exactly once.
• Space Complexity: O(1) (excluding the output vector). The algorithm uses a constant amount of extra space to store the boundary pointers. The space used by the output vector is not considered in the space complexity analysis of the algorithm itself.