Nested List Weight Sum - Practice Coding Problems

Nested List Weight Sum - Problem

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists.

The depth of an integer is the number of lists that it is inside of. For example, the nested list [1,[2,2],[[3],2],1] has each integer's value set to its depth.

Return the sum of each integer in nestedList multiplied by its depth.

Input & Output

Example 1 — Basic Nested Structure

$ Input: nestedList = [[1,1],2,[1,1]]

› Output: 10

💡 Note: Four 1's at depth 2, one 2 at depth 1: 1×2 + 1×2 + 2×1 + 1×2 + 1×2 = 2+2+2+2+2 = 10

Example 2 — Deeper Nesting

$ Input: nestedList = [1,[4,[6]]]

› Output: 27

💡 Note: 1 at depth 1, 4 at depth 2, 6 at depth 3: 1×1 + 4×2 + 6×3 = 1 + 8 + 18 = 27

Example 3 — Single Level

$ Input: nestedList = [1,2,3]

› Output: 6

💡 Note: All integers at depth 1: 1×1 + 2×1 + 3×1 = 1 + 2 + 3 = 6

Constraints

1 ≤ nestedList.length ≤ 50
The values of the integers in the nested list is in the range [-100, 100]
The maximum depth of any integer is less than or equal to 10

Visualization

Tap to expand

Understanding the Visualization

Input

Nested list with integers at various depths

Process

Multiply each integer by its depth level

Output

Sum of all weighted values

Key Takeaway

🎯 Key Insight: Track depth during traversal - deeper elements contribute more to the weighted sum

Asked in

Li LinkedIn 15 G Google 8 f Facebook 6 a Amazon 4

The key insight is to track depth while traversing the nested structure. Use DFS with depth parameter - multiply each integer by its depth and sum all results. Best approach is recursive DFS. Time: O(n), Space: O(d)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Recursive	O(n)	O(d)	Simple recursive traversal counting depth manually
Breadth-First Search	O(n)	O(n)	Level-by-level traversal using queue
Optimized DFS	O(n)	O(d)	Depth-first search with single pass traversal

Brute Force Recursive — Algorithm Steps

Start with depth 1
For each element, check if integer or list
If integer: add value × depth to sum
If list: recursively process with depth + 1

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with depth=1, traverse each element

Process

For integers: add value×depth, for lists: recurse with depth+1

Sum

Accumulate weighted sum from all recursive calls

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

typedef struct NestedItem {
    int isInteger;
    int value;
    struct NestedItem** items;
    int size;
} NestedItem;

int dfs(NestedItem** nested, int size, int depth) {
    int total = 0;
    for (int i = 0; i < size; i++) {
        if (nested[i]->isInteger) {
            total += nested[i]->value * depth;
        } else {
            total += dfs(nested[i]->items, nested[i]->size, depth + 1);
        }
    }
    return total;
}

int solution(NestedItem** nestedList, int size) {
    return dfs(nestedList, size, 1);
}

NestedItem** parseNestedList(const char* s, int* size) {
    // Simplified parsing for basic cases
    NestedItem** result = malloc(10 * sizeof(NestedItem*));
    *size = 0;
    
    int i = 1;
    while (i < strlen(s) - 1) {
        if (s[i] == '[') {
            // Handle nested array parsing
            i++;
        } else if (isdigit(s[i]) || s[i] == '-') {
            int start = i;
            if (s[i] == '-') i++;
            while (i < strlen(s) && isdigit(s[i])) i++;
            
            NestedItem* item = malloc(sizeof(NestedItem));
            item->isInteger = 1;
            item->value = atoi(s + start);
            result[(*size)++] = item;
        } else {
            i++;
        }
    }
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int size;
    NestedItem** nestedList = parseNestedList(line, &size);
    
    int result = solution(nestedList, size);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each element exactly once where n is total number of elements

✓ Linear Growth

Space Complexity

O(d)

Recursion stack depth equals maximum nesting depth d

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Recursive — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler