## DEV Community is a community of 615,790 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. # BFE coding challenge #3 implement Array.prototype.flat()

https://bfe.dev is like a LeetCode for FrontEnd developers. I’m using it to practice my skills.

## Goal

We are asked to implement `flat()` to remove the nested square brackets.

``````const arr = [1, , [3, ]];
flat(arr)
// [1, 2, 3, ]
flat(arr, 1)
// [1, 2, 3, ]
flat(arr, 2)
// [1, 2, 3, 4]
``````

## Recursion

The recursion approach is easy, collect result while iterating through the array.

1. if meets another array, `flat()` it first, and then collect the results
2. if meets non-array element, just collect it in order.

With this in mind, following recursion approach becomes natural.

``````function flat(arr, depth = 1) {
const result = []
for (let item of arr) {
if (Array.isArray(item) && depth > 0) {
result.push(...flat(item, depth - 1))
} else {
result.push(item)
}
}
return result
}
``````

## Rewrite with reduce

Seems like a good chance to use reduce. Let's modify a little.

``````function flat(arr, depth = 1) {
return arr.reduce((result, item) => {
if (Array.isArray(item) && depth > 0) {
result.push(...flat(item, depth - 1))
} else {
result.push(item)
}
return result
}, [])
}

``````

## Iterative Approach

When preparing for an tech interview, rewriting recursion with iteration is a must-to-know.

Let's first write down how would we remove the brackets manually. Left is the target array, right is the result array.

``````[1, , [3, ]]  => []
``````

Meets 1, not array, just collect it

``````[, [3, ]] => 
``````

next is `` this is array, so remove the brackets, and put it back.

``````[2, [3, ]] => 
``````

next is 2, so collect it

``````[[3, ]] => [1,2]
``````

Following above steps, we can get

``````[3, ] => [1,2]
[] => [1,2,3]
 => [1,2,3]
[] => [1,2,3,4]
``````

One problem is the `depth`, we cannot just remove all the brackets, so all the element should track its own depth.
let's redo above process with `depth` this time.

Suppose depth is 1:

``````[[1, 1], [, 1], [[3, ], 1]] => []
``````

next element is 1 with depth 1, so collect it.

``````[[, 1], [[3, ], 1]] => 
``````

next element is `` with depth1, so remove the brackets and push back 2 with depth 0

``````[[2, 0], [[3, ], 1]] => 
``````

next is 2 with depth 0, collect it

``````[[[3, ], 1]] => [1, 2]
``````

next is `[3,]` with depth 1, push them back with depth 0

``````[[3,0],[,0]] => [1, 2]
``````

collect 3

``````[[,0]] => [1, 2, 3]
``````

now we get `` with depth 0, since 0 we cannot remove the brackets any more, just collect ``

``````[] => [1,2,3,]
``````

With above process in mind, an iterative approach is easy to come up with.

``````function flat(arr, depth = 1) {
const result = []
const stack = [...arr.map(item => ([item, depth]))]

while (stack.length > 0) {
if (Array.isArray(head) && depth > 0) {
stack.unshift(...head.map(item => ([item, depth - 1])))
} else {
}
}
return result
}
``````

There is performance concern in above approach - `shift/unshift` should be avoided, because every `shift/unshift` actually changes all rest element's indices.

To improve this, we could solve it from right to left, meaning using `pop/push`, and we only need to reverse it for once.

``````function flat(arr, depth = 1) {
const result = []
const stack = [...arr.map(item => ([item, depth]))]

while (stack.length > 0) {
const [top, depth] = stack.pop()
if (Array.isArray(top) && depth > 0) {
stack.push(...top.map(item => ([item, depth - 1])))
} else {
result.push(top)
}
}

return result.reverse()
}
``````

Ok, passed! Hope it helps. If you are interested, give it a try on https://BFE.dev

See you next time.

## Discussion (0) 