Function that sums up all integers from a deeply nested array

Question

I have an issue here, I'm trying to create a function that sums up all integers from a deeply nested array, but it's failing an unit test, which means something is not right. Here is my function:

export const arraySum = (arr) => {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    if (typeof arr[i] === "number") sum = sum + arr[i];
    else if (Array.isArray(arr[i])) sum = sum + arraySum(arr[i]);
  }
  return sum;
};

And here is my unit test which is failing:

test("it should sum up from deeply nested arrays", () => {
    type ValueOrArray = number | Array<ValueOrArray>;
    const createDeeplyNestedArray = (depth: number): ValueOrArray => {
      let retval: ValueOrArray = [1];
      for (let i = 0; i < depth - 1; i++) {
        retval = [1, retval];
      }
      return retval;
    };

    const NUMBER_OF_ELEMENTS = 100000;
    const arr = createDeeplyNestedArray(NUMBER_OF_ELEMENTS);
    expect(arraySum(arr)).toEqual(NUMBER_OF_ELEMENTS);
  });

Answer 1

That doesn't work bc like Keith said you are reaching the maximum call stack size.

RangeError: Maximum call stack size exceeded is a type of error thrown in JavaScript when a function call is made that exceeds the program's stack size. The call stack is a data structure that keeps track of which functions have been called, and in what order.

Maybe you can try to solve it in a iterative way like this:

 const arraySum = (arr) => {
  if (!Array.isArray(arr)) return 0;
  let sum = 0;
  while (Array.isArray(arr)) {
    let arrCopy = [];
    for (let i = 0; i < arr.length; i++) {
      if (typeof arr[i] === "number") sum = sum + arr[i];
      else if (Array.isArray(arr[i])) arrCopy = arrCopy.concat(arr[i]);
    }
    arr = arrCopy.length > 0 ? arrCopy : null;
  }
  return sum;
};

Answer 2

Function memory is stored on something called a "call stack". Whenever you call a function, all of its variables are allocated and pushed onto the 'stack' and when the function returns, they are popped off the stack. Given the following code:

const a = () => {
}

const b = () => {
   a()
   // some code
}

const c = () => {
   b()
}

c()

When c is called, your call stack will contain all the memory for variables used in c. When c calls b, all the memory for variables used in b are added to the stack. When b calls a all the memory for variables used in a are added to the stack. When a finishes executing (so when you get to 'some code'), variables related to a are deallocated and removed from the stack.

The problem you have here is that every time your function recursively calls itself, more memory is being allocated onto the stack. to stop this kind of code using up all the system memory, the runtime limits how big the stack can get - which is why you are hitting this error.

To pass this test, you need a solution which doesn't call itself every time it hits an array within an array. Here's my solution, effectively using an array as a buffer; each time I hit a nested array I add it to the buffer. Once I finish processing the outer array, I then check if there is any arrays left in the buffer.

export const arraySum = (arr) => {
  let sum = 0;
  const buffer = [arr];
  while (buffer.length > 0) {
    const next = buffer.shift();
    for (let i = 0; i < next.length; i++) {
      if (typeof next[i] === "number") sum = sum + next[i];
      else if (Array.isArray(next[i])) buffer.push(next[i]);
    }
  }
  return sum;
};

Answer 3

We can use a stack or queue in place of recursion. Also, order doesn't matter.

function f(A) {
  let sum = 0;
  let stack = [A];
  
  while (stack.length > 0) {
    stack.pop().forEach(e => {
      if (Array.isArray(e))
        stack.push(e);
      else if (typeof e === "number")
        sum += e;
    });
  }
  
  return sum;
}

console.log(f([1,2,[3,[4]]]));

Answer 4

The approach of combining a flat based flattening function which circumvents call stack errors of very deeply nested arrays of a nesting depth close to 10_000 and higher and a reduce based function which does sum-up number types only, does solve the OP's problem. And the following implementation does prove it ...

// Implementation
function flatAlmostInfiniteNestedArray(arr) {
  while (arr.length < (arr = arr.flat(1000)).length) {
  }
  return arr;
}
function totalNestedNumberValues(arr) {
  return flatAlmostInfiniteNestedArray(arr)
    .reduce((total, value) => (
      'number' === typeof value
        ? total + value
        : total
    ), 0);
}

// Test
const createDeeplyNestedArray = depth => {
  let retval = [1];
  for (let i = 0; i < depth - 1; i++) {
    retval = [1, retval];
  }
  return retval;
};
const NUMBER_OF_ELEMENTS = 100000;
const arr = createDeeplyNestedArray(NUMBER_OF_ELEMENTS);

console.log(
  '(totalNestedNumberValues(arr) === NUMBER_OF_ELEMENTS) ?..',
  (totalNestedNumberValues(arr) === NUMBER_OF_ELEMENTS),
);

.as-console-wrapper { min-height: 100%!important; top: 0; }

Edit ... due to following comments

"Very interesting. I hadn't realized that Array.flat was implemented in a way that would lead to a call stack overflow. It makes sense that it would be, but I didn't know, and have never had a real-world structure where it would matter. Thanks!" – Scott Sauyet

"@ScottSauyet ...the poor man's approach of (mis)using flat as kind of a callstack-safe solution looses if it comes to performance ... jsbench.me :: sum up deeply nested array's number values" – Peter Seliger

One of the above linked performance tests features a better, much more performant, stack based, solution for flattening deeply nested arrays which are critical of being natively flattened due to possible overflowing call stacks.

Thus the formerly provided code example would change to ...

// Implementation
function flatCallstackCriticalNestedArray(nested) {
  const stack = [nested];
  const flat = [];
  let value;

  while (stack.length) {
    if (Array.isArray(value = stack.pop())) {
    
      stack.push(...value);
    } else {
      flat.push(value);
    }
  }
  return flat;
}
function totalNestedNumberValues(arr) {
  return flatCallstackCriticalNestedArray(arr)
    .reduce((total, value) => (
      'number' === typeof value
        ? total + value
        : total
    ), 0);
}

// Test
const createDeeplyNestedArray = depth => {
  let retval = [1];
  for (let i = 0; i < depth - 1; i++) {
    retval = [1, retval];
  }
  return retval;
};
const NUMBER_OF_ELEMENTS = 100000;
const arr = createDeeplyNestedArray(NUMBER_OF_ELEMENTS);

console.log(
  '(totalNestedNumberValues(arr) === NUMBER_OF_ELEMENTS) ?..',
  (totalNestedNumberValues(arr) === NUMBER_OF_ELEMENTS),
);

.as-console-wrapper { min-height: 100%!important; top: 0; }

Answer 5

Have you considered a using library? This might not be as fast as a vanilla solution, but it should still be plenty fast and much more readable.

.as-console-wrapper {max-height: 100% !important; top: 0}

<script type="module">
import objectScan from 'https://cdn.jsdelivr.net/npm/object-scan@18.3.0/lib/index.min.js';

const createDeeplyNestedArray = (depth) => {
  let retval = [1];
  for (let i = 0; i < depth - 1; i += 1) {
    retval = [1, retval];
  }
  return retval;
};

const NUMBER_OF_ELEMENTS = 100000;
const arr = createDeeplyNestedArray(NUMBER_OF_ELEMENTS);

const arraySum = objectScan(['**'], {
  rtn: 'sum',
  filterFn: ({ value }) => typeof value === 'number'
});
console.log(arraySum(arr));
// => 100000
</script>

Disclaimer: I'm the author of object-scan

Note that this will traverse arrays and objects. If you only want to traverse arrays you could use ['**{[*]}'] as search needles.