Given a nested array of integers, write a function that returns a flattened array – all nesting is removed, each element is an integer, and order is maintained.
Example:
let nested = [1, [10, 12, 1], [4, [2, 0]], 30];
let flattened = flatten(nested);
console.log(flattened) // [1, 10, 12, 1, 4, 2, 0, 30]The problem here doesn’t require anything crazy. It does, however, elicit a discussion on how to generally approach problem solving. Successfully solving a problem using recursion usually requires some of this upfront (as opposed to playing around with a while-block and pointers until you get what you want).
First, what are the cases? What could the inputs look like, given an input nested array of integers?
[] // empty
[3] // one-element array (int)
[[1,2,3]] // one-element array (another array)
[1, 2, 3, 4, 5] // array of ints
[1, 2, [3,4,5]] // mix of ints and arrays of ints
[1, 2, [3, [4,5]], 6] // arrays within arrays within arraysSecond, what’s the roadblock?
The complication arises when encountering arrays within arrays (within arrays). If we were dealing with just integers, this would be easy (and pointless) because the input would already be flat.
Third, given the cases and the roadblock, how do we break up this “flattening” problem into smaller subproblems?
Each element in the nested array is either an integer or another array. If its an integer, we just need to add it to our flattened array. If it’s an array, though, we need to find a way to “extract” its integer elements and append them to our output array.
So that’s how our problem gets subdivided: as we go through the input array, if the element is an integer, we add it to our output array. If the element is another array, though, we repeat this same procedure locally on the subarray.
Basic Recursive Solution
This conversational routine forms the basis of a recursive solution.
If the current input is just a number, the function returns that number as the sole element of an array.
If the input is an array and has no length, the function returns an empty array.
Otherwise, the function concatenates the return value of a recursive call on the “tail” of the array (list.slice(1)) onto a recursive call on the “head” of the array (list[0]).
Basic Recursion – Pros and Cons
This is just one solution. It’s pretty transparent in how it handles the cases and roadblocks we established. But this solution, depending on the Javascript engine/optimizer being used, may not be the most memory-efficient or time-efficient.
For instance, each time Array.prototype.concat() is called, a new array is created; depending on the browser or environment, concat() and slice() may or may not be optimized.
Additionally, this solution is irksome because it makes two recursive calls per one function call, and both depend on each others return values, which can make recursive calls and allocate new stack frames on the order of 2^n as a worst case.
Tangentially, the recursive call is not in tail position. Tail-positioned recursion is when the return value of that call is the final desired return value (aka we don’t need to otherwise add/divide/multiply/concat/transform it after getting the return value).
In modern Javascript (ES6) and modern Javascript engines, this is important because of tail-call optimization (TCO) being baked in. That is, when the recursive function call is in tail position, TCO ensures that new stack frames aren’t being allocated for every single call because a tail-positioned call just needs to calculate a return value and that’s it. This optimization is huge because now we can express ourselves in Javascript using recursion without having it blow up the call stack.
Phew, hopefully I didn’t botch anything up too badly in that explanation. The great part is that, if we aren’t happy with this solution, since we’ve used recursive thinking to really understand the problem, we won’t have much trouble trying out different approaches to solving it.
Divide-and-Conquer Solution
Another solution to consider takes the divide-and-conquer approach. D&C solves problems by first breaking up the problem into a set of smaller subproblems, then solving and “conquering” each of those back up into one merged solution.
Implementation-wise, this is very similar to the way mergeSort works. You divide the input array into left and right subarrays, and then break each of those down into their own left and right subarrays, until they are at the size we want (either empty or with one element in them).
Once we get to that point, we merge the left with the right (concatenating), then concatenating that merged array onto its complementary right array, and so on, until all of these subarrays have been merged back up into one flattened array.
Let’s walk through the time complexity of this solution.
Divide: Flatten gets called as many times as there are integers in our flattened array. This number (k) is unknown at call time, as we don’t know how deeply nested this input array is.
For many divide-and-conquer algorithms, division works as a function of the number of elements in the input (n), usually at O(log n) because at each step, the array gets divided into two (n, n/2, n/4, n/8, etc). If the input array isn’t deeply nested, we get closer to O(log n) as we can then determine time complexity in terms of input size.
Conquer: This portion takes a time complexity of O(k), as we are simply concatenating k complementary subsections until they merge into 1 array.
Iterative Solution:
While we’re at it, let’s see what a less “recursive” solution would look like.
This time, we’ll use a for-loop to take care of most of the iterating across the array. The only time we’ll make recursive calls is if we run into an element that is not a ‘number’ primitive.
This reads very nicely, and we only make recursive calls if we absolutely have to. Otherwise, we simply push the current element onto the result array, which is an O(1) operation.
I like the reducer best though:
There are many ways to solve this simple problem, each with its pros and cons (and I definitely missed out on some other good ones!). Solving small problems like this in many different ways is reminiscent of that phrase “Make it work, make it right, make it fast.” The most important piece is understanding the problem and coming up with something that gets the job done, even if it’s suboptimal, ugly, or hard to follow. Then, as your needs for its performance increase, the need to refactor the solution also increases.
ammar mian 