Construction
What is this?
Some problems are hard because the algorithm is hard. These are hard because the algorithm is short and the boundaries are not. Inserting into a sorted circular list is a three-line splice, except at the one place in the ring where the values stop ascending, when every value is identical, and when the list is empty. Miss any of those and you have an infinite loop rather than a wrong answer.
The second problem is a different kind of trap: you are asked to weight items by how shallow they are, but you do not learn the maximum depth until you have already walked the whole structure. The third, Plus One Linked List, has a carry that flows right to left in a list you can only walk left to right.
Fun fact: Nested List Weight Sum II has a solution that looks like sleight of hand. Instead of finding the maximum depth and then weighting, you keep a running total of every level's unweighted sum and add that running total to the answer once per level. A value at depth 1 in a 3-deep structure ends up counted three times, one at depth 3 exactly once, which is precisely the inverse-depth weight. You never multiply by a depth; repetition does the multiplication for you.
🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Short version: enumerate the boundary cases before writing the loop. A sorted ring has exactly one discontinuity and two degenerate shapes; a depth-weighted sum has one unknown you can either resolve with a first pass or dissolve by accumulating differently.
1. The three insertion cases
Walk prev/curr around the ring once. Insert when any of these holds:
| Case | Test | Meaning |
|---|---|---|
| In order | prev.val <= v <= curr.val |
the ordinary slot, between two ascending values |
| At the wrap | prev.val > curr.val and (v >= prev.val or v <= curr.val) |
v is a new maximum or a new minimum; both belong at the seam |
| Uniform | you returned to the start without inserting | every value is equal, so any position is correct |
The wrap case is the one that gets missed. In a ring like 3 → 4 → 1 → 2 → (3), the descent from 4 to 1 is the seam, and inserting 5 (a new max) or 0 (a new min) both happen there, which is why one test covers two situations that feel opposite.
The uniform case is why the loop must be bounded. 1 → 1 → 1 never satisfies either test, so without a "stop after one full lap" guard the walk never terminates.
2. The inverse-depth accumulation
Two approaches, and the contrast is the lesson.
Two passes. Find maxDepth, then walk again summing value × (maxDepth − depth + 1). Direct, obvious, easy to defend.
One pass, no depths. Process level by level. Keep running (the total of every integer seen so far, unweighted) and add it to answer after each level that holds an integer. Skip levels that hold only empty lists, or the answer is too big ([-3, [[]], 5] is 2, not 4):
The value 2 was folded into running at level 1 and then re-added at level 2, so it contributed twice, exactly its weight. Shallow things get counted more often because they were added earlier.
3. Where you'll actually meet this
- Consistent hashing. Placing a node on a hash ring is the seam problem: the wrap from the largest hash back to the smallest must be handled. Real systems keep the ring in a sorted array or tree rather than a linked list, so the list version is the interview model of the idea.
- Arbitrary-precision integers. Incrementing a bignum is the Plus One idea: the carry stops at the first digit that does not overflow.
- Nested documents. Scoring JSON or outline-style content by how shallow each value sits is the second problem's shape.
4. Problems in this chapter
Insert into a Sorted Circular Linked List
Splice a value into a ring while preserving sorted order. Three cases, one full-lap termination guard, and an empty-list case that must point the new node at itself.
Pattern: ring traversal with case analysis. Target: O(n) time, O(1) space.
Nested List Weight Sum II
Sum integers weighted by inverse depth. Either find the maximum depth first, or accumulate level sums and add the running total once per level so shallow values are counted more often.
Pattern: level-order accumulation. Target: O(n) time, O(W) space for the widest level in the queue.
Plus One Linked List
Add one to a number stored one digit per node, most significant first. Find the rightmost digit that is not 9: bump it, zero everything after it, and prepend a new head only when every digit is a 9.
Pattern: find the pivot in one forward pass. Target: O(n) time, O(1) space.
5. Common pitfalls
- No termination guard on the ring walk. With all-equal values neither insertion test ever fires; stop after returning to the entry node.
- Forgetting the empty list. A brand-new single node must point to itself, or the ring invariant is broken for every later insertion.
- Treating new-max and new-min as separate cases. Both belong at the seam; one combined test is simpler and less error-prone.
- Comparing with strict
<. Duplicates are legal in a sorted ring, so the in-order test needs<=on at least one side. - Confusing the two weight-sum variants. In the first version weight increases with depth (a plain recursion works); here it decreases, which is why the naive recursion cannot know the weight when it reaches a leaf.
- Recomputing depth per element. If you go the two-pass route, compute
maxDepthonce, not per value. - Treating all-9s like any other list.
9 → 9 → 9has no non-9 to bump, so Plus One needs a new leading1node. - Adding the running sum for empty levels. In Weight Sum II, a level with no integer must not add
runningagain.
6. Key takeaways
- Enumerate the boundaries before the loop. In a ring that means the seam, the uniform list, and the empty list.
- The wrap point is where new extremes belong: one test, two situations.
- Bound every circular traversal. One full lap, then stop.
- When a weight depends on something you learn later, either take a first pass to learn it or restructure the accumulation so it never needs to be known.
- Repetition can stand in for multiplication. Adding a running sum once per level is inverse-depth weighting.
- Why interviewers like it: all three problems are short, and both fail on inputs a hurried candidate never considers, which makes them efficient tests of care rather than cleverness.
Order: Insert into a Sorted Circular Linked List → Nested List Weight Sum II → Plus One Linked List.
Nested List Weight Sum II
Core idea: Flip the weights of Nested List Weight Sum I: now the deepest integers count least (weight 1) and the shallowest count most. You can skip computing
maxDepth: keep a running unweighted sum across BFS levels and add it to the total at every level, so each shallow value is counted once for every level from its own down to the bottom.
Problem, rephrased
You're scoring a document outline in which top-level sections set the theme and a footnote buried five sublevels deep barely moves the needle. You're given nestedList, a nested list of integers: each element is either a plain integer or another list whose elements are again integers or lists, to any depth. There is no depth field. Each element is a NestedInteger handle: ask isInteger(), read getInteger() if true, otherwise descend via getList().
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson