Flattening Nested Arrays

Implementing Array Flattening in JavaScript

Flattening arrays is a standard FAANG interview problem with two principal implementation patterns:

1. Recursive Implementation with Depth Control

function flatten(arr, depth = 1) {
  if (depth <= 0) return arr.slice();
  const result = [];
  for (const item of arr) {
    if (Array.isArray(item)) {
      result.push(...flatten(item, depth - 1));
    } else {
      result.push(item);
    }
  }
  return result;
}

• Time Complexity: $O(N)$ where $N$ is the total count of elements across all nested arrays.
• Space Complexity: $O(D)$ where $D$ is the maximum recursion depth, plus $O(N)$ for the output array.
• Limitation: Extremely deep recursion (e.g., $D > 10,000$) will trigger RangeError: Maximum call stack size exceeded.

2. Iterative Implementation Using an Explicit Stack

To eliminate call stack limitations, manage state using an in-memory stack:

function flattenIterative(arr) {
  const stack = [...arr];
  const result = [];
  while (stack.length > 0) {
    const next = stack.pop();
    if (Array.isArray(next)) {
      stack.push(...next);
    } else {
      result.push(next);
    }
  }
  return result.reverse();
}

The Sparse Array Trap

A sparse array contains indices that have never been initialized ([1, , 3]). This is fundamentally different from [1, undefined, 3]:

• 1 in [1, , 3] is false (no property key '1' exists on the array).
• 1 in [1, undefined, 3] is true.
• The ECMAScript specification (§ 23.1.3.11) mandates that Array.prototype.flat discards empty slots entirely. [1, , 3].flat() produces [1, 3].