NeetCode #616LC-339MediumGraphs
← Back to All Problems#616 · #339 · Nested List Weight Sum(嵌套列表加权和)
📌 Problem Statement & Constraints
This is an interactive problem. You are given a nested list of integers where each element is an integer or a list. Return the sum of every integer multiplied by its depth (the outermost level has depth 1). Constraints: the total number of integers is at most 50; the nesting depth is at most 50.
💡 Core Algorithmic Approaches
- A recursive DFS over the structure, carrying the current depth.
- An integer contributes
value * depth; a nested list recurses withdepth + 1. - The depth starts at 1 for the outermost level.
- The whole traversal is O(n) in the number of elements.
💻 Benchmark Python3 Implementation
class Solution:
def depthSum(self, nestedList: "List[NestedInteger]") -> int:
def dfs(items: "List[NestedInteger]", depth: int) -> int:
total = 0
for item in items:
if item.isInteger():
total += item.getInteger() * depth # weight by depth
else:
total += dfs(item.getList(), depth + 1)
return total
return dfs(nestedList, 1) # the outermost level has depth 1⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each element is visited once.
💾 Space Complexity
O(d) for the recursion depth.
⚠️ Interview Pitfalls & Follow-ups
- Starting the depth at 0: the outermost level is depth 1.
- Incrementing the depth for integers as well: only nested lists increase the depth.
- Flattening first and then weighting: the depth information would be lost.
- Confusing this with 364: there the weight is
maxDepth - depth + 1, the reverse.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.