extract 2D array from another 2D array represented as a 1D array

Question

So if I have a 2D array such as

const array = [
 [1, 2, 3, 4, 5],
 [9, 8, 7, 6, 5],
 [1, 8, 3, 6, 5],
 [9, 8, 7, 6, 5],
 [1, 8, 3, 6, 5],
 [1, 2, 3, 4, 5]
 ];

which could for the point of the question be any size, square or not square.

and I want to extract 3x3 arrays out of it, for instance at 1,1 that would be const sub = [[8, 7, 6], [8, 3, 6], [8, 7, 6]]. So far so good - I can do this. However I am flattening the 2D array so that its represented as a 1D array (long story as to why), i.e

const array = [1, 2, 3, 4, 5, 9, 8, 7, 6, 5, 1, 8, 3, 6, 5, 9, 8, 7, 6, 5, 1, 8, 3, 6, 5, 1, 2, 3, 4, 5];

What I'm trying to do is extract the same (or any) 3x3 array out of this but while its represented as a 1D array, so I would then get back [8, 7, 6, 8, 3, 6, 8, 7, 6].

I almost got there, however I made an error of only working with arrays that were 9x9 and always extracting 3x3 subsets which mean that my solution only works for that specific case, and the more I stare at my solution, the more I cannot work out what the generic solution would look like.

My solution:

const extractSubsetFrom1D = (array, subHeight, subWidth, startRow, startCol) => {
 const kWH = subWidth * subHeight
 const subset = array.slice(((((kWH - 2) * startRow) + startCol) * kWH), ((((kWH - 2) * startRow) + startCol) * kWH) + kWH)
 return subset
}

In my case subHeight and subWidth were always equalling 3 respectively, and as the array itself was always 9x9 I believe I accidentally stumbled on a solution for that specific case as they divide nicely into each other.

To be clear my solution will fail for the startRow = 1 startCol = 0 for the provided array (it works for the startRow = 0 scenario

• Barry Carter: developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/… (Array.flat) may or may not be helpful. It can flatten arrays up to a certain point and then stop, but that might not be what you need.
• Thomas: as an idea: extractSubset = (arr, { top, left, bottom, right }) => arr.slice(top, bottom).map(row => row.slice(left, right)) and then something like extractSubset(array, {top: -3, right: 3}) every one of the 4 boundaries is optional

Answer 1

It's not entirely clear to me how you came to your current implementation, but I can at least tell:

• ✅ You correctly determined the size of the sub grid array to return (kWH)
• ❌ You incorrectly assume you can slice out a sub grid as one continuous part of the original 1d array
• 🟠 The calculation of the first element seems kind-of-right but is actually wrong (probably because of the previous mistake)

From (y,x) to i

Let's start from scratch and work our way up to a nice one liner.

In a 2d-array, you can get a cell's value by doing:

cellValue = grid2d[y][x]

Once you flatten it, you'll need to do:

cellValue = grid1d[y * GRID_WIDTH + x]

y * GRID_WIDTH takes you to the start of the right row, and + x gets you to the right column.

As you can see, you need to know the original grid's size before you can even query a specific cell. That means your extract function would need an argument to pass the original width (or, if the grids are guaranteed to be square, you can do Math.sqrt(array.length).

A slice per row

Let's use this math to find the indices of a 2x2 sub grid at (1,1) extracted from a 3x3 source grid:

0 1 2
3 [4][5]
6 [7][8]

As you can see, the resulting indices are [4,5,7,8]. There is no way to slice these indices out of the source array directly because we don't want to include the 6.

Instead, we can use a nested loop to skip the gaps between our rows:

const to1d = (x, y, w) => y * w + x;
const extractSubGrid1D = (grid, gridWidth, x, y, w, h) => {
 const yTop = y;
 const yBottom = y + h
 const xLeft = x;
 const xRight = x + w;
 
 const subgrid = [];
 
 for (let y = yTop; y < yBottom; y += 1) {
 for (let x = xLeft; x < xRight; x += 1) {
 const index = to1d(x, y, gridWidth);
 subgrid.push(grid[index]);
 }
 }
 return subgrid;
}
const originalGrid = [
 0, 1, 2,
 3, 4, 5,
 6, 7, 8
];
console.log(
 extractSubGrid1D(originalGrid, 3, 1, 1, 2, 2)
)

Once you get a feel for the logic, feel free to refactor.

The other way around

To go from a 1d-index to a 2d coordinate, you can do:

x = i % w
y = Math.floor(i / w)

Applying this logic, you can also fill your sub grid like so:

• Create a new array of the right size
• For each of its indices, determine the original grid's (x, y) coordinate
• Transform that coordinate back to an index to query the original grid with

const to1d = (x, y, w) => y * w + x;
const extractSubGrid1D = (grid, gridWidth, x, y, w, h) => Array.from(
 { length: w * h },
 (_, i) => grid[to1d(x + i % w, y + Math.floor(i / w), gridWidth)]
)
const originalGrid = [
 0, 1, 2,
 3, 4, 5,
 6, 7, 8
];
console.log(
 extractSubGrid1D(originalGrid, 3, 1, 1, 2, 2)
)

• amlwwalker: Hi thanks for this detailed answer. I think as you wondered in the opening of your response, I expected it to be easier than it was and built on error after error.... Just one question - the two snippets you provide seem to take the same inputs - and therefore are one and the same right? The second is just a very 'tight' version of the first? I.e they both do the same thing from the perspective of the caller of extractSubGrid1D?
• user3297291: Yes, they’re just two different ways of writing the exact same thing. So it’s up to personal preferences which of the two you prefer