# 54\_Spiral Matrix

Given a matrix of`mxn` *\_elements (* `m` *rows,* `n` \_columns), return all elements of the matrix in spiral order.

**Example 1:**

```
Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

Output:
 [1,2,3,6,9,8,7,4,5]
```

**Example 2:**

```
Input:
[
  [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]
```

## Solution

**Idea**:

* Solve the problem from the most outside layer to the center, one layer by one layer
* Take the most outside layer as an example, add the first n-1 elements from the first row, then add the first m-1 elements from the last column, then add the first n-1 elements from the last row in reversed order, then add the first m-1 elements from the first column in reversed order. In this order, the number of elements added each time is easy to find.
* Have a list represents the directions which are right, down, left, up
* After adding one element into the output, set its value to be "used", so that next time if we iterate to "used", we will change direction. The other two situations when needs to change direction are: 1) the row index is out of range; 2) the column index is out of range.

**Time Complexity**: $$O(m\*n)$$

**Space Complexity**: $$O(1)$$ not considering the output

```python
def spiralOrder(matrix):
    """
    :type matrix: List[List[int]]
    :rtype: List[int]
    """
    if not matrix :
        return []

    m = len(matrix)
    n = len(matrix[0])
    output = []
    shift = [[0,1], [1,0], [0,-1], [-1,0]]
    i = j = direction = 0 

    for _ in range(m*n) :
        output.append(matrix[i][j])
        matrix[i][j] = "used"
        i_new, j_new = i + shift[direction][0], j + shift[direction][1]
        if i_new not in range(m) or j_new not in range(n) or matrix[i_new][j_new] == "used" :
            direction = (direction + 1) % 4
            i_new, j_new = i + shift[direction][0], j + shift[direction][1]
        i, j = i_new, j_new
    return output
```

## Solution2 :

divide and conquer


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lei-d.gitbook.io/leetcode/matrix/54spiral-matrix.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.