Product Sum

Tags

Product Sum

Category

Recursion

Difficulty

Easy

Problem Statement

Write a function that takes a special array (an array that can contain integers and other nested special arrays) and returns its product sum. The product sum of a special array is the sum of its elements, where nested arrays are summed and then multiplied by their depth level. The outermost array has a depth of 1.

For example, [5, 2, [7, -1], 3, [6, [-13, 8], 4]] has a product sum of 12.

Intuition

Each level of nesting introduces a multiplier equal to the current depth. A nested array's contribution to the total is amplified by how deeply it is nested. Recursion naturally models this: every time we encounter a sub-array, we recurse with an incremented depth, and the returned sum gets multiplied by that depth.

Approach

  1. Define a recursive helper that accepts the array and the current depth (starting at 1).
  2. Initialize a running sum to 0.
  3. Iterate through each element in the array:
    • If the element is a number, add it to sum.
    • If the element is an array, recursively call the helper with depth + 1 and add the result to sum.
  4. Return sum * depth.

Pseudocode

function productSum(array, depth = 1):
    sum = 0
    for element in array:
        if element is an array:
            sum += productSum(element, depth + 1)
        else:
            sum += element
    return sum * depth

Time & Space Complexity

  • Time: O(n) where n is the total number of elements including those inside nested arrays. Every element is visited exactly once.
  • Space: O(d) where d is the maximum depth of nesting, due to the recursive call stack.

Key Insights

  • The multiplication by depth happens at the return step, meaning inner sums are first computed and then scaled.
  • This is a natural application of recursion: the structure of the data (nested arrays) mirrors the structure of the solution (nested function calls).
  • The depth multiplier compounds — an element nested 3 levels deep effectively gets multiplied by 1 * 2 * 3... no, it gets multiplied only by its own level's depth, but the outer multiplications cascade. For example, a value at depth 3 is multiplied by 3, and that result is part of a sum multiplied by 2, which in turn is part of a sum multiplied by 1. So the effective multiplier is 3 * 2 * 1 = 6... Actually, re-reading the definition: the sum at each depth level is multiplied by that depth. So the compounding does occur.

Edge Cases

  • Empty array [] should return 0.
  • Array with no nesting, e.g., [1, 2, 3], returns 6 (sum multiplied by depth 1).
  • Deeply nested single elements, e.g., [[[5]]] — the value 5 is at depth 3, so: depth 3 sum = 5 * 3 = 15, depth 2 sum = 15 * 2 = 30, depth 1 sum = 30 * 1 = 30.
  • Negative numbers within nested arrays.
  • Arrays containing only other arrays with no direct integer elements.

Linked mentions