Why there is difference between [] and new Array

Question

I was having a look at the popular NQueen problem. The below code simply returns the number of possible ways. It gives different outputs depending upon the way in which the board matrix is passed.

// just a helper function
const isSafe = (board, row, col) => {
  for (let i = row; i >= 0; i--) {
    if (board[i][col]) return false;
  }
  for (let i = row, j = col; i >= 0 && j >= 0; i--, j--) {
    if (board[i][j]) return false;
  }
  for (let i = row, j = col; i >= 0 && j < board.length; i--, j++) {
    if (board[i][j]) return false;
  }
  for (let i = row; i >= 0; i--) {
    if (board[i][col]) return false;
  }
  return true;
};

const getWays = (board, row) => {
  if (row == board.length) {
    return 1;
  }

  let count = 0;
  for (let col = 0; col < board.length; col++) {
    if (isSafe(board, row, col)) {
      board[row][col] = true;
      count += getWays(board, row + 1);
      board[row][col] = false;
    }
  }
  return count;
};

If i call getWays like below the output is 2 which is correct

const n = 4;
let board = new Array(n).fill(new Array(n).fill(false));
for (let i = 0; i < n; i++) {
  board[i] = new Array(n).fill(false);
}
console.log(getWays(board, 0));

But if i call getWays like below the answer is 0 which is incorrect

const n = 4;
let board = new Array(n).fill(new Array(n).fill(false));
console.log(getWays(board, 0));

I don't understand how these 2 ways of creating the matrix are causing different outputs even though they generate same matrix. Can someone point out what am I missing with a little explaination and link to any documentation(if applicable/possible)

If you fill your array with N copies of exactly the same array object, you will have problems. — tadman
– tadman, Commented Mar 10, 2021 at 19:13
In other words, the first snippet contains N different arrays within board, in the second snippet board contains the same array 10 times and if you change that array in one row all other rows change as well. And the same is true in java btw. — luk2302
– luk2302, Commented Mar 10, 2021 at 19:14
totally missed that thing. Thanks @luk2302. Could you please add it as answer so that I can mark it — Rishabh Singh
– Rishabh Singh, Commented Mar 10, 2021 at 19:19

Stephen P · Accepted Answer · 2021-03-11 01:09:10Z

Let's deconstruct this statement:
let board = new Array(n).fill(new Array(n).fill(false));

You're creating a new variable named board and assigning something to it.

What are you assigning to it?
A new Array(4) which you also initially fill with "something".

What is that "something"?
It is a reference to a new Array(4) which you fill with false
→ it is One new array filled with false

So board is an array with four references to the same Array.
If you change that array in one row all other rows change as well. You can see this with a small test program.

const n = 4;
let board = new Array(n).fill(new Array(n).fill(false));
console.log(board);

board[0][2] = 'Q';
console.log(board[2][2]);

Running this snippet in Stackoverflow produces the output:

[
  [
    /**id:2**/
    false,
    false,
    false,
    false
  ],
  /**ref:2**/,
  /**ref:2**/,
  /**ref:2**/
]

The first element of the board Array is given an id of 2 and the other three elements of board have a reference to 2, telling you they are the same Array so changing one changes all rows — say board[0][2]="Q" also makes console.log(board[2][2]) come out as "Q"

This looks different in a browser console, which is likely to display that first console.log(board) as this:

console.log(board)
(4) [Array(4), Array(4), Array(4), Array(4)]
  0: (4) [false, false, false, false]
  1: (4) [false, false, false, false]
  2: (4) [false, false, false, false]
  3: (4) [false, false, false, false]
  length: 4

Then you'll see the effect if you write board to the console output again after assigning to a cell:

board[0][2]='Q';
console.log(board)
(4) [Array(4), Array(4), Array(4), Array(4)]
  0: (4) [false, false, "Q", false]
  1: (4) [false, false, "Q", false]
  2: (4) [false, false, "Q", false]
  3: (4) [false, false, "Q", false]
  length: 4

Now, in your first case which works, you follow that initial statement with a loop

for (let i = 0; i < n; i++) {
  board[i] = new Array(n).fill(false);
}

What this does is throw away the original contents of board[0] through board[3], throw away the four references to the one Array, and instead assign four newly created Arrays. It is equivalent to this series, without using a loop:

const n = 4;
let board = new Array(n);
let r = new Array(n).fill(false);
board[0] = r;
board[1] = r;
board[2] = r;
board[3] = r;
// A little clearer here that board[0] through board[3] all contain references to 'r'
console.log(board);

// Now replace those references to 'r' with new Arrays...
board[0] = new Array(n).fill(false);
board[1] = new Array(n).fill(false);
board[2] = new Array(n).fill(false);
board[3] = new Array(n).fill(false);
console.log(board);

@luk2302 that out. This is more explaination than anyone could ever ask for. I just missed the fact that fill being passed a refrence. I had a little bit of hard time because the console.log prints same board in each case. Any way to print it in console like the way Stackoverflow produces output?
@RishabhSingh There is no way I know to convince the various browser consoles to change their output format. Personally I would appreciate a toggle so I could switch between those two representations.

Collectives™ on Stack Overflow

Why there is difference between [] and new Array

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related