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

↓

Merge intervals

↓

Adjust pointers

↓

Continue merging if needed

↓

Finish insertion

Start from head, move until intervals end before new start, then merge overlapping intervals or insert new interval, adjusting pointers accordingly.

Execution Sample

DSA Go

type Interval struct {
  start, end int
  next *Interval
}

func insertInterval(head *Interval, newInterval *Interval) *Interval {
  // Insert newInterval into sorted linked list of intervals
}

Insert a new interval into a sorted linked list of intervals, merging overlaps.

Execution Table

Step	Operation	Current Node	Pointer Changes	Visual State
1	Start at head	Interval(1,3)	None	1->3 -> 6->9 -> 12->16 -> null
2	Check if current.end < new.start (3 < 4)	Interval(1,3)	None	1->3 -> 6->9 -> 12->16 -> null
3	Move to next node	Interval(6,9)	None	1->3 -> 6->9 -> 12->16 -> null
4	Check if current.end < new.start (9 < 4)	Interval(6,9)	No	1->3 -> 6->9 -> 12->16 -> null
5	Check overlap with new interval (4,10)	Interval(6,9)	Merge intervals: new.start = min(4,6)=4, new.end = max(10,9)=10	1->3 -> 6->9 -> 12->16 -> null
6	Move to next node to check further overlap	Interval(12,16)	None	1->3 -> 6->9 -> 12->16 -> null
7	Check overlap with current (12 <= 10)?	Interval(12,16)	No	1->3 -> 6->9 -> 12->16 -> null
8	Insert merged interval before current	Interval(12,16)	Set previous.next = newInterval, newInterval.next = current	1->3 -> 4->10 -> 12->16 -> null
9	Finish insertion	null	None	1->3 -> 4->10 -> 12->16 -> null

💡 Reached end of overlapping intervals, inserted merged interval, no more merges needed.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 8	Final
current	Interval(1,3)	Interval(1,3)	Interval(6,9)	Interval(12,16)	null
newInterval	Interval(4,10)	Interval(4,10)	Interval(4,10)	Interval(4,10)	Interval(4,10)
previous	null	Interval(1,3)	Interval(1,3)	Interval(1,3)	Interval(1,3)
list	1->3 -> 6->9 -> 12->16 -> null	1->3 -> 6->9 -> 12->16 -> null	1->3 -> 6->9 -> 12->16 -> null	1->3 -> 4->10 -> 12->16 -> null	1->3 -> 4->10 -> 12->16 -> null

Key Moments - 3 Insights

Why do we move the 'current' pointer forward only when current.end < new.start?

Because intervals before new.start do not overlap and should be skipped. This is shown in execution_table rows 2 and 3 where we move forward until we find potential overlap.

How do we merge overlapping intervals?

We update newInterval's start to the minimum of both starts and end to the maximum of both ends, as in step 5. This merges the current interval with newInterval.

Why do we insert the merged interval before the first non-overlapping interval?

Because the list is sorted, and after merging all overlaps, the merged interval fits before the first interval that starts after it, as shown in step 8.

Visual Quiz - 3 Questions

Look at the execution_table, what is the 'current' node at step 4?

A Interval(12,16)

B Interval(1,3)

C Interval(6,9)

D null

💡 Hint

Check the 'Current Node' column at step 4 in the execution_table.

At which step does the newInterval get merged with an existing interval?

A Step 3

B Step 5

C Step 7

D Step 8

💡 Hint

Look for the step where 'Merge intervals' happens in the 'Operation' column.

If the newInterval was (10,11), at which step would the insertion happen?

A After step 7

B After step 2

C After step 4

D After step 9

💡 Hint

Consider when the newInterval does not overlap and must be inserted before the first interval starting after it.

Concept Snapshot

Insert Interval into Sorted List:
- Traverse list while current.end < new.start
- Merge overlapping intervals by updating newInterval
- Insert merged/new interval before first non-overlapping node
- Adjust pointers to maintain list integrity
- Result: sorted, merged intervals list

Full Transcript

This visualization shows how to insert a new interval into a sorted linked list of intervals. We start at the head and move forward while the current interval ends before the new interval starts. When we find overlapping intervals, we merge them by updating the new interval's start and end to cover all overlaps. After merging, we insert the new merged interval before the first interval that does not overlap. Pointers are adjusted to keep the list connected. The execution table tracks each step, showing current node, pointer changes, and the visual state of the list. Variable tracker shows how pointers and intervals change. Key moments clarify why we move pointers and how merging works. The quiz tests understanding of these steps.

Practice

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

easy

A. To merge overlapping intervals and keep the list sorted

B. To add the new interval at the end without merging

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

D. To sort the list again after insertion

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: Determine the correct action

   We must merge any overlapping intervals with the new one to keep the list sorted and non-overlapping.

3. Final Answer:

   To merge overlapping intervals and keep the list sorted -> Option A

4. Quick Check:

   Insert interval = merge and keep sorted [OK]

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

Common Mistakes:

• Just appending without merging
• Removing intervals incorrectly
• Sorting again after insertion

2. Which Go syntax correctly declares a slice of intervals where each interval is a slice of two integers?

easy

A. intervals := [][2]int{{1, 3}, {6, 9}}

B. intervals := [][]int{1, 3, 6, 9}

C. intervals := []int{1, 3, 6, 9}

D. intervals := [][]int{{1, 3}, {6, 9}}

Solution

1. Step 1: Identify slice of slices syntax

   In Go, [][]int means a slice of slices of int, suitable for intervals like [start, end].

2. Step 2: Check each option

   intervals := [][]int{{1, 3}, {6, 9}} correctly uses [][]int with nested slices for intervals. intervals := [][2]int{{1, 3}, {6, 9}} uses array [2]int which is valid but less common. intervals := []int{1, 3, 6, 9} is a flat slice, not intervals. intervals := [][]int{1, 3, 6, 9} is invalid syntax.

3. Final Answer:

   intervals := [][]int{{1, 3}, {6, 9}} -> Option D

4. Quick Check:

   Slice of slices = [][]int{{start,end}} [OK]

Hint: Use [][]int for slice of intervals in Go [OK]

Common Mistakes:

• Using flat []int instead of [][]int
• Incorrect array vs slice syntax
• Missing curly braces for nested slices

3. What is the output of the following Go code snippet after inserting interval [2,5] into intervals [[1,2],[6,9]]?

intervals := [][]int{{1, 2}, {6, 9}}
newInterval := []int{2, 5}
// After insertion and merging
result := [][]int{{1, 5}, {6, 9}}
fmt.Println(result)

medium

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

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

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

D. [[2 5] [6 9]]

Solution

1. Step 1: Insert and check overlap

   New interval [2,5] overlaps with [1,2] because 2 <= 2. Merge them to [1,5].

2. Step 2: Keep other intervals

   [6,9] does not overlap with [1,5], so it stays as is.

3. Final Answer:

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

4. Quick Check:

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

Hint: Merge overlapping intervals to combine ranges [OK]

Common Mistakes:

• Not merging overlapping intervals
• Appending new interval without sorting
• Incorrect interval order

4. Given this Go function snippet to insert an interval, what is the bug?

func insert(intervals [][]int, newInterval []int) [][]int {
    var result [][]int
    for _, interval := range intervals {
        if interval[1] < newInterval[0] {
            result = append(result, interval)
        } else if interval[0] > newInterval[1] {
            result = append(result, newInterval)
            newInterval = interval
        } else {
            newInterval[0] = min(newInterval[0], interval[0])
            newInterval[1] = max(newInterval[1], interval[1])
        }
    }
    result = append(result, newInterval)
    return result
}

medium

A. Appending newInterval multiple times causes duplicates

B. Not updating newInterval correctly during merge

C. Missing return statement

D. Incorrect comparison operators in if conditions

Solution

1. Step 1: Analyze appending logic

   When interval[0] > newInterval[1], newInterval is appended and then replaced by interval. This can cause multiple appends of newInterval.

2. Step 2: Identify duplicate insertion

   Because newInterval is appended inside the loop multiple times, duplicates appear in result.

3. Final Answer:

   Appending newInterval multiple times causes duplicates -> Option A

4. Quick Check:

   Multiple appends = duplicates [OK]

Hint: Append newInterval once after loop to avoid duplicates [OK]

Common Mistakes:

• Appending inside loop multiple times
• Not updating newInterval boundaries
• Forgetting to return result

5. You have intervals [[1,3],[6,9]] and want to insert [2,7]. What is the final list after insertion and merging?

hard

A. [[1,3],[2,7],[6,9]]

B. [[1,9]]

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

D. [[1,9],[6,9]]

Solution

1. Step 1: Merge [2,7] with overlapping intervals

   [2,7] overlaps with [1,3] and [6,9]. Merge all three intervals into one covering from min start 1 to max end 9.

2. Step 2: Final merged interval

   The merged interval is [1,9], replacing the original two intervals.

3. Final Answer:

   [[1,9]] -> Option B

4. Quick Check:

   Merge all overlapping = [[1,9]] [OK]

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

Common Mistakes:

• Partial merges leaving overlaps
• Appending without merging
• Incorrect interval boundaries