Insert Interval into Sorted List in DSA C# - Execution Trace

Concept Flow - Insert Interval into Sorted List

Create new interval node

↓

Start at head of sorted list

↓

Traverse nodes while current.end < new.start

↓

Check overlap with current node

↓

Merge intervals

↓

Update pointers

↓

Done

Create the new interval node, traverse the sorted list to find the correct position, merge overlapping intervals if needed, or insert the new interval in order, then update pointers.

Execution Sample

DSA C#

ListNode InsertInterval(ListNode head, Interval newInterval) {
  // Traverse to find insert position
  // Merge overlapping intervals
  // Insert or merge
  return head;
}

This code inserts a new interval into a sorted linked list of intervals, merging overlaps.

Execution Table

Step	Operation	Current Node	Pointer Changes	Visual State
1	Create new interval [4,6]	N/A	newNode = [4,6]	[1,3] -> [5,7] -> [8,10] -> null newNode = [4,6]
2	Start at head [1,3]	[1,3]	current = head	[1,3] -> [5,7] -> [8,10] -> null
3	Check if current.end < new.start (3 < 4)	[1,3]	Move prev = current, current = current.next	prev = [1,3] current = [5,7] List unchanged
4	Check if current.end < new.start (7 < 4) false	[5,7]	Stop traversal	prev = [1,3] current = [5,7]
5	Check overlap: new.start <= current.end (4 <= 7) true	[5,7]	Merge intervals: new.start = min(4,5)=4, new.end = max(6,7)=7	newNode = [4,7] List unchanged
6	Check next node [8,10] for overlap with newNode [4,7]	[8,10]	No overlap (8 > 7), stop merging	newNode = [4,7]
7	Link prev.next to newNode	prev = [1,3]	prev.next = newNode	[1,3] -> [4,7]
8	Link newNode.next to current.next ([8,10])	newNode = [4,7]	newNode.next = [8,10]	[1,3] -> [4,7] -> [8,10] -> null
9	Remove merged nodes between newNode and current.next (current was [5,7])	N/A	Garbage collect [5,7]	[1,3] -> [4,7] -> [8,10] -> null
10	Return head	N/A	N/A	[1,3] -> [4,7] -> [8,10] -> null

💡 Traversal stops when current.end >= new.start; merging done; new interval inserted and list updated.

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 5	After Step 7	Final
current	[1,3]	[5,7]	[5,7]	[5,7]	[5,7]	[5,7]
prev	null	[1,3]	[1,3]	[1,3]	[1,3]	[1,3]
newNode	N/A	N/A	N/A	[4,7]	[4,7]	[4,7]
head	[1,3]	[1,3]	[1,3]	[1,3]	[1,3]	[1,3]

Key Moments - 3 Insights

Why do we move 'prev' and 'current' pointers during traversal?

We move 'prev' and 'current' to find the correct position to insert or merge the new interval. 'prev' tracks the node before 'current' so we can update pointers correctly (see execution_table steps 3 and 4).

Why do we merge intervals instead of just inserting the new one?

If the new interval overlaps with existing intervals, merging prevents duplicates and keeps the list sorted with non-overlapping intervals (see step 5 where newNode merges with [5,7]).

What happens to the old nodes that are merged?

The merged nodes are removed by updating pointers to skip them, and they become unreachable for garbage collection (see step 9).

Visual Quiz - 3 Questions

Look at the execution_table, what is the 'newNode' interval after step 5?

A [4,6]

B [4,7]

C [5,7]

D [1,3]

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 5 where merging happens.

At which step does the traversal stop because current.end >= new.start?

A Step 3

B Step 4

C Step 6

D Step 7

💡 Hint

Look at the 'Operation' and 'Current Node' columns to see when traversal stops.

If the new interval was [2,4], how would the pointer 'prev' change after traversal?

A prev would be null

B prev would be [1,3]

C prev would be [5,7]

D prev would be [8,10]

💡 Hint

Refer to variable_tracker and execution_table steps 2 and 3 for pointer movement logic.

Concept Snapshot

Insert Interval into Sorted List:
- Traverse list with 'prev' and 'current' to find insert position
- Merge overlapping intervals by adjusting new interval boundaries
- Update pointers: prev.next = newNode, newNode.next = current.next
- Remove merged nodes by skipping them
- Return head of updated list

Full Transcript

This visualization shows how to insert a new interval into a sorted linked list of intervals. We start by creating a new node for the interval. Then we traverse the list with two pointers: 'prev' and 'current'. We move forward while the current interval ends before the new interval starts. When we find overlap, we merge intervals by updating the new interval's start and end. We continue merging if needed. Then we update pointers to insert the merged interval into the list, skipping merged nodes. Finally, we return the head of the updated list. This keeps the list sorted and non-overlapping.

Practice

1. What is the main goal when inserting a new interval into a sorted list of non-overlapping intervals?

easy

A. To sort the intervals again after insertion without merging

B. To add the new interval at the end without checking overlaps

C. To remove all intervals that come before the new interval

D. To merge overlapping intervals and keep the list sorted without overlaps

Solution

1. Step 1: Understand the problem context

   The list contains sorted, non-overlapping intervals. Inserting a new interval may cause overlaps.

2. Step 2: Identify the required action

   We must merge any overlapping intervals with the new one and keep the list sorted without overlaps.

3. Final Answer:

   To merge overlapping intervals and keep the list sorted without overlaps -> Option D

4. Quick Check:

   Insert and merge intervals = To merge overlapping intervals and keep the list sorted without overlaps [OK]

Hint: Merge overlapping intervals to keep list sorted and non-overlapping [OK]

Common Mistakes:

• Inserting without merging overlaps
• Appending without sorting
• Removing unrelated intervals

2. Which of the following C# code snippets correctly declares a list of intervals as List intervals?

easy

A. var intervals = new List { [1, 3], [6, 9] };

B. var intervals = new List { new int[] {1, 3}, new int[] {6, 9} };

C. List intervals = new List { (1, 3), (6, 9) };

D. List<int> intervals = new List<int> { {1, 3}, {6, 9} };

Solution

1. Step 1: Check correct syntax for List of int arrays

   List requires elements as int arrays, declared with new int[] {start, end}.

2. Step 2: Validate each option

   var intervals = new List { new int[] {1, 3}, new int[] {6, 9} }; uses new int[] correctly; others use invalid syntax like braces or tuples.

3. Final Answer:

   var intervals = new List { new int[] {1, 3}, new int[] {6, 9} }; -> Option B

4. Quick Check:

   List of int arrays syntax = var intervals = new List { new int[] {1, 3}, new int[] {6, 9} }; [OK]

Hint: Use new int[] {start, end} inside List initialization [OK]

Common Mistakes:

• Using curly braces instead of new int[]
• Using tuples instead of arrays
• Incorrect variable type declaration

3. Given the intervals [[1, 3], [6, 9]] and a new interval [2, 5], what is the resulting list after inserting and merging?

medium

A. [[2, 5], [6, 9]]

B. [[1, 3], [2, 5], [6, 9]]

C. [[1, 5], [6, 9]]

D. [[1, 9]]

Solution

1. Step 1: Identify overlapping intervals

   The new interval [2, 5] overlaps with [1, 3] because 2 ≤ 3.

2. Step 2: Merge overlapping intervals

   Merge [1, 3] and [2, 5] into [1, 5]. The interval [6, 9] remains unchanged.

3. Final Answer:

   [[1, 5], [6, 9]] -> Option C

4. Quick Check:

   Merged intervals = [[1, 5], [6, 9]] [OK]

Hint: Merge intervals if new start ≤ existing end [OK]

Common Mistakes:

• Not merging overlapping intervals
• Inserting new interval without merging
• Merging all intervals incorrectly

4. Consider this C# code snippet to insert an interval into a sorted list. What is the bug?

var intervals = new List { new int[] {1, 2}, new int[] {3, 5} };
var newInterval = new int[] {4, 7};

foreach(var interval in intervals) {
    if(interval[1] >= newInterval[0]) {
        interval[1] = Math.Max(interval[1], newInterval[1]);
        break;
    }
}

medium

A. It modifies only the first overlapping interval but misses merging subsequent overlaps

B. It throws a runtime exception due to invalid index access

C. It inserts the new interval at the wrong position

D. It does not check for any overlaps before merging

Solution

1. Step 1: Analyze the loop behavior

   The loop breaks after merging with the first overlapping interval, ignoring others.

2. Step 2: Identify the bug impact

   Intervals after the first overlap are not merged, causing incorrect final intervals.

3. Final Answer:

   It modifies only the first overlapping interval but misses merging subsequent overlaps -> Option A

4. Quick Check:

   Loop breaks early, missing merges = It modifies only the first overlapping interval but misses merging subsequent overlaps [OK]

Hint: Do not break loop early; merge all overlapping intervals [OK]

Common Mistakes:

• Breaking loop too soon
• Not merging all overlaps
• Assuming single overlap only

5. You have intervals [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]] and a new interval [4, 8]. After inserting and merging, what is the final list?

hard

A. [[1, 2], [3, 10], [12, 16]]

B. [[1, 2], [4, 8], [12, 16]]

C. [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]]

D. [[1, 2], [3, 8], [12, 16]]

Solution

1. Step 1: Find intervals overlapping with [4, 8]

   Intervals [3, 5], [6, 7], and [8, 10] overlap with [4, 8].

2. Step 2: Merge all overlapping intervals

   Merge [3, 5], [6, 7], [8, 10], and [4, 8] into [3, 10].

3. Step 3: Keep non-overlapping intervals unchanged

   Intervals [1, 2] and [12, 16] remain as is.

4. Final Answer:

   [[1, 2], [3, 10], [12, 16]] -> Option A

5. Quick Check:

   Merged overlapping intervals correctly = [[1, 2], [3, 10], [12, 16]] [OK]

Hint: Merge all intervals overlapping new interval into one [OK]

Common Mistakes:

• Merging only some overlapping intervals
• Not merging intervals that touch at boundaries
• Replacing intervals instead of merging