algoadvance

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

Clarifying Questions

  1. Constraints on the matrix size?
    • Both the number of rows m and columns n can range from 1 to 10. This ensures that our solution doesn’t need to concern itself with extreme memory management or performance issues.
  2. What is the range of the matrix’s elements?
    • The elements of the matrix can be any integer.
  3. Are there any constraints regarding time complexity?
    • Since the dimensions are relatively small, the problem can be solved with a time complexity of O(m*n) to ensure efficiency.
  4. Should we consider any special cases?
    • Yes, consider matrices with only one row or one column, and the smallest case where m = 1 and n = 1.

Strategy

  1. Boundary Pointers: Use four boundary pointers (top, down, left, right) to keep track of the edges of the matrix that are not yet traversed.
  2. Direction Control: Track the current direction of traversal (right, down, left, up) using an index.
  3. Traversal Loop:
    • Traverse the matrix in the specified direction.
    • After completing a direction, update the respective boundary pointer.
    • Switch direction and repeat until all elements are covered.

Code

def spiralOrder(matrix):
    if not matrix:
        return []

    # Initialize boundary pointers
    top, down = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    result = []
    direction = 0  # 0 -> right, 1 -> down, 2 -> left, 3 -> up

    while top <= down and left <= right:
        if direction == 0:  # Move right
            for col in range(left, right + 1):
                result.append(matrix[top][col])
            top += 1
        elif direction == 1:  # Move down
            for row in range(top, down + 1):
                result.append(matrix[row][right])
            right -= 1
        elif direction == 2:  # Move left
            for col in range(right, left - 1, -1):
                result.append(matrix[down][col])
            down -= 1
        elif direction == 3:  # Move up
            for row in range(down, top - 1, -1):
                result.append(matrix[row][left])
            left -= 1
        
        # Update direction for next iteration
        direction = (direction + 1) % 4

    return result

Time Complexity

Try our interview co-pilot at AlgoAdvance.com