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.
I hope this post will help you in one way or the other. Do let me know your thoughts in the comments.
Top comments (0)