JavaScript Interview: How to implement array flattening method

1 What is array flattening?

The concept is simple, it means reducing the dimensionality of a "multidimensional" array, for example:

// The original array is a "three-dimensional" array const array = [1, 2, [3, 4, [5, 6], 7], 8, 9]
 
// can be reduced to two-dimensional newArray1 = [1, 2, 3, 4, [5, 6], 7, 8, 9]
 
// It can also be reduced to one dimension newArray2 = [1, 2, 3, 4, 5, 6, 7, 8, 9]

Array flattening is also called array flattening and array dimensionality reduction.

2 Array flattening method in JS standard library

The JavaScript standard library has implemented the array flattening method Array.prototype.flat()

The flat() method recursively traverses an array to a specified depth and merges all elements with the elements in the traversed subarray into a new array and returns it.

Syntax: var newArray = arr.flat([depth])

Parameter: depth is an optional value, indicating the depth of the multidimensional array to be traversed. The default value is 1. It can be understood as the number of layers you want to expand (or reduce dimension).

Return value: a new array composed of the traversed elements and the elements of the subarray

Example:

const array = [1, 2, [3, 4, [5, 6], 7], 8, 9]
const newArray1 = array.flat() // equivalent to array.flat(1); reduce 1 dimension // newArray1: [1, 2, 3, 4, [ 5, 6 ], 7, 8, 9]
 
const newArray2 = array.flat(2) // Reduce 2 dimensions // newArray2: [1, 2, 3, 4, 5, 6, 7, 8, 9]

special:

When depth<=0, the returned array has the same dimension as the original array (note that only the dimension is the same, see point 3 for the empty space)

const array = [1, 2, [3, 4, [5, 6], 7], 8, 9]
array.flat(-1)
// [1, 2, [3, 4, [5, 6], 7], 8, 9]

depth=Infinity, the returned array becomes one-dimensional

array.flat(Infinity)
// [1, 2, 3, 4, 5, 6, 7, 8, 9]

If there are vacancies in the original array, the flat method will eliminate them. Even flat(0) will eliminate them, so the first point is "only the number of dimensions is the same". And the empty space will be eliminated at the level to which the flat method expands, and the empty space at a deeper level will not be eliminated.

const array1 = [1, , 2, [3, ,4, [5, 6], 7], 8, 9] 
// Note that this array has two empty spaces array.flat(0)
// [ 1, 2, [ 3, ，4, [ 5, 6 ], 7 ], 8, 9 ]
// The first vacancy is gone, but the second vacancy is still there

3 Implementing a flat method

The steps of the flat method to expand one layer (reduce one dimension) are as follows: traverse the array and determine whether the current element is an array. If it is not an array, save it directly; if it is an array, expand it and save it

The flat method expands multiple layers (reduces multiple dimensions) by recursively performing the same operation on the sub-elements of the array based on the expansion of one layer.

This method can be broken down into three steps:

1. How to traverse an array

2. How to determine whether an element is an array

3. Recursion

Implement the above three steps and combine them to get different flat implementations

3.1 How to traverse an array

There are many methods, here are 3 categories:

1. for related

• for loop
• for...of

for...in is built for iterating over object properties and is not recommended for use with arrays.

const array = [1, 2, [3, 4, [5, 6], 7], 8, 9]
// for loop for (let i = 0; i < array.length; i++) {
    const element = array[i];
}
// for...of
for (const element of array) {
    
}

2. Array method: a method that can directly obtain array elements

• forEach()
• reduce()
• map()

// forEach()
array.forEach(element => {
    
});
// reduce()
array.reduce((pre, cur) => {
    const element = cur
}, [])
// map()
array.map(element => {
  
})

3. Array Methods: Methods that Return Iterator Objects

• keys()
• values()
• entries()
  

// These three methods are only to obtain the traversal object, and also need to be used with for...of to traverse // keys()
for (let i of array.keys()) {
  const element = array[i]
}
// values()
for (let element of array.values() ) {
  
}
// entries()
for (let [i, element] of array.entries()) {
  console.log(array[i])
  console.log(element)
}

3.2 How to determine whether an element is an array

Suppose there is a variable a, determine whether it is an array. Here are 4 methods:

• Array has a static method Array.isArray() which is used to determine whether a variable is an array.
• The instanceof operator is used to detect whether the prototype property of the constructor function appears in the prototype chain of an instance object.
  If a is an array, Array.prototype will appear on its prototype chain.
• Determined by the object's constructor (this method may fail because the constructor can be changed manually)
• Judging by Object.prototype.toString(), this method can return a string representing the object

// Method 1
Array.isArray(a)
// Method 2
an instanceof Array
// Method 3
a.constructor === Array
// Method 4
// Use call to call the toString method on Object.prototype Object.prototype.toString.call(a) === '[object Array]'
 
// This cannot be judged, because this toString has already overwritten Object.prototype.toString
// Only Object.prototype.toString can correctly determine the type a.toString()

3.3 Recursion

Recursion: perform the same operation on child elements

function flat() {
  let res = []
  Traverse the array {
    if (the current element is an array) {
      flat(current element) gets a one-dimensional array and concatenates the one-dimensional array into res} else {
      res.push(current element)
    }
  }
  return res
}

3.4 Preliminary implementation of the flat method

By choosing the traversal method and the array judgment method, you can preliminarily implement the flat method with recursion, such as:

function myFlat(arr) {
  let res = [];
  for (const item of arr) {
    if (Array.isArray(item)) {
      res = res.concat(myFlat(item));
      // Note that the concat method returns a new array and does not change the original array} else {
      res.push(item);
    }
  }
  return res;
}

The myFlat method can flatten a multidimensional array into a one-dimensional array, but it cannot specify the depth of the expansion and cannot handle empty arrays.

4 Optimization

4.1 Specifying the expansion depth

It is actually very simple to handle the expansion depth. We can add a recursive termination condition, that is, depth<=0. The code is as follows:

function myFlat(arr, depth = 1) {
  // If depth <= 0, return directly if (depth <= 0) {
      return arr
  }
  let res = [];
  for (const item of arr) {
    if (Array.isArray(item)) {
      // Each recursive call will increment depth-1
      res = res.concat(myFlat(item, depth - 1));
    } else {
      res.push(item);
    }
  }
  return res;
}

4.2 Array Vacancy Processing

In fact, we should try to avoid empty arrays.

Earlier we mentioned different ways to traverse an array, and they handle empty positions in the array differently.

ForEach, reduce, and map will ignore empty spaces when traversing, but for...of will not ignore empty spaces and will treat them as undefined.

4.2.1 for...of adds empty space judgment

So we need to improve the myFlat method that traverses the array in for...of:

function myFlat(arr, depth = 1) {
  if (depth <= 0) {
    return arr;
  }
  let res = [];
  for (const item of arr) {
    if (Array.isArray(item)) {
      res = res.concat(myFlat(item, depth - 1));
    } else {
      // Determine if the array is empty item !== undefined && res.push(item);
    }
  }
  return res;
}

4.2.2 forEach and map method traversal

Of course, you can also use forEach and map methods to traverse the array, so you don’t have to judge manually.

But there is a special case to consider, that is, when depth <= 0, we use the filter method to eliminate array vacancies.

// forEach
function myFlat(arr, depth = 1) {
  if (depth <= 0) {
    return arr.filter(item => item !== undefined);
  }
  let res = [];
  arr.forEach((item) => {
    if (Array.isArray(item)) {
      res = res.concat(myFlat(item, depth - 1));
    } else {
      res.push(item);
    }
  });
  return res;
}
 
// map
function myFlat(arr, depth = 1) {
  if (depth <= 0) {
    return arr.filter(item => item !== undefined);
  }
  let res = [];
  arr.map((item) => {
    if (Array.isArray(item)) {
      res = res.concat(myFlat(item, depth - 1));
    } else {
      res.push(item);
    }
  });
  return res;
}

4.2.3 reduce method

Among them, the reduce method is the most concise and is also one of the methods often tested in interviews.

function myFlat(arr, depth = 1) {
  return depth > 0
    ? arr.reduce(
        (pre, cur) =>
          pre.concat(Array.isArray(cur) ? myFlat(cur, depth - 1) : cur),
        []
      )
    : arr.filter((item) => item !== undefined);
}

5 Others

5.1 Stack

In theory, recursive methods can usually be converted into non-recursive methods, that is, using a stack

function myFlat(arr) {
  let res = [];
  const stack = [].concat(arr);
  while (stack.length > 0) {
    const item = stack.pop();
    if (Array.isArray(item)) {
      // Expand one layer using the spread operator stack.push(...item);
    } else {
      item !== undefined && res.unshift(item);
    }
  }
  return res;
}

However, this method cannot specify the expansion depth and can only be fully expanded into a one-dimensional array.

5.2 Improvements

To improve the disadvantage that the stack cannot specify the expansion depth, the code is as follows:

function myFlat(arr, depth = 1) {
  if (depth <= 0) {
    return arr.filter((item) => item !== undefined);
  }
  let res;
  let queue = [].concat(arr);
  while (depth > 0) {
    res = [];
    queue.forEach((item) => {
      if (Array.isArray(item)) {
        // Note that before using the spread operator to expand the array, use the filter method to remove the empty spaces res.push(...item.filter((e) => e !== undefined));
      } else {
        res.push(item);
      }
    });
    depth--;
    queue = res;
  }
  return res;
}

Summarize

This is the end of this article about how to implement array flattening in JavaScript interviews. For more information about how to implement array flattening in JS, please search for previous articles on 123WORDPRESS.COM or continue to browse the following related articles. I hope you will support 123WORDPRESS.COM in the future!