algoadvance

Leetcode 54. Spiral Matrix

Problem Statement

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

Clarifying Questions

  1. Can the matrix be empty?
    • Yes, handle the case of an empty matrix by returning an empty list.
  2. Does the matrix always have integers as elements?
    • Yes, the matrix will contain integer elements only.
  3. Are there any constraints on the size of the matrix?
    • No explicit constraints, but your solution should handle typical input sizes efficiently.

Strategy

To solve this problem, we will use a simulation approach, where we simulate the process of traversing the matrix in spiral order. The matrix can be traversed layer by layer, and in each layer we can follow a specific direction order: right, down, left, and up. We keep track of our boundaries to know when to change direction. Here’s the detailed strategy:

  1. Initialize Boundaries: Set the initial boundaries for rows and columns.
  2. Direction Vectors: Use direction vectors to simplify the movement in the matrix.
  3. Traversal:
    • Move to the right until the right boundary is reached.
    • Move down until the bottom boundary is reached.
    • Move left until the left boundary is reached.
    • Move up until the top boundary is reached.
    • After completing every cycle (right, down, left, up), adjust the boundaries accordingly.
  4. Completion: Repeat the above steps until all elements have been traversed.

Implementation

#include <vector>

std::vector<int> spiralOrder(const std::vector<std::vector<int>>& matrix) {
    if(matrix.empty()) return {};

    int m = matrix.size();
    int n = matrix[0].size();
    std::vector<int> result;
    
    int left = 0;
    int right = n - 1;
    int top = 0;
    int bottom = m - 1;

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

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

        if (top <= bottom) { // Check if we still have rows to process
            // Traverse from right to left along the bottom row
            for (int col = right; col >= left; --col) {
                result.push_back(matrix[bottom][col]);
            }
            --bottom; // Move the bottom boundary up
        }

        if (left <= right) { // Check if we still have columns to process
            // Traverse from bottom to top along the left column
            for (int row = bottom; row >= top; --row) {
                result.push_back(matrix[row][left]);
            }
            ++left; // Move the left boundary to the right
        }
    }

    return result;
}

Time Complexity

The time complexity of this solution is O(m * n), where m is the number of rows and n is the number of columns. This is because every element in the matrix is visited exactly once. The space complexity is O(1) (excluding the space required for the output list), as we only use a few additional variables to manage the boundaries and directions.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI