Flatten a Multilevel Doubly Linked List

📋

Problem

Imagine you have a complex file system where folders can contain files and other folders nested arbitrarily deep. You want to list all files in a single linear order, flattening the hierarchy.

You are given a doubly linked list where in addition to the next and previous pointers, each node may have a child pointer, which may point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure. Flatten the list so that all the nodes appear in a single-level, doubly linked list. The nodes should appear in the order they are encountered in a depth-first traversal.

1 ≤ Number of nodes ≤ 10^5Node values are integersChild pointers may be nullThe list may be empty (head is null)

Edge cases: Empty list (head is null) → output is nullList with no child pointers → output is the same listList where every node has a child → output is a deeply nested flattened list

</>

IDE

def flatten(head: 'Node') -> 'Node':public Node flatten(Node head)Node* flatten(Node* head)function flatten(head)

def flatten(head):
    # Write your solution here
    pass

class Solution {
    public Node flatten(Node head) {
        // Write your solution here
        return null;
    }
}

#include <vector>
using namespace std;

Node* flatten(Node* head) {
    // Write your solution here
    return nullptr;
}

function flatten(head) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Flattened list missing child nodes or child lists appended at the end onlyGreedy approach that flattens child lists only after traversing next nodes✅ Flatten child lists immediately when encountered before continuing with next nodes

Wrong: Infinite loop or repeated nodes in outputNot clearing child pointers after flattening causing repeated processing✅ Set node.child = null after flattening its child list

Wrong: Broken doubly linked list with incorrect prev pointersNot updating prev pointers when linking child lists✅ Set child.prev = current node and child's last next.prev = original next node

Wrong: Function crashes or returns non-null on empty inputNo base case for null head input✅ Add base case: if head is null, return null immediately

Wrong: Function modifies single node or returns null incorrectlyIncorrect handling of single node with no child✅ Return head immediately if no child or next nodes

✓

Test Cases

Make sure your solution handles empty and single-node lists correctly.

Watch out for greedy approaches and pointer update errors.

Focus on algorithmic complexity and avoid nested loops.

t1_01basic

Input{"head":[1]}

Expected{"val":1,"prev":null,"next":{"val":2,"prev":null,"next":{"val":3,"prev":null,"next":{"val":7,"prev":null,"next":{"val":8,"prev":null,"next":{"val":11,"prev":null,"next":{"val":12,"prev":null,"next":{"val":9,"prev":null,"next":{"val":10,"prev":null,"next":{"val":4,"prev":null,"next":{"val":5,"prev":null,"next":{"val":6,"prev":null,"next":null,"child":null},"child":null},"child":null},"child":null},"child":null},"child":null},"child":null},"child":null},"child":null},"child":null},"child":null},"child":null}

⏱ Performance - must finish in 2000ms

Starting at head 1, traverse next nodes until 3, then go down child list starting at 7, flattening recursively, then continue with 4, 5, 6.

💡 Think about depth-first traversal of the multilevel list.

💡 Use a stack or recursion to process child lists before continuing with next nodes.

💡 Link child list between current node and next node, then nullify child pointer.

Why it failed: Incorrect flattening order or missing child nodes. Fix by ensuring child lists are inserted immediately after current node before continuing with next nodes. This is the canonical example test.

✓ Correctly flattened the multilevel doubly linked list preserving DFS order.

t1_02basic

Input{"head":[1]}

Expected{"val":1,"prev":null,"next":{"val":2,"prev":null,"next":{"val":3,"prev":null,"next":{"val":4,"prev":null,"next":{"val":5,"prev":null,"next":null,"child":null},"child":null},"child":null},"child":null},"child":null}

⏱ Performance - must finish in 2000ms

Node 3 has a child list 4->5 which is flattened between 3 and null.

💡 Check if child lists are inserted immediately after their parent node.

💡 Ensure child pointers are set to null after flattening.

💡 Update prev pointers correctly when linking child lists.

Why it failed: Child list not inserted or child pointer not cleared. Fix by linking child list after current node and nullifying child pointer.

✓ Child list correctly flattened and linked.

t2_01edge

Input{"head":null}

Expectednull

⏱ Performance - must finish in 2000ms

Empty list input should return null.

💡 Check if input head is null before processing.

💡 Return null immediately if list is empty.

💡 Avoid dereferencing null pointers.

Why it failed: Function crashes or returns non-null on empty input. Fix by adding base case: if head is null, return null.

✓ Correctly handles empty list input.

t2_02edge

Input{"head":[1]}

Expected{"val":1,"prev":null,"next":null,"child":null}

⏱ Performance - must finish in 2000ms

Single node with no child remains unchanged after flattening.

💡 Test with minimal input of one node.

💡 Ensure function returns the same node if no child exists.

💡 Check that no pointers are incorrectly modified.

Why it failed: Function modifies single node or returns null incorrectly. Fix by returning head immediately if no child or next nodes.

✓ Correctly returns single node unchanged.

t2_03edge

Input{"head":[1]}

Expected{"val":1,"prev":null,"next":{"val":5,"prev":null,"next":{"val":2,"prev":null,"next":{"val":3,"prev":null,"next":{"val":4,"prev":null,"next":null,"child":null},"child":null},"child":null},"child":null},"child":null}

⏱ Performance - must finish in 2000ms

Every node has a child, resulting in a deeply nested flattened list preserving DFS order.

💡 Test deep nesting of child pointers.

💡 Ensure recursive or stack-based DFS fully traverses all levels.

💡 Verify child pointers are cleared after flattening.

Why it failed: Partial flattening or missing nested children. Fix by recursively flattening all child lists before continuing.

✓ Correctly flattens deeply nested child lists.

t3_01corner

Input{"head":[1]}

Expected{"val":1,"prev":null,"next":{"val":5,"prev":null,"next":{"val":2,"prev":null,"next":{"val":3,"prev":null,"next":{"val":4,"prev":null,"next":null,"child":null},"child":null},"child":null},"child":null},"child":null}

⏱ Performance - must finish in 2000ms

Greedy approach that flattens child lists only when next is null fails here; correct DFS order requires flattening child of 1 before continuing to 2.

💡 Beware of flattening child lists only at the end of next nodes.

💡 Use DFS to flatten child lists immediately after current node.

💡 Insert child list between current node and next node, not after traversing next nodes.

Why it failed: Greedy flattening after next traversal causes incorrect order. Fix by flattening child list immediately when found, before continuing next.

✓ Correct DFS order flattening, not greedy.

t3_02corner

Input{"head":[1]}

Expected{"val":1,"prev":null,"next":{"val":2,"prev":null,"next":{"val":3,"prev":null,"next":null,"child":null},"child":null},"child":null}

⏱ Performance - must finish in 2000ms

Confusing 0/1 flattening with unbounded: child list must be flattened once per node, not repeatedly or infinitely.

💡 Ensure child lists are flattened exactly once per node.

💡 Avoid loops or repeated flattening of the same child.

💡 Clear child pointer after flattening to prevent reprocessing.

Why it failed: Repeated flattening or infinite loops due to not clearing child pointer. Fix by setting child to null after flattening.

✓ Child pointer cleared and flattened exactly once.

t3_03corner

Input{"head":[1]}

Expected{"val":1,"prev":null,"next":{"val":2,"prev":null,"next":{"val":3,"prev":null,"next":{"val":4,"prev":null,"next":null,"child":null},"child":null},"child":null},"child":null}

⏱ Performance - must finish in 2000ms

Off-by-one errors in linking prev and next pointers cause broken doubly linked list after flattening.

💡 Carefully update prev pointers when linking child lists.

💡 Check that child's prev points to current node after insertion.

💡 Verify next pointers of last child node link to original next node.

Why it failed: Prev or next pointers not updated correctly causing broken links. Fix by setting child.prev = current and child's last next.prev = original next.

✓ All prev and next pointers correctly updated.

t4_01performance

Input{"head":[1]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100000 nodes linked linearly with no children; O(n) expected to complete within 2s.

💡 Use iterative or recursive DFS with O(n) time complexity.

💡 Avoid repeated traversals or nested loops causing O(n^2).

💡 Use stack or recursion carefully to avoid stack overflow.

Why it failed: TLE due to O(n^2) or exponential complexity. Fix by using O(n) DFS or iterative stack approach.

✓ Algorithm runs in O(n) time and passes performance test.

Practice

1. You need to design a data structure that supports adding intervals, removing intervals, and querying whether a given range is fully covered by the added intervals. Which approach guarantees efficient updates and queries with logarithmic time complexity per operation?

easy

A. Use a balanced binary search tree (e.g., TreeMap) to store and merge intervals, enabling logarithmic time operations.

B. Use a brute force list of intervals and scan all intervals for each operation.

C. Use dynamic programming to precompute coverage for all possible ranges.

D. Use a greedy algorithm that always merges intervals only when queried.

Solution

1. Step 1: Understand the problem requirements

   The data structure must support add, remove, and query operations on intervals efficiently.

2. Step 2: Evaluate approaches

   Brute force scanning is O(n) per operation, which is inefficient. DP is not suitable for dynamic interval updates. Greedy merging only on query delays merging and leads to inefficient queries. Balanced BST with interval merging maintains sorted intervals and merges overlapping ones, supporting O(log n) operations.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Balanced BST with merging -> O(log n) per operation [OK]

Hint: Balanced BST with merging enables efficient interval operations [OK]

Common Mistakes:

• Thinking DP or greedy solves dynamic interval updates efficiently

2. Given the following addRange method snippet from the optimal RangeModule implementation, what is the value of self.starts after calling addRange(2, 6) on an initially empty RangeModule?

def addRange(self, left: int, right: int) -> None:
    i = bisect_left(self.starts, left)
    j = bisect_right(self.starts, right)

    if i != 0 and self.intervals[self.starts[i-1]] >= left:
        i -= 1
        left = min(left, self.starts[i])
    if j != 0:
        right = max(right, self.intervals[self.starts[j-1]])

    for k in self.starts[i:j]:
        del self.intervals[k]
    self.starts[i:j] = [left]
    self.intervals[left] = right

easy

A. [2, 6, 7]

B. [2, 6]

C. [2]

D. [6]

Solution

1. Step 1: Trace bisect indices on empty starts list

   Initially, self.starts = []. Calling bisect_left([], 2) returns 0, and bisect_right([], 6) returns 0.

2. Step 2: Update intervals and starts

   Since i == 0, the first if condition is skipped. Also, j == 0, so second if is skipped. No intervals to delete. Insert left=2 at self.starts[0:0], so self.starts = [2]. Interval stored as {2:6}.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Starts list after first addRange is [2] [OK]

Hint: Bisect on empty list returns 0, so starts list gets single element [OK]

Common Mistakes:

• Assuming right endpoint is also inserted in starts list

3. Given the following Python code for merging two skylines, and the inputs left = [[1, 3], [5, 0]] and right = [[2, 4], [6, 0]], what is the merged skyline returned by mergeSkylines(left, right)?

easy

A. [[1, 3], [2, 4], [5, 0], [6, 0]]

B. [[1, 3], [5, 0], [6, 0]]

C. [[1, 3], [2, 4], [4, 0], [6, 0]]

D. [[1, 3], [2, 4], [4, 0], [5, 0], [6, 0]]

Solution

1. Step 1: Trace first iterations of the merge loop

   Compare left[0]=(1,3) and right[0]=(2,4): 1 < 2, so x=1, h1=3, h2=0, max_h=3 -> merged=[[1,3]]

2. Step 2: Next iterations and final merge

   Next left[1]=(5,0), right[0]=(2,4): 2 < 5, x=2, h2=4, h1=3, max_h=4 -> merged=[[1,3],[2,4]]; then right[1]=(6,0) vs left[1]=(5,0): 5 < 6, x=5, h1=0, h2=4, max_h=4 (no change), then x=6, h2=0, max_h=0 -> merged=[[1,3],[2,4],[4,0],[5,0],[6,0]] after extending remaining points.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Stepwise max height updates match merged skyline [OK]

Hint: Track h1 and h2 updates carefully during merge [OK]

Common Mistakes:

• Off-by-one in indices
• Missing key points when heights change

4. What is the time complexity of adding a number and then finding the median using the balanced two heaps approach with lazy deletion for a data stream of size n?

medium

A. O(log n) per addNum and O(log n) per findMedian

B. O(n) per addNum and O(1) per findMedian

C. O(log n) per addNum and O(1) per findMedian

D. O(1) per addNum and O(n) per findMedian

Solution

1. Step 1: Analyze addNum complexity

   Adding a number involves pushing to a heap and balancing heaps, each O(log n) operations.

2. Step 2: Analyze findMedian complexity

   Median is retrieved from the top of heaps without modification, O(1) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Insertion is O(log n), median retrieval O(1) [OK]

Hint: Heap push/pop are O(log n), median peek is O(1) [OK]

Common Mistakes:

• Assuming sorting each query is O(log n)
• Confusing addNum with findMedian complexity

5. Suppose the AllOne data structure is extended to allow keys to be reused after removal (i.e., keys can be reinserted after their count reaches zero). Which modification is necessary to maintain O(1) operations and correctness?

hard

A. Do nothing special; existing code handles reuse correctly

B. Maintain a separate reuse queue to track keys that can be reinserted

C. Reset key's count to zero and keep it in the data structure to track reuse

D. Ensure keys are fully removed from all buckets and mappings upon count zero, then treat reuse as new insertion

Solution

1. Step 1: Understand reuse implications

   Keys removed at count zero must be fully deleted to avoid stale references.

2. Step 2: Ensure reuse is treated as new insertion

   On reuse, key is inserted fresh with count 1, requiring clean removal previously.

3. Step 3: Confirm O(1) operations

   Full removal and fresh insertion maintain O(1) updates and correctness.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Proper removal prevents duplicates and stale buckets [OK]

Hint: Full removal before reuse ensures correctness and O(1) ops [OK]

Common Mistakes:

• Keeping keys with zero count in data structure causes bugs