Pramp Matrix Spiral Copy Problem

Given a 2D array (matrix) inputMatrix of integers, create a function spiralCopy that copies inputMatrix’s values into a 1D array in a spiral order, clockwise. Your function then should return that array. Analyze the time and space complexities of your solution.

Example:

input:  inputMatrix  = [ [1,    2,   3,  4,    5],
                         [6,    7,   8,  9,   10],
                         [11,  12,  13,  14,  15],
                         [16,  17,  18,  19,  20] ]

output: [1, 2, 3, 4, 5, 10, 15, 20, 19, 18, 17, 16, 11, 6, 7, 8, 9, 14, 13, 12]

See the illustration below to understand better what a clockwise spiral order looks like.

Clockwise Spiral Order

Constraints:

  • [time limit] 5000ms
  • [input] array.array.integer inputMatrix
    • 1 ≤ inputMatrix[0].length ≤ 100
    • 1 ≤ inputMatrix.length ≤ 100
  • [output] array.integer

Solution

func spiralCopy(inputMatrix: [[Int]]) -> [Int] {
    var result = [Int]()
    var pos = (row: 0, col: 0)
    var rowEnd = inputMatrix.count - 1
    var colEnd = inputMatrix[0].count - 1
    var isComplete: Bool {
        return rowEnd < 0 || colEnd < 0
    }
    
    while true {
        // move right
        guard !isComplete else { break }
        for _ in 0...colEnd {
            if !result.isEmpty {
                pos.col += 1
            }
            result += [inputMatrix[pos.row][pos.col]]
        }
        rowEnd -= 1

        // move down
        guard !isComplete else { break }
        for _ in 0...rowEnd {
            pos.row += 1
            result += [inputMatrix[pos.row][pos.col]]
        }
        colEnd -= 1
        
        // move left
        guard !isComplete else { break }
        for _ in (0...colEnd).reversed() {
            pos.col -= 1
            result += [inputMatrix[pos.row][pos.col]]
        }
        rowEnd -= 1
        
        // move up
        guard !isComplete else { break }
        for _ in (0...rowEnd).reversed() {
            pos.row -= 1
            result += [inputMatrix[pos.row][pos.col]]
        }
        colEnd -= 1
    }
    
    return result
}

Space and Time Complexity

This algorithm loops through all elements of the input array one time. We also create an output array with the same number of elements as the input array. Therefore, both space and time complexity are \(O(n) \).

Think Different

  • Index out of range.
  • Used pos.col < > colEnd instead of iterating up to colEnd.
  • Important to increment pos.row and pos.col prior to appending to avoid double append.
  • Move isComplete check outside of inner loops.
  • Put condition to check for first append at index (0,0).

Leave a Reply

Come See Me

San Francisco, CA
hello@ingax.com

See My Work