54. Spiral Matrix

🟧 Medium

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

Example 1

matrix

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

Example 2

matrix

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]

Constraints

• m == matrix.length

• n == matrix[i].length

• 1 <= m, n <= 10

• -100 <= matrix[i][j] <= 100

Hint 1

Well for some problems, the best way really is to come up with some algorithms for simulation. Basically, you need to simulate what the problem asks us to do.

Hint 2

We go boundary by boundary and move inwards. That is the essential operation. First row, last column, last row, first column, and then we move inwards by 1 and repeat. That's all. That is all the simulation that we need.

Hint 3

Think about when you want to switch the progress on one of the indexes. If you progress on i out of [i, j], you'll shift in the same column. Similarly, by changing values for j, you'd be shifting in the same row. Also, keep track of the end of a boundary so that you can move inwards and then keep repeating. It's always best to simulate edge cases like a single column or a single row to see if anything breaks or not.

Solution

My Solution

func spiralOrder(matrix [][]int) []int {
    m, n := len(matrix), len(matrix[0])
    l, r, up, down := 0, n-1, 0, m-1
    nums := make([]int, 0, m*n)

    for {
        for i:= l; i<= r; i++ {
            nums = append(nums, matrix[up][i])
        }
        up++
        if up > down {
            break
        }

        for i:=up; i<=down; i++ {
            nums = append(nums, matrix[i][r])
        }
        r--
        if l>r {
            break
        }

        for i:=r; i>=l; i-- {
            nums = append(nums, matrix[down][i])
        }
        down--
        if down < up {
            break
        }

        for i:= down; i>=up; i-- {
            nums = append(nums, matrix[i][l])
        }
        l++
        if l > r {
            break
        }
    }

    return nums
}

Optimal solution

func spiralOrder(matrix [][]int) []int {
    if len(matrix) == 0 {
        return []int{}
    }

    top, bottom := 0, len(matrix)-1
    left, right := 0, len(matrix[0])-1
    result := []int{}

    for top <= bottom && left <= right {
        // Yuqoridan o‘ngga
        for i := left; i <= right; i++ {
            result = append(result, matrix[top][i])
        }
        top++

        // O‘ngdan pastga
        for i := top; i <= bottom; i++ {
            result = append(result, matrix[i][right])
        }
        right--

        // Pastdan chapga
        if top <= bottom {
            for i := right; i >= left; i-- {
                result = append(result, matrix[bottom][i])
            }
            bottom--
        }

        // Chapdan yuqoriga
        if left <= right {
            for i := bottom; i >= top; i-- {
                result = append(result, matrix[i][left])
            }
            left++
        }
    }

    return result
}

result

Leetcode: link