We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Spiral Matrix

Difficulty: Medium

Problem Description

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

Key Insights

  • The problem requires traversing a 2D array in a spiral pattern: right across the top row, then down the right column, then left across the bottom row, and finally up the left column.
  • We need to manage boundaries (top, bottom, left, right) to ensure we do not revisit elements.
  • The traversal continues until all elements are added to the result.

Space and Time Complexity

Time Complexity: O(m * n) - where m is the number of rows and n is the number of columns, as we need to visit each element once. Space Complexity: O(1) - if we consider the output list separate, the space complexity is O(m * n) due to the storage of results, but the algorithm itself uses constant space.

Solution

The approach uses a simulation of the spiral traversal by maintaining four boundaries (top, bottom, left, right). The algorithm iterates through the matrix while adjusting these boundaries after each complete direction of traversal (right, down, left, and up).

  1. Initialize boundaries for the current layer of the matrix.
  2. Traverse from left to right along the top row, then increment the top boundary.
  3. Traverse from top to bottom along the right column, then decrement the right boundary.
  4. If there are remaining rows, traverse from right to left along the bottom row, then decrement the bottom boundary.
  5. If there are remaining columns, traverse from bottom to top along the left column, then increment the left boundary.
  6. Repeat until all boundaries converge.

Code Solutions

def spiralOrder(matrix):
    if not matrix:
        return []
    
    result = []
    top, bottom, left, right = 0, len(matrix) - 1, 0, len(matrix[0]) - 1
    
    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
        
        # Traverse from top to bottom along the right column
        for i in range(top, bottom + 1):
            result.append(matrix[i][right])
        right -= 1
        
        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
            
        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
            
    return result
← Back to All Questions