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.
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).
