Nested Array Sum

01 · Question

A nested array contains integers or other nested arrays. Return the sum of all integers at any depth. The input is finite and acyclic; empty nested arrays contribute zero.

Examples: [1,[2,3],[4,[5]],6] → 21; [[[[1]],2]] → 3; [] → 0; [[],[-2,[5]],0] → 3.

In Go, arrays are represented by []any, containing values of type int or nested []any.

02 · Analysis

Eager: a call accepts an array; it adds integer children directly and recurses only on arrays. Lazy: the helper accepts either an integer or an array; an integer is a base case, and every child gets a call.

Both are correct with consistent contracts. Empty arrays return the initial sum of zero. Every recursive call descends into a contained item, so finite acyclic input terminates.

Let N count all integer entries and array containers, including empty arrays, and H be the maximum nesting depth. Both use O(N) time and O(H) stack space (O(1) for empty input). Counting only integers would miss work on deeply nested empty arrays. Very deep inputs may require iterative traversal to avoid runtime stack limits; an explicit stack also consumes memory.

03 · Solution

Reference solution

1. Eager: recurse only on nested arrays

1def nested_array_sum(arr):
2    total = 0
3    for item in arr:
4        if isinstance(item, int):
5            total += item
6        else:
7            total += nested_array_sum(item)
8    return total

2. Lazy: integers are base cases

1def nested_array_sum(value):
2    if isinstance(value, int):
3        return value
4    total = 0
5    for item in value:
6        total += nested_array_sum(item)
7    return total

Robot Instructions

Powers Mod M