34. Spiral Matrix

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

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

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]

Problem Breakdown:

1. Define four boundaries: top, bottom, left, right. These shrink inward as we traverse each layer of the spiral.

• result = []
  top, bottom = 0, len(matrix) - 1
  left, right = 0, len(matrix[0]) - 1

2. Traverse right across the top row, then move the top boundary down.

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

3. Traverse down the right column, then move the right boundary left.

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

4. Traverse left across the bottom row (if still valid), then traverse up the left column (if still valid). Adjust boundaries after each.

•     if top <= bottom:
          for j in range(right, left - 1, -1):
              result.append(matrix[bottom][j])
          bottom -= 1
      if left <= right:
          for i in range(bottom, top - 1, -1):
              result.append(matrix[i][left])
          left += 1

5. Continue until all boundaries have crossed. Return the result.

• return result

Summary:

Use four boundaries (top, bottom, left, right) that shrink inward. Traverse in order: right along top, down along right, left along bottom, up along left. Check boundary validity before bottom and left traversals to avoid duplicates.

Time and Space Complexity:

Time Complexity: O(m * n) - we visit every element exactly once.

Space Complexity: O(1) - excluding the output array.

Python Solution:

def spiralOrder(matrix):
    result = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    while top <= bottom and left <= right:
        for j in range(left, right + 1):
            result.append(matrix[top][j])
        top += 1
        for i in range(top, bottom + 1):
            result.append(matrix[i][right])
        right -= 1
        if top <= bottom:
            for j in range(right, left - 1, -1):
                result.append(matrix[bottom][j])
            bottom -= 1
        if left <= right:
            for i in range(bottom, top - 1, -1):
                result.append(matrix[i][left])
            left += 1
    return result

JavaScript Solution:

var spiralOrder = function(matrix) {
    const result = [];
    let top = 0, bottom = matrix.length - 1;
    let left = 0, right = matrix[0].length - 1;
    while (top <= bottom && left <= right) {
        for (let j = left; j <= right; j++) result.push(matrix[top][j]);
        top++;
        for (let i = top; i <= bottom; i++) result.push(matrix[i][right]);
        right--;
        if (top <= bottom) {
            for (let j = right; j >= left; j--) result.push(matrix[bottom][j]);
            bottom--;
        }
        if (left <= right) {
            for (let i = bottom; i >= top; i--) result.push(matrix[i][left]);
            left++;
        }
    }
    return result;
};

Java Solution:

class Solution {
    public List spiralOrder(int[][] matrix) {
        List result = new ArrayList<>();
        int top = 0, bottom = matrix.length - 1;
        int left = 0, right = matrix[0].length - 1;
        while (top <= bottom && left <= right) {
            for (int j = left; j <= right; j++) result.add(matrix[top][j]);
            top++;
            for (int i = top; i <= bottom; i++) result.add(matrix[i][right]);
            right--;
            if (top <= bottom) {
                for (int j = right; j >= left; j--) result.add(matrix[bottom][j]);
                bottom--;
            }
            if (left <= right) {
                for (int i = bottom; i >= top; i--) result.add(matrix[i][left]);
                left++;
            }
        }
        return result;
    }
}