# Implementation of array flattening

2021-08-27 03:18:33 Yangyan

# Flattening of arrays

## 1. What is array flattening

The so-called flattening of arrays , It refers to converting an array with multiple nested layers into an array without nesting . for example : take `[1, [2, 3], [4, [5, [6]]]]` Convert into `[1, 2, 3, 4, 5, 6]`

``````const arr = [1, [2, 3], [4, [5, [6]]]]
arr.flat(3) //=> [1, 2, 3, 4, 5, 6]
Copy code ``````

## 2. Implementation of array flattening

### 1. Initially realized

Flatten the passed in array and return

``````(function() {
function flatten(res = []) {
const array = this

for (let i = 0, len = array.length; i < len; i ++) {
const val = array[i]

if (Array.isArray(val)) { //  If it's an array ,  Flatten it
val.flatten(res)
} else { //  If it's not an array ,  Then put the element directly into  res  that will do
res.push(val)
}
}

return res
}

Array.prototype.flatten = flatten
})()

const array = [1, 2, [3, [4, [5, 6, [7, 8]]]]]
array.flatten() //=> [1, 2, 3, 4, 5, 6, 7, 8]
Copy code ``````

### 2. Further realization

It's easy to see , and `JS` Medium `flat` comparison , The initial implementation was less `depth` Parameters ( Anti nesting depth ), Add here

``````(function() {
function flatten(depth = 1, res = []) {
const array = this

for (let i = 0, len = array.length; i < len; i ++) {
const val = array[i]

if (Array.isArray(val) && depth > 0) {
//  If  val  It's an array ,  And it needs to be flattened
val.flatten(depth - 1, res)
} else {
res.push(val)
}
}

return res
}

Array.prototype.flatten = flatten
})()

const array = [1, 2, [3, [4, [5, 6, [7, 8]]]]]
array.flatten(3) //=> [1, 2, 3, 4, 5, 6, [7, 8]]
Copy code ``````

Although remove `res` The parameter is closer to `flat` function , But to prevent every execution `flatten` Functions need to create a `res` Array , Each time you accept a recursive return value, you also need to expand it , It's a waste of time , It's a waste of space , So... Is not removed `res` Parameters . As shown below :

``````(function() {
function flatten(depth = 1) {
const array = this
const res = []

for (let i = 0, len = array.length; i < len; i ++) {
const val = array[i]

if (Array.isArray(val) && depth > 0) {
res.push(...val.flatten(depth - 1))
} else {
res.push(val)
}
}

return res
}

Array.prototype.flatten = flatten
})()
Copy code ``````

### 3. Final realization

When `flatten` Call to `depth === 1` when , Directly use the extension operator to add to `res` The array can be , Improve program efficiency

otherwise , You don't just need another layer of recursion , And every time you traverse an element, you have to go through multiple judgments

``````(function() {
function flatten(depth = 1, res = []) {
const array = this

for (let i = 0, len = array.length; i < len; i ++) {
const val = array[i]

if (Array.isArray(val) && depth > 0) {
if (depth === 1) {
res.push(...val)
} else {
val.flatten(depth - 1, res)
}
} else {
res.push(val)
}
}

return res
}

Array.prototype.flatten = flatten
})()

const array = [1, 2, [3, [4, [5, 6, [7, 8]]]]]
array.flatten(3) //=> [1, 2, 3, 4, 5, 6, [7, 8]]
Copy code ``````

## 3. Other implementation directions of array flattening

### 1. utilize `Array.prototype.reduce` Realization

``````(function() {
function flatten() {
const array = this
const res = array.reduce((prevVal, curVal) => {
return prevVal.concat(Array.isArray(curVal) ? curVal.flatten() : curVal)
}, [])
return res
}

Array.prototype.flatten = flatten
})()
Copy code ``````

### 2. utilize `Array.prototype.some` Realization

``````(function() {
function flatten() {
const array = this
const res = [...array]
while (res.some(item => Array.isArray(item))) {
res = [].concat(...res)
}
return res
}

Array.prototype.flatten = flatten
})()
Copy code ``````

### 3. utilize `Array.prototype.splice` Realization

``````(function() {
function flatten() {
const array = this
const res = [...array]

for (let i = 0; i < res.length; i ++) {
if (Array.isArray(res[i])) {
res.splice(i, 1, ...res[i])
i --
}
}

return res
}
Array.prototype.flatten = flatten
})()
Copy code ``````

### 4. utilize `stack` Realization

``````(function() {
function flatten() {
const array = this
const stk = [...array]
const res = []

while (stk.length) {
let topVal = stk.pop()
if (Array.isArray(topVal)) {
stk.push(...topVal)
} else {
res.push(topVal)
}
}

return res.reverse()
}
Array.prototype.flatten = flatten
})()
Copy code ``````