BFE coding challenge #3 implement Array.prototype.flat()

#challenge #javascript

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()

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.

if meets another array, flat() it first, and then collect the results
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) {
    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.

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()
}