Nested List Weight Sum II - Practice Coding Problems

Nested List Weight Sum II - 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.

Let maxDepth be the maximum depth of any integer. The weight of an integer is maxDepth - (the depth of the integer) + 1.

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

Input & Output

Example 1 — Basic Nested Structure

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

› Output: 12

💡 Note: Max depth is 2. Elements: 1 at depth 1 (weight 2), 4 at depth 2 (weight 1), 6 at depth 2 (weight 1). Sum = 1×2 + 4×1 + 6×1 = 12

Example 2 — Deeper Nesting

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

› Output: 17

💡 Note: Max depth is 3. Weights: depth 1→3, depth 2→2, depth 3→1. Sum = 1×3 + 2×2 + 2×2 + 3×1 + 2×2 + 1×3 = 17

Example 3 — Single Level

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

› Output: 6

💡 Note: All elements at depth 1, weight = 1. Sum = 1×1 + 2×1 + 3×1 = 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 50

Visualization

Tap to expand

Understanding the Visualization

Input

Nested list [1,[4,6]] with varying depths

Process

Calculate weights: deeper = lighter weight

Output

Weighted sum = 12

Key Takeaway

🎯 Key Insight: Inverted weighting gives higher weights to shallower elements (opposite of traditional depth weighting)

Asked in

Li LinkedIn 35 f Facebook 28 G Google 22

The key insight is that weight = maxDepth - currentDepth + 1 inverts the traditional depth weighting. Best approach uses BFS level processing to avoid needing max depth upfront. Time: O(n), Space: O(w) where w is maximum level width.

Common Approaches

Approach	Time	Space	Notes
✓ BFS Level Processing	O(n)	O(w)	Process elements level by level, calculating sum as we discover max depth
Two-Pass DFS	O(n)	O(d)	Find max depth first, then calculate weighted sum with second traversal

BFS Level Processing — Algorithm Steps

Step 1: Process elements level by level using queue
Step 2: Adjust sum when discovering new depth levels

Visualization

Tap to expand

Step-by-Step Walkthrough

Level 1

Process [1,[4,6]] → sum = 1

Level 2

Process [4,6] → sum = 10

Calculate

1×2 + 10×1 = 12

Code -

solution.c — C

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

#define MAX_QUEUE 1000
#define MAX_LEVELS 10

typedef struct {
    int value;
    int depth;
} QueueItem;

QueueItem queue[MAX_QUEUE];
int front = 0, rear = 0;
int levelSums[MAX_LEVELS];
int levelCount = 0;

void enqueue(int value, int depth) {
    queue[rear].value = value;
    queue[rear].depth = depth;
    rear++;
}

QueueItem dequeue() {
    return queue[front++];
}

int isEmpty() {
    return front >= rear;
}

void parseAndEnqueue(const char* str, int* pos, int depth) {
    if (str[*pos] == '[') {
        (*pos)++; // skip '['
        while (str[*pos] != ']') {
            if (str[*pos] == ',') (*pos)++;
            parseAndEnqueue(str, pos, depth + 1);
        }
        (*pos)++; // skip ']'
    } else {
        int num = 0;
        int sign = 1;
        if (str[*pos] == '-') {
            sign = -1;
            (*pos)++;
        }
        while (isdigit(str[*pos])) {
            num = num * 10 + (str[*pos] - '0');
            (*pos)++;
        }
        enqueue(sign * num, depth);
    }
}

int solution(const char* input) {
    front = rear = 0;
    levelCount = 0;
    
    int pos = 1; // skip first '['
    while (input[pos] != ']') {
        if (input[pos] == ',') pos++;
        parseAndEnqueue(input, &pos, 1);
    }
    
    // Process by levels
    int maxDepth = 0;
    while (!isEmpty()) {
        QueueItem item = dequeue();
        if (item.depth > maxDepth) {
            maxDepth = item.depth;
            if (levelCount < item.depth) levelCount = item.depth;
        }
        if (item.depth <= MAX_LEVELS) {
            levelSums[item.depth - 1] += item.value;
        }
    }
    
    int totalSum = 0;
    for (int i = 0; i < levelCount; i++) {
        int weight = maxDepth - i;
        totalSum += levelSums[i] * weight;
    }
    
    return totalSum;
}

int main() {
    char input[1000];
    fgets(input, sizeof(input), stdin);
    input[strcspn(input, "\n")] = 0;
    
    int result = solution(input);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single BFS traversal visiting all n elements once

✓ Linear Growth

Space Complexity

O(w)

Queue stores at most w elements where w is maximum width at any level

✓ 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

BFS Level Processing — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler