JavaScript Interview Question: Flatten an array | Solved iteratively and recursively with tradeoffs declared

explanation.md

When I originally sought to tackle this problem I chose the easier recursive solution to solve it with. However, due to the fact that in JavaScript Proper Tail Calls (PTC) (correct me if I'm wrong) are not currently supported and it seems like there's little hope that they'll be one soon. If they were, the trade offs here might be different (I haven't really thought through that scenario yet). For more on that see TC39/#22 and the transcript of the TC30 discussion.

For those of you that don't know, if we had PTC the stack growth issue with recursion would not be a problem. Meaning our memory complexity for the stack would be constant.

Anyway, the recursive solution is obviously much much easier but limited by the stack - which is never a great thing. So, depending on the size of your inputs, it may simply fail entirely.

So, I decided to implement it iteratively as well.

Time and Space Complexity Trade-offs

Disclaimer: I may be wrong here and overthinking this, so any help is welcome in adding to my understanding of the complexities.

Recursive Solution

T: O(n + m) S: O(n + m) (limited by stack)

Time Explanation I've read in many places that the time complexity of this is simply a linear O(n), however, I think this is incorrect based on my understanding it seems like we have two variables.

n = the number of items in all arrays m = the largest number of nested arrays

During the recursive function we must iterate over each nested array and each item in the array. Given the examples below we can see how n and m are two separate variables.

No nested arrays = [1,2,3,4,5] would iterated a total of 5 times Only nested arrays = [[[[[4]]]]] would iterate a total of 1 + 5 times (1 for the item in the final array and 5 for each nested array). This might not matter so much here and maybe we can just use O(n) to represent this, but the two variables are very different in determining Space Complexity which is why it seems logical that we represent them separately here as well.

Space Explanation So, here, we definitely have two different independent variables in determining our space complexity.

n = the total number of non-array items m = the deepest collection of nested arrays this is the important part

Given the input [[[[1,2]]]] We would return a new array of length 2 (representing n) and at the greatest height our function stack grows to is 4, obviously two different independent variables.

Final remark: imagine we had an input like [[[[[...[1]...]]]]] where the ... represent some very large number, we could easily blow the stack (oh how I wish we had Proper Tail Calls).

So, that's why the iterative solution should also be a consideration.

Iterative Solution

This is actually a pretty cool solution - we can we just implement the stack ourselves instead of using the call stack to track our location.

T: O((n + m) * m) (see optimizations for improving this) S: O(n + m)

Time Explanation

With the iterative solution, our time complexity is worse because of the get function call made every time we do the while loop. Technically, get is actually called twice everytime we loop since exists calls it as well. But since we drop the constants O(n * 2m) is simply O(n * m). We could optimize that, but I haven't done that yet. So, lets look at an example to confirm this.

Let's say we have the following input [[1],[[2]],[[[3]]]] For the final (3rd) item in the root array our collected indices will look like [2, 0, 0] representing the location in the nested array. This array must be iterated over every time we do our while loop. And the while loop will be represented by O(n + m) where n represents the number of non-array items and m is the total number of nested arrays.

Space Complexity Each time we find a nested array, we must add a new index to the custom stack that we've built to keep track of where in the array we're currently at. This is reprsented by m and n is the number of non-array items that will exist in the returned flattened array.

Optimizaions

... maybe later. But for now, this was my first pass. I did this all in about 1 hour to practice for solving problems like these when necessary.

Ah, looking over this again I see that for the iterative solution we could also keep a refererence to the current array to prevent using the get function and exists as well. This would simplify the logic and decrease the time complexity to O(n + m)

Implement tail call optimization anyway.

flatten-array.js

/**
 * In general, I chose for each of my functions to return a new array so that 
 * inherintely means the space complexity is at least O(n). But see explanation.md
 * for more detail.
 */

/********************
 * Recursive Solution
 ********************/

function flattenArrayRecursive(arr, flattened = []) {
  arr.forEach(item => {
    Array.isArray(item) ? flattenArrayRecursive(item, flattened) : flattened.push(item)
  })
  return flattened
}

/********************
 * Iterative Solution
 ********************/

/**
 * Return the nested array item given the arr and indices
 */
function get(arr, indices) {
  let item = arr[indices[0]]
  indices.forEach((index, i) => {
    // skip the first index because we already set it on the first line of this function
    if (i !== 0) {
      item = item[index]
    }
  })
  return item
}

/**
 * Return true or false based on whether the nested item in arr exists or not
 */
function exists(arr, indices) {
  const indicesWithoutLast = [...indices]
  const lasti = indicesWithoutLast.pop()
  const lastArr = indicesWithoutLast.length > 0 ? get(arr, indicesWithoutLast) : arr
  return lasti <= lastArr.length - 1
}

function flattenArrayIterative(arr) {
  if (!Array.isArray(arr)) return
  let flat = []
  if (arr.length === 0) return flat

  const indices = [0]

  while (indices.length > 0) {
    if (!exists(arr, indices)) {
      indices.pop()
      if (indices.length !== 0) {
        indices.push(indices.pop() + 1)
      }
      continue
    }

    const item = get(arr, indices)
    if (Array.isArray(item)) {
      indices.push(0)
      continue
    }

    flat.push(item)
    indices.push(indices.pop() + 1)
  }

  return flat
}