BFE coding challenge #3 implement Array.prototype.flat()
Tags: javascript, challenge
Published: 2020-08-28 04:39:26

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


This article is about the coding problem [BFE.dev#3. implement Array.prototype.flat()](https://bigfrontend.dev/problem/implement-Array-prototype.flat)

## Goal

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

```js
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.

```js
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.

```js
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.

```js
function flat(arr, depth = 1) {
  const result = []
  const stack = [...arr.map(item => ([item, depth]))]
  
  while (stack.length > 0) {
    const [head, depth] = stack.shift()
    if (Array.isArray(head) && depth > 0) {
      stack.unshift(...head.map(item => ([item, depth - 1])))
    } else {
      result.push(head)
    }
  }
  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.

```js
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!

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/18n3usjq0zimzuaejea5.gif)


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

See you next time.