Flatten a Multilevel Doubly Linked List

▶

Steps

setup

Initialize traversal at head node 1

Start with the head node (value 1). The current pointer is set to node 1, and the stack shows the traversal starting point.

💡 Initialization sets the starting point for flattening, making clear where the algorithm begins.

Line:

curr = head

💡 The algorithm begins traversal from the head node, preparing to scan for child pointers.

traverse

Move to node 2 (no child)

Move the current pointer from node 1 to node 2. Node 2 has no child, so no splicing occurs.

💡 Each move forward checks for children; no child means simple traversal.

Line:

curr = curr.next

💡 Traversal advances linearly when no child is present.

traverse

Move to node 3 (child detected)

Current pointer moves to node 3, which has a child pointer to node 7. The algorithm prepares to flatten this child list.

💡 Detecting a child triggers the flattening process at this node.

Line:

if curr.child:

💡 Child pointers indicate sublists that must be integrated into the main list.

expand

Find tail of child list starting at node 7

Traverse the child list starting at node 7 to find its tail node (node 10). This tail will be connected to node 4.

💡 Finding the tail is essential to reconnect the flattened child list back to the main list.

Line:

tail = child
while tail.next:
    tail = tail.next

💡 The tail node marks where the child list ends and where to reconnect the main list.

insert

Connect tail node 10 to node 4

Connect the tail of the child list (node 10) to node 4, preserving the original next nodes after node 3.

💡 This connection ensures the flattened child list links back to the main list seamlessly.

Line:

if curr.next:
    tail.next = curr.next
    curr.next.prev = tail

💡 Re-linking the tail to the next node maintains list continuity after splicing.

insert

Splice child list starting at node 7 after node 3

Set node 3's next pointer to its child (node 7) and update child's prev pointer to node 3, effectively splicing the child list in.

💡 Splicing inserts the entire child list directly after the current node.

Line:

curr.next = child
child.prev = curr
curr.child = None

💡 Removing the child pointer after splicing prevents reprocessing and marks the list as flattened at this node.

traverse

Move to node 7 (child of node 3)

Traverse into the newly spliced child list starting at node 7, which has no child pointer itself.

💡 Traversal continues into the child list to check for further children.

Line:

curr = curr.next

💡 The algorithm handles nested children by continuing traversal into spliced lists.

traverse

Move to node 8 (child detected)

At node 8, detect a child pointer to node 11, triggering flattening of this nested child list.

💡 Nested children require the same flattening steps recursively.

Line:

if curr.child:

💡 The algorithm handles multiple levels by repeating the flattening process.

expand

Find tail of nested child list starting at node 11

Traverse the nested child list starting at node 11 to find its tail node (node 12).

💡 Finding the tail allows reconnecting the nested child list back to node 9.

Line:

tail = child
while tail.next:
    tail = tail.next

💡 Tail node marks the end of the nested child list for reconnection.

insert

Connect tail node 12 to node 9

Connect the tail of the nested child list (node 12) to node 9, preserving the original next nodes after node 8.

💡 This connection maintains list continuity after splicing the nested child list.

Line:

if curr.next:
    tail.next = curr.next
    curr.next.prev = tail

💡 Re-linking the tail to the next node maintains list continuity after splicing nested children.

insert

Splice nested child list starting at node 11 after node 8

Set node 8's next pointer to its child (node 11) and update child's prev pointer to node 8, splicing the nested child list in.

💡 Splicing inserts the nested child list directly after node 8.

Line:

curr.next = child
child.prev = curr
curr.child = None

💡 Removing the child pointer after splicing prevents reprocessing nested children.

traverse

Traverse nodes 11 and 12 (no children)

Move through nodes 11 and 12 sequentially; neither has children, so traversal continues linearly.

💡 Nodes without children are traversed without modification.

Line:

curr = curr.next

💡 Traversal proceeds through flattened child lists smoothly.

traverse

Move to node 12

Advance current pointer to node 12, continuing traversal through the flattened nested child list.

💡 Traversal continues until the end of the nested child list.

Line:

curr = curr.next

💡 Traversal moves forward through all nodes in the flattened list.

traverse

Move to node 9 (continuing after nested child list)

After finishing nested child list, move to node 9, which has no child pointer.

💡 Traversal resumes at the node following the spliced nested child list.

Line:

curr = curr.next

💡 Flattening preserves original next nodes after child lists.

traverse

Move to node 10 (no child)

Traverse to node 10, the tail of the first child list, which has no child pointer.

💡 Traversal continues linearly through the flattened child list.

Line:

curr = curr.next

💡 Traversal covers all nodes in the spliced child list.

traverse

Move to node 4 (continue main list after child)

After finishing the child list, move to node 4, continuing traversal on the main list.

💡 Traversal resumes on the main list after splicing child lists.

Line:

curr = curr.next

💡 Flattening preserves the original order after child lists.

traverse

Traverse nodes 5 and 6 (no children)

Traverse nodes 5 and 6 sequentially; neither has children, so traversal continues to the end.

💡 Traversal completes the main list after flattening all children.

Line:

curr = curr.next

💡 Traversal finishes at the end of the flattened list.

traverse

Move to node 6 (end of list)

Move to node 6, the last node in the list, which has no child pointer.

💡 Traversal reaches the end of the list.

Line:

curr = curr.next

💡 Traversal ends when current pointer becomes null after last node.

reconstruct

Traversal complete, return flattened list head

Current pointer is now null, indicating traversal and flattening are complete. Return the head node as the flattened list.

💡 Returning the head provides access to the fully flattened list.

Line:

return head

💡 The algorithm completes with a fully flattened list accessible from the original head.

class Node:
    def __init__(self, val, prev=None, next=None, child=None):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child

def flatten(head):
    curr = head  # STEP 1: Initialize traversal
    while curr:
        if curr.child:  # STEP 3,8: Child detected
            child = curr.child
            tail = child
            while tail.next:  # STEP 4,9: Find tail of child list
                tail = tail.next
            if curr.next:  # STEP 5,10: Connect tail to curr.next
                tail.next = curr.next
                curr.next.prev = tail
            curr.next = child  # STEP 6,11: Splice child list
            child.prev = curr
            curr.child = None
        curr = curr.next  # STEP 2,7,12-18: Move to next node
    return head  # STEP 19: Return flattened list head

📊

Flatten a Multilevel Doubly Linked List - Watch the Algorithm Execute, Step by Step

Watching each pointer update and child list integration step-by-step reveals how the algorithm maintains list integrity while flattening, which is hard to grasp from code alone.

no_opElement[0]: 1

Stack (top→bottom)

1

no_opElement[1]: 2

Stack (top→bottom)

2

1

peekElement[2]: 3

Stack (top→bottom)

3

2

1

no_opElement[2]: 3

Stack (top→bottom)

3

2

1

Contributes: "Tail found at node 10"

no_opElement[2]: 3

Stack (top→bottom)

3

2

1

Contributes: "Tail node 10 connected to node 4"

pushElement[2]: 3

Stack (top→bottom)

7

3

2

1

↑ pushed: 7

Contributes: "Child list spliced after node 3"

no_opElement[3]: 7

Stack (top→bottom)

7

3

2

1

peekElement[4]: 8

Stack (top→bottom)

8

7

3

2

1

no_opElement[4]: 8

Stack (top→bottom)

8

7

3

2

1

Contributes: "Tail found at node 12"

no_opElement[4]: 8

Stack (top→bottom)

8

7

3

2

1

Contributes: "Tail node 12 connected to node 9"

pushElement[4]: 8

Stack (top→bottom)

11

8

7

3

2

1

↑ pushed: 11

Contributes: "Nested child list spliced after node 8"

no_opElement[5]: 11

Stack (top→bottom)

11

8

7

3

2

1

no_opElement[6]: 12

Stack (top→bottom)

12

11

8

7

3

2

1

no_opElement[7]: 9

Stack (top→bottom)

9

12

11

8

7

3

2

1

no_opElement[8]: 10

Stack (top→bottom)

10

9

12

11

8

7

3

2

1

no_opElement[9]: 4

Stack (top→bottom)

4

10

9

12

11

8

7

3

2

1

no_opElement[10]: 5

Stack (top→bottom)

5

4

10

9

12

11

8

7

3

2

1

no_opElement[11]: 6

Stack (top→bottom)

6

5

4

10

9

12

11

8

7

3

2

1

no_op

Stack (top→bottom)

6

5

4

10

9

12

11

8

7

3

2

1

Contributes: "Flattened list head returned"

Key Takeaways

✓ Flattening is done in-place by splicing child lists directly into the main list without extra memory.

This insight is hard to see from code alone because pointer updates are subtle and interdependent.

✓ Finding the tail of the child list before splicing is crucial to reconnect the flattened list correctly.

Visualizing the tail traversal clarifies why this step is necessary to avoid losing nodes.

✓ Child pointers are removed immediately after splicing to prevent reprocessing and mark progress.

Seeing the child pointer cleared in the trace shows how the algorithm avoids infinite loops.

Practice

1. You need to design a cache that evicts the least frequently used item when full, and among items with the same frequency, evicts the least recently used one. Which approach guarantees O(1) average time complexity for both get and put operations?

easy

A. Using a simple hash map with frequency counts and sorting keys on each eviction

B. Maintaining a frequency map of doubly linked lists to track keys by frequency and recency

C. Using a min-heap keyed by frequency and timestamp to evict the least frequently used item

D. Using a single doubly linked list ordered by frequency and recency

Solution

1. Step 1: Understand the eviction criteria

   The cache must evict the least frequently used key, and if multiple keys share the same frequency, evict the least recently used among them.

2. Step 2: Identify data structures supporting O(1) operations

   A frequency map with doubly linked lists allows grouping keys by frequency and maintaining recency order within each frequency group, enabling O(1) updates and eviction.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Frequency map + doubly linked lists is the classic LFU O(1) approach [OK]

Hint: Frequency map + doubly linked lists enable O(1) LFU cache [OK]

Common Mistakes:

• Using sorting on eviction is too slow
• Min-heap adds O(log n) overhead
• Single list can't maintain frequency and recency efficiently

2. Consider the following Python code implementing an LRU Cache with capacity 2. After executing the sequence of operations below, what is the return value of cache.get(1)?

cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
cache.get(1)
cache.put(3, 3)
cache.get(2)
cache.put(4, 4)
cache.get(1)
cache.get(3)
cache.get(4)

easy

A. 1

B. 3

C. -1

D. 4

Solution

1. Step 1: Trace cache state after each operation

   After put(1,1) and put(2,2), cache has keys [2 (MRU), 1 (LRU)]. get(1) moves key 1 to MRU, order: [1,2]. put(3,3) evicts LRU key 2, cache: [3,1]. get(2) returns -1 (evicted). put(4,4) evicts LRU key 1, cache: [4,3].

2. Step 2: Evaluate get(1) after put(4,4)

   Key 1 was evicted, so get(1) returns -1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Key 1 evicted after put(4,4), so get(1) -> -1 [OK]

Hint: Remember to update usage order on get and evict LRU on put [OK]

Common Mistakes:

• Forgetting to move accessed node to front
• Evicting wrong node
• Returning wrong value after eviction

3. 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

4. What is the time complexity of performing n operations (push, pop, increment) on the optimal CustomStack implementation that uses a lazy increment array?

medium

A. O(n * k), where k is the increment size

B. O(n + k), where k is the maximum increment size

C. O(n log n), due to increment propagation

D. O(n), total for all operations combined

Solution

1. Step 1: Analyze push and pop operations

   Each push and pop is O(1) amortized, as they add or remove one element.

2. Step 2: Analyze increment operation

   Increment only updates inc array at one index, O(1) per call. Propagation happens lazily during pop, each element's increment propagated once.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   All n operations combined run in O(n) total time [OK]

Hint: Lazy increments make all operations O(1) amortized, total O(n) [OK]

Common Mistakes:

• Assuming increment is O(k) per call
• Confusing total time with per-operation time

5. What is the time complexity of the divide and conquer approach to the Skyline Problem when given n buildings? Assume merging two skylines of total length m takes O(m) time.

medium

A. O(n²)

B. O(n)

C. O(n log n)

D. O(n * w) where w is the width of the skyline

Solution

1. Step 1: Identify divide and conquer recurrence

   The algorithm splits buildings into halves recursively, then merges skylines in O(m) time where m is proportional to n.

2. Step 2: Solve recurrence and analyze merge cost

   Recurrence is T(n) = 2T(n/2) + O(n), which solves to O(n log n). The width w does not affect complexity here.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Divide and conquer with linear merge per level -> O(n log n) [OK]

Hint: Divide and conquer recurrence T(n)=2T(n/2)+O(n) -> O(n log n) [OK]

Common Mistakes:

• Confusing width w with n
• Assuming quadratic due to nested loops