⚡Flashcard Drill➔
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

  1. A recursive DFS over the structure, carrying the current depth.
  2. An integer contributes value * depth; a nested list recurses with depth + 1.
  3. The depth starts at 1 for the outermost level.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems