daily coding problem #65: Given a N by M matrix of numbers, print out the matrix in a clockwise spiral.

readme.md

Good morning! Here's your coding interview problem for today.

This problem was asked by Amazon.

Given a N by M matrix of numbers, print out the matrix in a clockwise spiral.

For example, given the following matrix:

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

You should print out the following:

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

Questions

is matrix well-formed and uniform? assuming yes -- meaning there are no extra elements in arrays and the matrix is exactly a rectangular shape.

assuming starting at 0,0

clockwise start is:

go right
go down
go left
go up

in a repeated pattern until all barriers have been hit

we need to keep track of the boundary wall positions:

top
right
bottom
left

Thoughts

the idea

rowIndex = 3, columnIndex = 4
top = right = bottom = left = null
currentPosition = 0,0

start at currentPosition, top = 0

go right until rightBoundary (null || columnIndex + 1), rightBoundary = 4, cp = 0,4
go down until bottomBoundary (null || rowIndex) + 1, bottomBoundary = 3, cp = 3,4
go left until leftBoundary (null || -1), leftBoundary = 0, cp = 3,0
go up until topBoundary (0), top = 1, cp = 1,0

go right until rightBoundary (4), rightBoundary = 3, cp = 1,3
go down until bottomBoundary(3), bottomBoundary = 2, cp = 2,3
go left until leftBoundary(0), leftBoundary = 1, cp = 2,1

if at any point going in any direction hits our boundary, the loop should stop

if going right, (cp.y + 1 = rightBoundary), break
if going down, (cp.x + 1 = bottomBoundary), break
if going left, (cp.y - 1 = leftBoundary), break
if going up, ( cp.x - 1 = topBoundary), break

Code

//these are indices
let topBoundary = 0
let rightBoundary = matrix[0].length
let bottomBoundary = matrix.length
let leftBoundary = -1

let cp = [0,0]  //starting position

//record the first element
const results = [].concat(matrix[cp[0]][cp[1]]) 

// where we temporary hold the results of each direction of movement
let holding

while (true) {
  //right
  if (cp[1] + 1 == rightBoundary) break
  holding = goRight(matrix, cp, rightBoundary)
  results.push(...holding)
  rightBoundary--
  cp[1] = rightBoundary

  //down
  if (cp[0] + 1 == bottomBoundary) break
  holding = goDown(matrix, cp, bottomBoundary)
  results.push(...holding)
  bottomBoundary--
  cp[0] = bottomBoundary

  //left
  if (cp[1] - 1 == leftBoundary) break
  holding = goLeft(matrix, cp, leftBoundary)
  results.push(...holding)
  leftBoundary++
  cp[1] = leftBoundary

  //up
  if (cp[0] - 1 == topBoundary) break
  holding = goUp(matrix, cp, topBoundary)
  results.push(...holding)
  topBoundary++
  cp[0] = topBoundary
}


console.log('results', results)
console.log('is it: ', JSON.stringify(results) === JSON.stringify(solution))

function goRight(matrix, cp, rightBoundary) {
  const [x, y] = cp
  const output = []
  for (let i = y + 1; i < rightBoundary; i++) {
    output.push(matrix[x][i])
  }
  return output
}

function goDown(matrix, cp, bottomBoundary) {
  const [x, y] = cp
  const output = []
  for (let i = x + 1; i < bottomBoundary; i++) {
    output.push(matrix[i][y])
  }
  return output
}

function goLeft(matrix, cp, topBoundary) {
  const [x, y] = cp
  const output = []
  for (let i = y - 1; i > leftBoundary; i--) {
    output.push(matrix[x][i])
  }
  return output
}

function goUp(matrix, cp, topBoundary) {
  const [x, y] = cp
  const output = []
  for (let i = x - 1; i > topBoundary; i--) {
    output.push(matrix[i][y])
  }
  return output
}