54_Spiral Matrix

Given a matrix ofmxn _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

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