Polyfill: Array.prototype.flat() without recursion
Tags: interview, webdev, programming, javascript
Published: 2024-03-30 05:53:50

`Array.prototype.flat()` is a common polyfill interview question for junior JavaScript Engineers. It challenges the candidate to think recursively and their JavaScript knowledge around Arrays and their existing methods.

Recently I saw the same question with a twist:
**I cannot use recursion.**

My preferred way to do this would have been recursion. It is more intuitive and easier to solve. But solving it iteratively is also possible, given we handle all edge cases.


## Basics

The ask was simple:

Create a polyfill of `Array.prototype.flat(depth)`. It should return a new array flattened up to the depth provided. If depth is not provided its value will be 1. Also, infinity can be passed as a value and has to be handled.


## Approach

The variable `depth` gave me the idea of anchoring my iterations around it. But, to solve the `Infinity` case correctly I need to break out of the loop at the right time. I have to be careful not to create an endless loop.

How can I know when to break out of the loop? I can check if more arrays are left inside the list and can `break;` if not.

The original array is supposed to remain intact, so I know I need to create a copy. 


## Pseudocode 

```
flatIterative = (arr, depth=1) => {
flattenedArray = []
iterations =0

while(iterations < depth){
areArraysLeft = false
for(item in arr) 
  {
  if(isArray(item)){
     areArraysLeft = true
     append item array into flattenedArray
  }
  else{
     push item into flattenedArray
  }
  }
  if(!areArraysLeft){
     return flattenedArray
  }
  iterations++
}

return flattenedArray
}
```

The above was the first pseudocode I came up with. It was missing corner cases. You can try to find it out. Honestly, I ran the code first and then found out:

To replicate a recursive approach, I should iterate over `flattenedArray` and not the original `arr`. The `flattenedArray` might keep changing and I need to check it for array elements and push/append accordingly.

But if I am iterating over `flattenedArray`, then I cannot push into `flattenedArray` itself, I need to start from scratch with an empty array. The idea is that at every iteration, I should be starting from a new array otherwise I will end up with duplicates and another endless loop.

So the revised pseudo code looked like this:

```
flatIterative = (arr, depth=1) => {
flattenedArray = []
copyArray = arr
iterations =0

while(iterations < depth){
areArraysLeft = false
for(item in copyArray) 
  {
  if(isArray(item)){
     areArraysLeft = true
     append item array into flattenedArray
  }
  else{
     push item into flattenedArray
  }
  }
  if(!areArraysLeft){
     return flattenedArray
  }
  iterations++
  if(iterations < depth){
      copyArray = flattenedArray
      flattenedArray= []
  }

}

return flattenedArray
}
```

The last check is necessary so I am iterating over the right array and adding items to the right array. 


## Final Code

The above pseudo code looks good. To arrive at it I had to run my code on my machine a few times, but in a real interview, we should aim to use a pen-paper and dry run for edge cases.

Luckily we have existing JavaScript methods to do certain things:
For array check we have `Array.isArray()`
For pushing an item at the end, we have `Array.prototype.push()`
For appending another array from the end, we have `Array.prototype.concat()`

And this is how the final code looked like:

```
const flatIterative = (arr, depth=1) => {
  let iterations = 0;
  let flattenedArray = [];
  let copyArray = arr;
  while(iterations < depth){
    let isArrayLeft = false;
    for(let i = 0 ; i < copyArray.length;i++){
      if(Array.isArray(copyArray[i])){
        isArrayLeft = true;
        flattenedArray = flattenedArray.concat(copyArray[i]);
      }
      else{
        flattenedArray.push(copyArray[i]);
      }
      
    }
    if(isArrayLeft === false) return flattenedArray;
    iterations++;
    if(iterations < depth){
      copyArray = flattenedArray;
      flattenedArray= [];  
    }
  }
  
  return flattenedArray;
};
```

Here is the [codepen link](https://codepen.io/tushar8/pen/YzMVbmp?editors=1011).

I hope this post will help you in one way or the other. Do let me know your thoughts in the comments.