Informal Tags: nested 2D arrays, Array.from, Arrays,
Jaseem Abid generously agreed to give me another mock interview today because he has a behavioral tomorrow and his words “I can’t really prepare for that at this point because my answers will be built out of my , and the challenge was to design minesweeper!
I would not have passed the criteria for a real interview here - it turns out my ability to manipulate 2D arrays with Typescript is somewhat clunky and unpracticed . However, I do want to give myself props for this gem:
let ranTile = Math.floor(Math.random() * (height * width))
let tileWidth = ranTile % height
let tileHeight = Math.floor(ranTile / height)
return [tileWidth, tileHeight]This is something I learned while creating a game that allowed me to translate a line of height * width elements into a width and height values.
// HW / prep
// think of questions
// refresh my own spiel
// The challenge
// N-part question
// placeMines
// where is this going to go?
// Probably playing the game to be honest
// Doesn't have to really
function generateRandomTile(height: number, width: number){
let ranTile = Math.floor(Math.random() * (height * width))
let tileWidth = ranTile % height
let tileHeight = Math.floor(ranTile / height)
return [tileWidth, tileHeight]
}
// start: 11:30am
function placeMines(height: number, width: number, count: number){
const board: number[][] = []
// create a bunch of rows
for (let row = 0; row < height; row++){
const row: number[] = []
board.push(row)
// create a bunch of columns per row
for (let col = 0; col < width; col++){
row.push(0)
}
}
const randomTiles: number[][] = []
for (let c = 0; c < count; c++){
// is this range completely right?
// Inefficient - stop at count
// repeating tiles
let ranTile = generateRandomTile(height, width)
while (randomTiles.includes(ranTile)){
ranTile = generateRandomTile(height, width)
}
randomTiles.push(ranTile)
let [tileWidth, tileHeight]= ranTile
console.log(count)
board[tileWidth][tileHeight] = 1
}
return board
// return count of mines randomly, across a board
// 10 x 10 board, place 15 of them
}
const tester = (expectedMines: number, board: number[][]) => {
let minesFound = 0
for (let row of board){
for (let col of row){
if (col === 1){
minesFound++
}
}
}
console.log(expectedMines)
return expectedMines === minesFound
}
// placeMines(10, 10, 2)
//11:48
console.log(tester(2, placeMines(10, 10, 2)))
// Fix- 11:58 for the clashing repeat random tiles
// end timestamp: 12:07
// does JS have a tuple?
// My job is convincing the recruitor possibly not solving problemThis works, and the testing works, which is all good, but there are some problems to address.
Problem 1
Creating a board with two nested loops is a lot of typing and code complexity that could certainly be compressed into a single line. This is sort of a trick, but it’s a very useful trick.
for (let row = 0; row < height; row++){
const row: number[] = []
board.push(row)
for (let col = 0; col < width; col++){
row.push(0)
}
}
That’s 8 lines - it’s a big chunk. There are a few ways to do this.
Using Array.from
const grid = Array.from({ length: height }, () => Array(width).fill(0));
Array.from() takes two arguments. The first is an options object, which we are using to specify that the length of the array array should be equal to the variable height.
The second argument is a function, which specifies how to fill the array. In this case, we are using the Array(n) constructor with the .fill method to fill in the values of the rows.
Array.from is certainly kind of funky. It turns out there are a few other ways to use it. We can, for example, pass another array into Array.from. The second argument will always be a map function that is applied to every element in the array.
That map function can have up to two arguments: value and index. So if we wanted, we could create an array that was filled with its own indexes.
So what’s up with {length: height}?
It turns out I lied. There is no special options object expected by Array.from. Array.from will simply take any array-like object, like Map or Set (who gets to say those are array-like? I mean I guess MDN does but I’m not sure what this criteria is) that, in MDN’s words, has a length property.
So that’s what we’re doing - passing in an object with a length property. That’s enough for Array.from to create an Array for us.
My question is, why do this when we can instead use Array(numberOfItems)?
Well, it turns out that simply using Array(n) alone creates an array that is completely empty in such a way that running .map on it will actually skip each element, since each element is empty.
Not event undefined apparently, but truly empty:
This can be pretty easily fixed though - the spread operator apparently converts empty array slots into undefined ones, which can be mapped over. 
So these two lines are roughly equivalent:
Spread Array Constructor
const grid = [...Array(n)].map(e=>e)
Array.from Approach
const grid = Array.from({length: n}, e=>e)`
The only difference I am really able to find is performance. Because the spread operator involves going back over an array a second time, the first approach is technically slower.
I ran this benchmark
function usingArrayFrom(n: number) {
return Array.from({length: n}, (_, i) => i);
}
function usingSpreadAndMap(n: number) {
return [...Array(n)].map((_, i) => i);
}
// Benchmark
const n = 1000000;
let froms = 0
let spreads = 0
let loops = 1000
for (let i = 0; i < loops; i++){
let now = Date.now()
usingArrayFrom(n);
froms+=Date.now()-now
let now2 = Date.now()
usingSpreadAndMap(n);
spreads+=Date.now()-now2
}
console.log("Array.from", froms/loops)
console.log("Array.spead", spreads/loops)
---Results for 1000 loops--- Array.from = 1.997 ms/average Array.spead = 7.767 ms/average Ratio: From is 3.8x faster
When I swapped their order, this result was actually even a bit more dramatic Array.from1 =1.57 Array.spread7 = 7.79 Ratio: From is 6.2x faster
In summary, the Array.from({}, ()=>_) method is faster enough to use instead of spread. I sort of like the way spread looks - fewer parenthesis. You can probably use either. We’re comparing between 1 and 8 milliseconds to create an array with 1000 items in it.
What I found was that 2.5 - 3.8 times faster
Here’s a different method using the spread operator and Array.map together, which is pretty cool.
So I’d say that settles it. Objectively the best way to create a grid of height h by width w is:
const grid = Array.from({length: h}, () => Array(width).fill(0))
I suppose if you want to do it in the most performant way, .from is still more performant. It’s a little more than double the performance of the Array(n).fill(0) approach. Unfortunately. Once again, I feel like it’s syntactically not as nice. But benchmarks don’t lie:
function from(n: number) {
return Array(n).fill(0)
}
function fill(n: number) {
Array.from({length: n}, ()=>0)
}
// Benchmark
const n = 1000000;
let froms = 0
let fills = 0
let loops = 1000
for (let i = 0; i < loops; i++){
let now2 = Date.now()
fill(n);
fills+=Date.now()-now2
let now = Date.now()
from(n);
froms+=Date.now()-now
}
console.log("From", froms/loops)
console.log("Fills", fills/loops)Creating an array with a million 0’s for each of them one thousand times averages out to fill: 1.5ms from: .6ms
Wow! That’s so fast from! So I revise my conclusion. The fastest, one-line way I can find to create a 2D array is:
const grid = Array.from({length: h}, () => Array.from({length: w}, ()=>h))
Oh my god. I’m so sorry. I’m just writing this as I go, but the plot thickens. In isolation, the verdict is super clear, right? .from is much faster than the ...Array().fill() technique.
But when used together…
const grid = Array.from({length: h}, () => Array.from({length: w}, ()=>0))
// Average of 2.1ms*
const grid = [...Array(h)].map(e=>Array(w).fill(0))
//Average of 0.9ms*
// *where h and w are both 1000 over 1000 loops
So I guess we’ll never know. Do what you want, nothing makes sense. I say this tongue in cheek - modern Javascript parsers have all sorts of crazy optimizations, so the expectation that the results here would be deterministic and consistent across scales is unrealistic.
I wish I had a solid breakdown though, just to get to the bottom of this. I ran some benchmarks Claude created and came up with this:
Array.from({length: h}, () => [...Array(w)].map(() => 0));
// From -> spread -> map
// 75ms
Array.from({length: h}, () => Array.from({length: w}, () => 0));
// from -> from
// 41ms
[...Array(h)].map(() => Array(w).fill(0));
// spread -> map -> fill
//13ms
Array.from({length: h}, () => Array(w).fill(0));
// from -> fill
//11msThese are with 100x100 grids and 1000 iterations.
I’m not totally sure what’s going on here. But I do sort of feel like I got my wish - I really like the spread -> map -> fill for a combination of having the shortest and simplest syntax, matched with nearly the top performance. So that’s what I’m going to add to my toolkit.
**
Back to minesweeper
Did this OOP implementation and got stuck adding the bombs:
type Point = "BOMB" | number
class MineSweeper {
height: number
width: number
count: number
totalPoints: number
board: Point[][]
constructor(height: number, width: number, count: number){
this.height = height
this.width = width
this.count = count
this.totalPoints = this.height * this.width
this.board = this.createBoard(this.height, this.width)
}
createBoard(h: number, w: number): Point[][] {
return [...Array(h)].map(() => Array(w).fill(0))
}
findRandomPoint(): [number, number, number]{
let randomTile = Math.floor(Math.random() * this.totalPoints)
let ranWidth = randomTile % this.height
let ranHeight = Math.floor(randomTile / this.width)
return [randomTile, ranWidth, ranHeight]
}
setBoard(){
let uniquePoints = new Set()
console.log(uniquePoints.size)
while (uniquePoints.size <= this.totalPoints){
let [point, w, h] = this.findRandomPoint()
if (uniquePoints.has(point)) continue
uniquePoints.add(point)
this.board[w][h] = 'BOMB'
}
}
}
let ms = new MineSweeper(10, 10, 2)
ms.setBoard()
console.log(ms.board)It’s way to verbose. 43 lines. I’m going to try again.
type Point = "BOMB" | "_" | number
function mineSweeper(h: number, w: number, count: number): Point[][]{
let board = [...Array(h)].map(() => Array(w).fill('_'))
let uniquePoints = new Set()
while (uniquePoints.size < count){
let ranPoint = Math.floor(Math.random()*h*w)
if (uniquePoints.has(ranPoint)) continue
uniquePoints.add(ranPoint)
const ranHeight = ranPoint % h
const ranWidth = Math.floor(ranPoint / w)
board[ranHeight][ranWidth] = 'BOMB'
}
return board
}
console.log(mineSweeper(10, 10, 3))Wow that is way better. 18 lines. That took me about 5 minutes this time around.
[...Array(h)].map(()=>Array(w).fill('_'))Okay this time I got it in 3:11s:
type Point = "BOMB" | "_" | number
function generateBoard(h: number, w: number): Point[][] {
return [...Array(h)].map(()=>Array(w).fill("_"))
}
function mineSweeper(h: number, w: number, count: number): Point[][]{
let board = generateBoard(h, w)
let uniquePoints: Set<number> = new Set()
while (uniquePoints.size < count){
let ranPoint = Math.floor(Math.random() * h * w)
if (uniquePoints.has(ranPoint)) continue
let ranHeight = ranPoint % h
let ranWidth = Math.floor(ranPoint / w)
uniquePoints.add(ranPoint)
board[ranHeight][ranWidth] = "BOMB"
}
return board
}
console.log(mineSweeper(10, 10, 6))I think that extracting the board generation into it’s own function is actually very unnecessary, and wastes a lot of time.
It could be done later.