Insert Interval into Sorted List in DSA Rust - 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

↓

Adjust pointers

↓

Done

We create a new interval node, traverse the sorted list to find the right place, merge overlapping intervals if needed, or insert the new interval in order, adjusting pointers accordingly.

Execution Sample

DSA Rust

struct Interval {
    start: i32,
    end: i32,
    next: Option<Box<Interval>>,
}

fn insert_interval(head: Option<Box<Interval>>, new: Interval) -> Option<Box<Interval>>

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, 8]	None	new = [4,8]	[1,3] -> [6,9] -> [12,15] -> null
2	Start at head [1,3]	[1,3]	current = head	[1,3] -> [6,9] -> [12,15] -> null
3	Check if current.end < new.start (3 < 4)	[1,3]	Move prev = current, current = current.next	[1,3] -> [6,9] -> [12,15] -> null
4	Now current = [6,9], check overlap with new [4,8]	[6,9]	Overlap detected (6 <= 8)	[1,3] -> [6,9] -> [12,15] -> null
5	Merge new with current: new.start = min(4,6)=4, new.end = max(8,9)=9	[6,9]	new = [4,9]	[1,3] -> [6,9] -> [12,15] -> null
6	Remove current [6,9] from list, link prev.next to current.next	[6,9]	prev.next = [12,15]	[1,3] -> [12,15] -> null
7	Set current = prev.next = [12,15], check overlap with new [4,9]	[12,15]	No overlap (12 > 9), stop merging	[1,3] -> [12,15] -> null
8	Insert new [4,9] after prev [1,3]	Insert between [1,3] and [12,15]	prev.next = new, new.next = current	[1,3] -> [4,9] -> [12,15] -> null
9	Return updated list head	Head = [1,3]	No pointer change	[1,3] -> [4,9] -> [12,15] -> null

💡 No more overlaps; new interval inserted in correct position.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 6	After Step 7	Final
current	[1,3]	[6,9]	[6,9]	[12,15]	[12,15]	[12,15]
prev	None	[1,3]	[1,3]	[1,3]	[1,3]	[1,3]
new	[4,8]	[4,8]	[4,9]	[4,9]	[4,9]	[4,9]
list	[1,3]->[6,9]->[12,15]	[1,3]->[6,9]->[12,15]	[1,3]->[6,9]->[12,15]	[1,3]->[12,15]	[1,3]->[12,15]	[1,3]->[4,9]->[12,15]

Key Moments - 3 Insights

Why do we move 'prev' and 'current' pointers when current.end < new.start?

Because intervals before the new one do not overlap, we move forward to find where to insert or merge. See execution_table step 3 where current moves from [1,3] to [6,9].

How do we merge overlapping intervals?

We update the new interval's start to the minimum start and end to the maximum end of overlapping intervals, removing the old nodes. See steps 5 and 6 where new becomes [4,9] and [6,9] is removed.

Why do we stop merging when current.start > new.end?

Because intervals are sorted, no further overlaps can occur beyond this point. See step 7 where current is [12,15] and no overlap with new [4,9] is found.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the new interval's range after merging?

A [4,8]

B [6,9]

C [4,9]

D [1,3]

💡 Hint

Check the 'Operation' and 'Pointer Changes' columns at step 5 in execution_table.

At which step does the list remove the overlapping node [6,9]?

A Step 6

B Step 4

C Step 5

D Step 7

💡 Hint

Look for 'Remove current [6,9]' in the 'Operation' column of execution_table.

If the new interval was [10,11], at which step would the insertion happen?

A After step 6

B After step 7

C After step 3

D After step 8

💡 Hint

Refer to step 7 where current is [12,15] and no overlap occurs; insertion happens before current.

Concept Snapshot

Insert Interval into Sorted List:
- Traverse list while current.end < new.start
- Merge overlapping intervals by updating new.start and new.end
- Remove merged nodes by adjusting pointers
- Insert new interval in correct position
- Return updated list head

Full Transcript

This concept shows how to insert a new interval into a sorted linked list of intervals. We start by creating the new interval node. Then, we traverse the list to find where the new interval fits. If intervals overlap, we merge them by updating the new interval's start and end to cover all overlaps. We remove merged nodes by adjusting pointers. When no more overlaps exist, we insert the new interval in the correct position and return the updated list head. The execution table tracks each step, showing pointer changes and the list's visual state. Key moments clarify why pointers move and how merging works. The visual quiz tests understanding of these steps.

Practice

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

easy

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

B. To replace all intervals with the new interval

C. To sort the intervals in descending order

D. To add the new interval and merge any overlapping intervals

Solution

1. Step 1: Understand the problem context

   We have a sorted list of intervals and want to insert a new interval without breaking the order.

2. Step 2: Identify the required operation

   We must insert the new interval and merge any intervals that overlap with it to keep the list sorted and non-overlapping.

3. Final Answer:

   To add the new interval and merge any overlapping intervals -> Option D

4. Quick Check:

   Insert and merge intervals = To add the new interval and merge any overlapping intervals [OK]

Hint: Insert and merge overlapping intervals to keep list sorted [OK]

Common Mistakes:

• Replacing all intervals instead of merging
• Sorting intervals in descending order
• Removing intervals before the new one

2. Which Rust syntax correctly declares a vector of intervals where each interval is a tuple of two integers?

easy

A. let intervals: Vec<(i32, i32)> = vec![(1, 3), (6, 9)];

B. let intervals = [(1, 3), (6, 9)];

C. let intervals: Vec<[i32; 2]> = vec![[1, 3], [6, 9]];

D. let intervals: Vec<(int, int)> = vec![(1, 3), (6, 9)];

Solution

1. Step 1: Identify correct Rust tuple and vector syntax

   Rust uses (i32, i32) for tuple of two integers and Vec for vector type.

2. Step 2: Check each option

   let intervals: Vec<(i32, i32)> = vec![(1, 3), (6, 9)]; uses Vec<(i32, i32)> with vec! macro and tuples correctly. let intervals = [(1, 3), (6, 9)]; is an array, not a vector. let intervals: Vec<[i32; 2]> = vec![[1, 3], [6, 9]]; uses arrays inside vector, which is valid but different type. let intervals: Vec<(int, int)> = vec![(1, 3), (6, 9)]; uses 'int' which is invalid in Rust.

3. Final Answer:

   let intervals: Vec<(i32, i32)> = vec![(1, 3), (6, 9)]; -> Option A

4. Quick Check:

   Correct Rust tuple vector syntax = let intervals: Vec<(i32, i32)> = vec![(1, 3), (6, 9)]; [OK]

Hint: Use Vec<(i32, i32)> and vec! macro for interval list [OK]

Common Mistakes:

• Using 'int' instead of 'i32'
• Confusing arrays and tuples
• Not using vec! macro for vectors

3. Given the intervals vec![(1, 3), (6, 9)] and a new interval (2, 5), what is the resulting list after insertion 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: Insert new interval and find overlaps

   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 without sorting
• Merging all intervals incorrectly

4. Consider this Rust code snippet for inserting an interval into a sorted list:

fn insert_interval(intervals: &mut Vec<(i32, i32)>, new_interval: (i32, i32)) {
    let mut i = 0;
    while i < intervals.len() {
        if intervals[i].1 < new_interval.0 {
            i += 1;
        } else if intervals[i].0 > new_interval.1 {
            intervals.insert(i, new_interval);
            return;
        } else {
            intervals[i].0 = intervals[i].0.min(new_interval.0);
            intervals[i].1 = intervals[i].1.max(new_interval.1);
            intervals.remove(i + 1);
        }
    }
    intervals.push(new_interval);
}

What is the main bug in this code?

medium

A. It never increments index i inside the else block causing infinite loop

B. It inserts the new interval at the wrong position

C. It removes the wrong interval when merging overlapping intervals

D. It does not handle empty intervals vector

Solution

1. Step 1: Examine the else branch for merging

   The code updates intervals[i] by merging the new interval but never increments the index i inside the else block.

2. Step 2: Identify infinite loop cause

   Because i is not incremented after merging and removing intervals[i+1], the loop can get stuck processing the same index repeatedly, causing an infinite loop.

3. Final Answer:

   It never increments index i inside the else block causing infinite loop -> Option A

4. Quick Check:

   Missing i increment in else block = infinite loop [OK]

Hint: Always increment index after merging to avoid infinite loop [OK]

Common Mistakes:

• Forgetting to increment index after removal
• Assuming insert always works without checks
• Ignoring empty vector edge case

5. You have a sorted list of intervals vec![(1, 2), (3, 5), (6, 7), (8, 10), (12, 16)]. Insert the new interval (4, 8) and return the updated list after merging all overlapping intervals.

hard

A. [(1, 2), (3, 16)]

B. [(1, 2), (3, 10), (12, 16)]

C. [(1, 2), (4, 8), (12, 16)]

D. [(1, 2), (3, 5), (6, 8), (8, 10), (12, 16)]

Solution

1. Step 1: Identify intervals overlapping with (4, 8)

   Intervals (3, 5), (6, 7), and (8, 10) overlap with (4, 8) because their ranges intersect.

2. Step 2: Merge all overlapping intervals

   Merge (3, 5), (6, 7), (8, 10), and (4, 8) into one interval (3, 10). The intervals (1, 2) and (12, 16) remain unchanged.

3. Final Answer:

   [(1, 2), (3, 10), (12, 16)] -> Option B

4. Quick Check:

   Merged intervals after insertion = [(1, 2), (3, 10), (12, 16)] [OK]

Hint: Merge all intervals overlapping new interval's range [OK]

Common Mistakes:

• Merging only partially overlapping intervals
• Not merging intervals that touch at boundaries
• Replacing intervals incorrectly