DEV Community

loading...
Cover image for BFE coding challenge #3 implement Array.prototype.flat()

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

jser_zanp profile image jser ・3 min read

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]
Enter fullscreen mode Exit fullscreen mode

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
}
Enter fullscreen mode Exit fullscreen mode

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
  }, [])
}

Enter fullscreen mode Exit fullscreen mode

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]]]  => []
Enter fullscreen mode Exit fullscreen mode

Meets 1, not array, just collect it

[[2], [3, [4]]] => [1]
Enter fullscreen mode Exit fullscreen mode

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

[2, [3, [4]]] => [1]
Enter fullscreen mode Exit fullscreen mode

next is 2, so collect it

[[3, [4]]] => [1,2]
Enter fullscreen mode Exit fullscreen mode

Following above steps, we can get

[3, [4]] => [1,2]
[[4]] => [1,2,3]
[4] => [1,2,3]
[] => [1,2,3,4]
Enter fullscreen mode Exit fullscreen mode

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]] => []
Enter fullscreen mode Exit fullscreen mode

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

[[[2], 1], [[3, [4]], 1]] => [1]
Enter fullscreen mode Exit fullscreen mode

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

[[2, 0], [[3, [4]], 1]] => [1]
Enter fullscreen mode Exit fullscreen mode

next is 2 with depth 0, collect it

[[[3, [4]], 1]] => [1, 2]
Enter fullscreen mode Exit fullscreen mode

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

[[3,0],[[4],0]] => [1, 2]
Enter fullscreen mode Exit fullscreen mode

collect 3

[[[4],0]] => [1, 2, 3]
Enter fullscreen mode Exit fullscreen mode

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

[] => [1,2,3,[4]]
Enter fullscreen mode Exit fullscreen mode

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
}
Enter fullscreen mode Exit fullscreen mode

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()
}
Enter fullscreen mode Exit fullscreen mode

Ok, passed!

Alt Text

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

See you next time.

Discussion (0)

pic
Editor guide