Swift Spiral Matrix

Question

Question
Given an integer n, generate a square matrix filled with elements from 1 to n^2 in spiral order.

For example, Given n = 3,

You should return the following matrix: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

class Solution
{
    func generateMatrix(n: Int) -> [[Int]]
    {
        var matrix =
            [[Int]](count: n, repeatedValue: [Int](count: n, repeatedValue: 0))

        var left = 0
        var top = 0
        var right = n - 1
        var down = n - 1
        var count = 1

        while left <= right && top < down // shouble left <= right && top <= down

        {

            for j in (left...right)
            {

                matrix[top][j] = count
                count += 1
            }

            top += 1

            for i in (top...down)
            {

                matrix[i][right] = count
                count += 1
            }

            right -= 1

            for j in (left...right).reverse()
            {

                matrix[down][j] = count
                count += 1
            }
            down -= 1

            for i in (top...down).reverse()
            {

                matrix[i][left] = count
                count += 1
            }
            left += 1

        }

        return matrix
    }
}



var test = Solution()
var result = test.generateMatrix(3)
print(result)

This is my result, [ [ 1, 2, 3 ], [ 8, 0, 4 ], [ 7, 6, 5 ] ], the 9 is missing. I guess I should change my while loop to "left <= right && top <= down",but I got an error.

The error makes me so confusing. Since under the condition "left <= right && top <= down", variable top has no chance to get over variable down, however, the error alerts me range end < start.

Thank you so much for you help! Really appreciate your time.

Answer 1

Look like homework but I'll bite. Assuming i, j are the row and column indexes starting at 0, 0, the spiral movement can be described as follow:

1. Increase j until you hit the matrix boundary on the right
2. Increase i until you hit the matrix boundary at the bottom
3. Decrease j until you hit the matrix boundary on the left
4. Decrease i until you hit the matrix boundary at the top
5. Repeat step 1 - 4, substituting "matrix boundary" for "non-empty cell"

Here's the code:

let n = 3

// Init an all-zero matrix
var matrix = Array(repeating: Array(repeating: 0, count: n), count: n)

var i = 0
var j = 0

// These 2 variables control how we move the i and j cursors
// Initial move is from left to right
var deltaI = 0
var deltaJ = 1

for number in 1...(n*n) {
    matrix[i][j] = number

    let nextI = i + deltaI
    let nextJ = j + deltaJ

    // nextCellIsEmpty == true if:
    //      * nextI is within boundary of the matrix; and
    //      * nextJ is within boundary of the matrix; and
    //      * matrix[nextI][nextJ] is not taken
    let nextCellIsEmpty = (0..<n ~= nextI) && (0..<n ~= nextJ) && (matrix[nextI][nextJ] == 0)

    // If the next cell is not empty, we need to adjust how
    // the cursors move
    if !nextCellIsEmpty {
        if deltaJ == 1 { deltaI = 1; deltaJ = 0; }
        else if deltaI == 1 { deltaI = 0; deltaJ = -1; }
        else if deltaJ == -1 { deltaI = -1; deltaJ = 0; }
        else if deltaI == -1 { deltaI = 0; deltaJ = 1; }
    }

    i += deltaI
    j += deltaJ
}

matrix.forEach { print($0) }

~= is the "pattern match" operator. a..<b ~= c returns true if a <= c < b