1
\$\begingroup\$

A whiteboarding challenge: Given a 2D array (matrix) inputMatrix of integers, create a function spiralCopy that copies inputMatrix's values into a 1D array in a clockwise spiral order. Your function then should return that array.

inputMatrix = [
  [1, 2, 3, 4, 5, 6],
  [7, 8, 9, 10, 11, 12],
  [13, 14, 15, 16, 17, 18],
  [19, 20, 21, 22, 23, 24],
  [25, 26, 27, 28, 29, 30],
  [31, 32, 33, 34, 35, 36]
]

const spiralCopy = (matrix) => {
  const spiralLength = matrix.length * matrix[0].length;
  const spiral = [];

  let iLeftRightStart = 0; // +1
  let iLeftRightEnd = matrix[0].length; // -1
  let leftRightPosition = 0; // +1
  let iTopBottomStart = 1; // +1
  let iTopBottomEnd = matrix.length; // -1
  let topBottomPosition = matrix[0].length - 1; // -1
  let iRightLeftStart = matrix[0].length - 2; // -1
  let iRightLeftEnd = 0; // +1
  let rightLeftPosition = matrix.length - 1; // -1
  let iBottomTopStart = matrix.length - 2; // -1
  let iBottomTopEnd = 1; // +1                      
  let bottomTopPosition = 0; // +1

  const leftToRight = (iStart, iEnd, position) => {
    for (let i = iStart; i < iEnd; i++) {
      spiral.push(matrix[position][i]);
    }
  }

  const topToBottom = (iStart, iEnd, position) => {
    for (let i = iStart; i < iEnd; i++) {
      spiral.push(matrix[i][position]);
    }
  }

  const rightToLeft = (iStart, iEnd, position) => {
    for (let i = iStart; i >= iEnd; i--) {
      spiral.push(matrix[position][i]);
    }
  }

  const bottomToTop = (iStart, iEnd, position) => {
    for (let i = iStart; i >= iEnd; i--) {
      spiral.push(matrix[i][position]);
    }
  }

  while (spiral.length < spiralLength) {
    leftToRight(iLeftRightStart, iLeftRightEnd, leftRightPosition);
    topToBottom(iTopBottomStart, iTopBottomEnd, topBottomPosition);
    rightToLeft(iRightLeftStart, iRightLeftEnd, rightLeftPosition);
    bottomToTop(iBottomTopStart, iBottomTopEnd, bottomTopPosition);
    iLeftRightStart++;
    iLeftRightEnd--;
    leftRightPosition++;
    iTopBottomStart++;
    iTopBottomEnd--;
    topBottomPosition--;
    iRightLeftStart--;
    iRightLeftEnd++;
    rightLeftPosition--;
    iBottomTopStart--;
    iBottomTopEnd++;
    bottomTopPosition++;
  }
  return spiral;
}
console.log(spiralCopy(inputMatrix));
// prints [1, 2, 3, 4, 5, 6, 12, 18, 24, 30, 36, 35, 34, 33, 32, 31, 25, 19, 13, 7, 8, 9, 10, 11, 17, 23, 29, 28, 27, 26, 20, 14, 15, 16, 22, 21]

So the function works and runs with time complexity of O(N). However, I don't like that I'm using 12 different variables which I then increment/decrement. How can this be consolidated, and is it possible to make the algorithm even faster due to the instant access of JavaScript arrays?

\$\endgroup\$
1
\$\begingroup\$

First, I normally like using local functions to clean up code like you're doing with topToBottom, rightToLeft and similar functions. I don't think it's helping here though. You've extracted four nearly identical pieces of code into four nearly identical functions. It may be possible to extract the common aspects out into a single function, then you'd have the one function being called four times. Until then though, I'd recommend just inlining the functions:

const spiralCopy = (matrix) => {
  const spiralLength = matrix.length * matrix[0].length;
  const spiral = [];

  let iLeftRightStart = 0; // +1
  let iLeftRightEnd = matrix[0].length; // -1
  let leftRightPosition = 0; // +1
  let iTopBottomStart = 1; // +1
  let iTopBottomEnd = matrix.length; // -1
  let topBottomPosition = matrix[0].length - 1; // -1
  let iRightLeftStart = matrix[0].length - 2; // -1
  let iRightLeftEnd = 0; // +1
  let rightLeftPosition = matrix.length - 1; // -1
  let iBottomTopStart = matrix.length - 2; // -1
  let iBottomTopEnd = 1; // +1                      
  let bottomTopPosition = 0; // +1

  while (spiral.length < spiralLength) {
    for (let i = iLeftRightStart; i < iLeftRightEnd; i++) {
      spiral.push(matrix[leftRightPosition][i]);
    }

    for (let i = iTopBottomStart; i < iTopBottomEnd; i++) {
      spiral.push(matrix[i][topBottomPosition]);
    }

    for (let i = iRightLeftStart; i >= iRightLeftEnd; i--) {
      spiral.push(matrix[rightLeftPosition][i]);
    }

    for (let i = iBottomTopStart; i >= iBottomTopEnd; i--) {
      spiral.push(matrix[i][bottomTopPosition]);
    }

    iLeftRightStart++;
    iLeftRightEnd--;
    leftRightPosition++;
    iTopBottomStart++;
    iTopBottomEnd--;
    topBottomPosition--;
    iRightLeftStart--;
    iRightLeftEnd++;
    rightLeftPosition--;
    iBottomTopStart--;
    iBottomTopEnd++;
    bottomTopPosition++;
  }
  return spiral;
}

The common variable names alone make it clear what direction each loop is responsible for, and if you still wanted an explicit "name" associated with each loop, you could add a comment.

As for the bulk of separate variables, it seems like they could fall into a class (or similar grouping mechanism). You have a start bound, an end bound, and a current position. Each bound group also has a specific "accessor" (like matrix[i][position]), and a specific way its position is updated. If all five pieces are grouped, you can apply a common function (advance) to the group to isolate the common behavior:

inputMatrix = [
  [1, 2, 3, 4, 5, 6],
  [7, 8, 9, 10, 11, 12],
  [13, 14, 15, 16, 17, 18],
  [19, 20, 21, 22, 23, 24],
  [25, 26, 27, 28, 29, 30],
  [31, 32, 33, 34, 35, 36]
]

// This arguably isn't necessary, but it reduces some bulk in spiralCopy
// Accessor is a function that accepts i and the bound's position, and 
//   returns the number there.
// PositionAdvancer is a function that takes the current position, and returns
//   the next position
const newBounds = (start, end, position, positionAdvancer, accessor) =>
    ({start: start, end: end,
      position: position, 
      positionAdvancer: positionAdvancer,
      accessor: accessor});

// For brevity later
const inc = (i) => i + 1;
const dec = (i) => i - 1;

const spiralCopy = (matrix) => {
    const spiralLength = matrix.length * matrix[0].length;
    const spiral = [];

    function advance(bounds) {
        const {start, end, position, accessor, positionAdvancer} = bounds;

        // Decide what comparing and i advancing functions to use
        const [comp, adv] = start < end ?
                                [(a, b) => a < b, inc]
                                : [(a, b) => a >= b, dec];

        // Handle all the common behavior
        for (let i = start; comp(i, end); i = adv(i)) {
            spiral.push(accessor(i, position));
        }

        oppAdv = adv === inc ? dec : inc

        bounds.start = adv(bounds.start);
        bounds.end = oppAdv(bounds.end);
        bounds.position = positionAdvancer(bounds.position);
    }

    const leftRight = newBounds(0, matrix[0].length, 0, inc,
                                (i, p) => matrix[p][i]);

    const topBottom = newBounds(1, matrix.length, matrix[0].length - 1, dec,
                                (i, p) => matrix[i][p]);

    const rightLeft = newBounds(matrix[0].length - 2, 0, matrix.length - 1, dec,
                                (i, p) => matrix[p][i]);

    const bottomTop = newBounds(matrix.length - 2, 1, 0, inc,
                                (i, p) => matrix[i][p]);

    while (spiral.length < spiralLength) {
        advance(leftRight);
        advance(topBottom);
        advance(rightLeft);
        advance(bottomTop);
    }

    return spiral;
}

Now, I can't say that I necessarily recommend this in its entirety. advance got bulkier the longer I looked at it, and:

const got = spiralCopy(inputMatrix);
const expected = [1, 2, 3, 4, 5, 6, 12, 18, 24, 30, 36, 35, 34, 33, 32, 31, 25, 19, 13, 7, 8, 9, 10, 11, 17, 23, 29, 28, 27, 26, 20, 14, 15, 16, 22, 21];

if (got === expected) {
    console.log("Passed");

} else {
    console.log("Failed");
    console.log(got);
    console.log(expected);
}

Failed
[1, 2, 3, 4, 5, 6, 12, 18, 24, 30, 36, 35, 34, 33, 32, 31, 25, 19, 13, 7, 8, 9, 10, 11, 17, 23, 29, 28, 27, 26, 20, 14, 15, 16, 22, 21, 15]
[1, 2, 3, 4, 5, 6, 12, 18, 24, 30, 36, 35, 34, 33, 32, 31, 25, 19, 13, 7, 8, 9, 10, 11, 17, 23, 29, 28, 27, 26, 20, 14, 15, 16, 22, 21]

Ouch. For some reason, it insists on circling back up to 15 at the end. I can't for the life of me figure out why. I've already spent a good like hour and a bit on this though, and didn't want the alternative solution to go to waste.

This solution was mostly how I'd approach it in Clojure, and it doesn't translate 100% to Javascript given the bulk in some places. You still may be able to draw inspiration from it though. My primary goal here was to reduce the redundancy however I could, not adhere to idiomatic Javascript (as I don't write JS very often honestly).


Oh, and I increased indentation to use four-spaces, as I find that it's more readable. There doesn't seem to be a good consensus on what should be used though, so take that with a grain of salt.

\$\endgroup\$
2
\$\begingroup\$

Travel directions

You can imagine this problem being extended to a 3D array. That would mean you have 6 directions, which using your approach would mean half as much code again, and 4D array would have 8 directions. That would double the amount of code. This becomes impractical as you get to higher dimensions.

If you break the problem into a simpler model. Move in a direction for distance collecting items as you go then turn, every second turn decrease the distance, until zero.

A direction can be represented as a vector {x,y} that is right {1,0}, down {0,1} and so on. You store them in an array of vectors in the order you need to use.

I have solved assuming that the array given is a rhombus . You have not indicated if this is true or not. However it only requires a small modification to handle non rhombus arrays.

The result is something like

function spiral(arr) {
    var count, curDir, dist, size, x = 0, y = 0, dir = 0;
    const res = [], directions = [{x: 1, y: 0}, {x: 0, y: 1}, {x: -1, y: 0}, {x: 0, y: -1}];
    curDir = directions[0];
    dist = size = arr.length;
    count = size ** 2;
    while (count--) { 
        res.push(arr[y][x]);
        if (!--dist) {
            curDir = directions[++dir % 4];
            if (dir % 2) { size -- }
            dist = size;
        }
        x += curDir.x;
        y += curDir.y;
    }
    return res;
}

To test the function create some readable test arrays. The snippet has arrays that when processed will have values in order, so that it is easy to see if the result is correct.

[[
      [1, 2, 3, 4, 5, 6],
      [20, 21, 22, 23, 24, 7],
      [19, 32, 33, 34, 25, 8],
      [18, 31, 36, 35, 26, 9],
      [17, 30, 29, 28, 27, 10],
      [16, 15, 14, 13, 12, 101]
  ], [
      [1, 2, 3, 4, 5],
      [16, 17, 18, 19, 6],
      [15, 24, 25, 20, 7],
      [14, 23, 22, 21, 8],
      [13, 12, 11, 10, 9],
  ], [
      [1, 2, 3, 4],
      [12, 13, 14, 5],
      [11, 16, 15, 6],
      [10, 9, 8, 7],
  ], [
      [1, 2, 3],
      [8, 9, 4],
      [7, 6, 5],
  ], [
      [1, 2],
      [4, 3],
  ], [[1]]
].reverse().forEach(arr => console.log(spiral(arr).join(",")));


function spiral(arr) {
    var count, curDir, dist, size, x = 0, y = 0, dir = 0;
    const res = [], directions = [{x: 1, y: 0}, {x: 0, y: 1}, {x: -1, y: 0}, {x: 0, y: -1}];
    curDir = directions[0];
    dist = size = arr.length;
    count = size ** 2;
    while (count--) { 
        res.push(arr[y][x]);
        if (!--dist) {
            curDir = directions[++dir % 4];
            if (dir % 2) { size -- }
            dist = size;
        }
        x += curDir.x;
        y += curDir.y;
    }
    return res;
}

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.