Skip to content

Representing 2D array as 1D array

Posted on:January 6, 2022 at 04:06 AM

Arrays

Arrays are one of the most common data structures used by software developers. They are very versatile and easy to use. You can create an array in JavaScript using the following syntax

const myArray = []; // the most common way
//or
const myArray = new Array(length); // uses constructor to create array of size length

Some programming languages provide a way to create multi-dimensional arrays, unfortunately, JavaScript does not provide multi-dimensional arrays natively but we can simulate it

const twoDimensionalArray = new Array(5); // 5 is number of rows;
  for (let i = 0; i < twoDimensionalArray.length; i++) {
    twoDimensionalArray[i] = new Array(3); // 3 is number of columns
  }

We can re-write it more concisely using the following snippet:

Array.from(Array(5), () => new Array(3))

N-Dimensional Arrays

We can also create n-dimensional arrays through the following code snippet courtesy stackoverflow

function createArray(length) {
  var arr = new Array(length || 0), i = length;

    if (arguments.length > 1) {
        var args = Array.prototype.slice.call(arguments, 1);
        while(i--) arr[length-1 - i] = createArray.apply(this, args);
    }

    return arr;

}

createArray(); // [] or new Array()
createArray(2); // new Array(2)
createArray(3, 2); // [new Array(2),
// new Array(2),
// new Array(2)]

Mapping 2D array as one 1D array

Let’s suppose we have the following 2D array

const grid = [
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 60],
];

To access elements inside it we can use the indices so for example grid[1][2] means to go to the second row and fetch the third element which is sixteen.

Now consider that the same array is flattened into a single-dimensional array. Still, we want to access the element using the 2D dimensional indices so how can we map the grid[1][2] into a single-dimensional array?

const grid = [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60];
grid[1][2] // this won't work

We can use a simple formula for this:

grid[indexOfX + ArrayWidth + IndexY] // ArrayWidth is number of columns

indexOfX and indexOfY corresponds to the indices of the 2D array and ArrayWidth corresponds to the number of columns in the array.

So using the above formula we can access the elements using following index:

grid[1*4+2] // returns 16

Similarly to convert 1D array indices into 2D array we need to reverse the above steps i.e

x = i % ArrayWidth; // % is the "modulo operator", the remainder of i / width;
y = i / ArrayWidth; // where "/" is an integer division

See following for details