## 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, [2], [3, [4]]];
flat(arr)
// [1, 2, 3, [4]]
flat(arr, 1)
// [1, 2, 3, [4]]
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, [2], [3, [4]]]  => []
``````

Meets 1, not array, just collect it

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

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

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

next is 2, so collect it

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

Following above steps, we can get

``````[3, [4]] => [1,2]
[[4]] => [1,2,3]
[4] => [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], [[2], 1], [[3, [4]], 1]] => []
``````

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

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

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

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

next is 2 with depth 0, collect it

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

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

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

collect 3

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

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

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

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.