CODEWITHSUNDEEP
javascriptarraysalgorithm
Patrick
Patrick

Reputation: 57

Spiral traversal of an array in JavaScript

I'm working through a coding problem and writing a function that will traverse a nested array in a snail-like pattern (example here).

For example, given input of [[1,2,3], [8,9,4], [7,6,5]], the function should output [1,2,3,4,5,6,7,8,9].

Within my main function, I created 4 functions to traverse the array in all directions. At each step I push the value at the current grid position and check a flag array to determine if the next position has been visited yet.

I have two problems:

  1. I couldn't clone the array passed as an argument successfully. Even if I used array.slice(0), the new flagsArray seems to be functioning as a pointer to array and when I modify flagsArray, the changes are reflected in array. Why is that?

My approach to cloning seems to work when I run this test:

var array = [0, 1];
var array_clone = array.slice(0);
array_clone[2] = 3;
console.log(array); // No changes to array
  1. I get flagsArray[(i + 1)] is undefined error while executing traverseDown(). This looks like trying to read an index beyond flagsArray. But if I check for flagsArray[i + 1][j] === false && i < flagsArray.length in a while loop, shouldn't the loop just stop once it tries to read beyond the array? For one because flagsArray[flags.Array.length] would be undefined, therefore not equal to false, and the other reason being that I check also for i being within the flagsArray range.

Here's my function:

snail = function(array) {
  console.log(array);
  var output = [];

  var flagsArray = array.slice(0);

  // Populating flagsArray with false values
  // False = index not visited yet
  for (var i = 0; i < flagsArray.length; i++) {
    for (var j = 0; j < flagsArray[i].length; j++) {
      flagsArray[i][j] = false;
    }
  }
  var i = 0;
  var j = 0;

    var traverseRight = function() {
    while (flagsArray[i][j + 1] === false && j < flagsArray[i].length) {
      console.log(flagsArray[i][j].length + 'Traversing right Index traversed: [' + i + '][' + j +'] Flag before: ' + flagsArray[i][j] + 'Element pushed: ' + array[i][j]);
      output.push(array[i][j]);
      flagsArray[i][j] = true;
      j++;
    } 
  }

  var traverseDown = function() {
    while (flagsArray[i + 1][j] === false && i < flagsArray.length) {
      console.log('Traversing Down Index traversed: [' + i + '][' + j +'] Flag before: ' + flagsArray[i][j] + 'Element pushed: ' + array[i][j]);
      output.push(array[i][j]);
      flagsArray[i][j] = true;
      i++;
    }
  }

  var traverseLeft = function() {
    while (array[i][j - 1] === false && j >= 0) {
      console.log('Traversing left Index traversed: [' + i + '][' + j +'] Flag before: ' + flagsArray[i][j] + 'Element pushed: ' + array[i][j]);
      output.push(array[i][j]);
      flagsArray[i][j] = true;
      j--;
    }
  }

  var traverseUp = function() {
    while (array[i][j] === false && j >= 0) {
      console.log('Traversing Up Index traversed: [' + i + '][' + j +'] Flag before: ' + flagsArray[i][j] + 'Element pushed: ' + array[i][j]);
      output.push(array[i][j]);
      flagsArray[i][j] = true;
      i--;
    }
  }

  while (flagsArray[i][j + 1] === false) {
    traverseRight();
    traverseDown();
    traverseLeft();
    traverseUp();
  } 
  return output;
}

console.log(snail([[1,2,3],[8,9,4],[7,6,5]]));

Upvotes: 3

Views: 2345

Answers (2)

Lior Elrom
Lior Elrom

Reputation: 20852

Spiral Array (ES6)

Try this:

function spiral(array) {
    const matrix = [...array];
    const arr = [];

    while (matrix.length) {
        arr.push(
            ...matrix.shift(),
            ...matrix.map(a => a.pop()),
            ...matrix.pop().reverse(),
            ...matrix.map(a => a.shift()).reverse()
        );
    }
    return arr;
}

Upvotes: -1

Michael Laszlo
Michael Laszlo

Reputation: 12239

Question 1

I couldn't clone the array passed as an argument successfully. Even if I used array.slice(0), the new flagsArray seems to be functioning as a pointer to array and when I modify flagsArray, the changes are reflected in array. Why is that?

It's because you have a two-dimensional array and you've only made a copy of the outer array. Each of its elements is an original inner array.

To make a deep copy of array that we can manipulate without altering the original, we must copy each of the inner arrays:

var flags = new Array(array.length);
for (var i = 0; i < array.length; ++i) {
  flags[i] = array[i].slice();
}

(Note: I have taken the liberty of renaming flagsArray to flags. Also note that slice() can be called without an argument to copy the array starting from index 0.)

We can use Array.map to do the same thing more concisely:

var flags = array.map(function (subarray) {
  return subarray.slice();
});

But there's no point to copying the array values if we immediately overwrite them with false:

for (var i = 0; i < flags.length; i++) {
  for (var j = 0; j < flags[i].length; j++) {
    flags[i][j] = false;
  }
}

We can delete that double loop if we put false values into the flag array while we're making it:

var flags = array.map(function (subarray) {
  return subarray.map(function () {
    return false;
  });
});

Question 2

I get flagsArray[(i + 1)] is undefined error while executing traverseDown(). This looks like trying to read an index beyond flagsArray. But if I check for flagsArray[i + 1][j] === false && i < flagsArray.length in a while loop, shouldn't the loop just stop once it tries to read beyond the array?

No, JavaScript does nothing to prevent out-of-bounds array access. What's happening in the line

while (flagsArray[i + 1][j] === false && i < flagsArray.length) {

is that flagsArray[i + 1] evaluates to undefined because i + 1 is beyond the last element of the array. Then you try to look up [j], and the program crashes because undefined has no properties.

You don't even get around to evaluating i < flagsArray.length. Besides, that test wouldn't prevent an invalid index because if i is the index of the last element, flagsArray[i + 1] is out of bounds.

General observations

This test has two problems:

while (flagsArray[i][j + 1] === false && j < flagsArray[i].length) {

First, you're neglecting to check the array index before accessing the array. Second, you're not testing the right value. You should test j + 1 before accessing flagsArray[i][j + 1]:

while (j + 1 < flagsArray[i].length && flagsArray[i][j + 1] === false) {

There are similar problems with the three other tests.

As an alternative to writing four functions, I recommend that you write the traversal logic once and make it depend on an orientation variable that has a value from 0 through 3. The only thing that differs with the direction of movement is the amount by which you increment the grid indices. You can look up these incrementation values in a pair of arrays with orientation as the array index.

The incrementation arrays look like this:

var dr = [ -1, 0, 1, 0 ],  // North, east, south, west.
    dc = [ 0, 1, 0, -1 ];

Given a grid position r, c, you can calculate the next position like this:

var R = r + dr[orientation],
    C = c + dc[orientation];

The following snippet demonstrates this approach.

function print(line) {
  document.getElementById('message').innerHTML += line + '<br><br>';
}

var snail = function(array) {
  var result = [];

  var flags = array.map(function (subarray) {
    return subarray.map(function () {
      return false;
    });
  });
  print(JSON.stringify(array));

  var numRows = flags.length,
      numCols = flags[0].length,
      numElements = numRows * numCols,
      dr = [ -1, 0, 1, 0 ],  // North, east, south, west.
      dc = [ 0, 1, 0, -1 ],
      r = 0,
      c = 0,
      orientation = 1;       // Start heading east.

  var count = 0;

  while (result.length < numElements) {
    result.push(array[r][c]);
    flags[r][c] = true;
    var R = r + dr[orientation],  // Calculate the next grid position.
        C = c + dc[orientation];
    if (R >= 0 && R < numRows && C >= 0 && C < numCols && !flags[R][C]) {
      r = R;                      // If the position is valid, go ahead.
      c = C;
    } else {
      orientation = (orientation + 1) % 4;
      r = r + dr[orientation];    // Otherwise, turn clockwise and recalculate.
      c = c + dc[orientation];
    }
  }

  return result;
}

window.onload = function () {
  print(snail([ [1, 2, 3],
                [8, 9, 4],
                [7, 6, 5] ]));
};
body {
  font-family: sans-serif;
}
<div id="message"></div>

Upvotes: 5

Related Questions