Insert Interval into Sorted List in DSA Python - Execution Trace

Concept Flow - Insert Interval into Sorted List

Start with sorted intervals list

↓

Create new interval node

↓

Traverse list to find insert position

↓

Check overlap with current interval?

Yes→Merge intervals

↓

Update merged interval

↓

Insert new or merged interval

↓

Continue merging if needed

↓

Finish traversal

↓

Return updated intervals list

Start with a sorted list of intervals, find where to insert the new interval, merge overlapping intervals, and return the updated sorted list.

Execution Sample

DSA Python

intervals = [[1,3],[6,9]]
newInterval = [2,5]

def insert(intervals, newInterval):
    result = []
    i = 0
    # Add all intervals ending before newInterval starts
    while i < len(intervals) and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1
    # Merge all overlapping intervals
    while i < len(intervals) and intervals[i][0] <= newInterval[1]:
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i += 1
    result.append(newInterval)
    # Add remaining intervals
    while i < len(intervals):
        result.append(intervals[i])
        i += 1
    return result

# Insert and merge intervals
result = insert(intervals, newInterval)
print(result)

This code inserts the interval [2,5] into the sorted list [[1,3],[6,9]] and merges overlapping intervals.

Execution Table

Step	Operation	Current Interval	New Interval	Action	Intervals List State
1	Start	-	[2,5]	Initial intervals and new interval	[]
2	Check overlap	[1,3]	[2,5]	Overlap detected, merge intervals	[[1,5]]
3	Move to next	[6,9]	[1,5]	No overlap, add current interval to result	[[1,5],[6,9]]
4	Insert remaining	-	[1,5]	All intervals processed, insert merged interval if not added	[[1,5],[6,9]]
5	End	-	-	Return merged intervals list	[[1,5],[6,9]]

💡 All intervals processed and merged where overlapping, final list returned.

Variable Tracker

Variable	Start	After Step 2	After Step 3	Final
intervals	[[1,3],[6,9]]	[[1,3],[6,9]]	[[1,3],[6,9]]	[[1,3],[6,9]]
newInterval	[2,5]	[1,5]	[1,5]	[1,5]
result	[]	[[1,5]]	[[1,5],[6,9]]	[[1,5],[6,9]]
i (index)	0	1	2	2

Key Moments - 3 Insights

Why do we merge intervals when they overlap instead of just inserting the new interval?

Because overlapping intervals represent continuous ranges that should be combined into one. As shown in Step 2 of the execution_table, merging [1,3] and [2,5] creates [1,5], avoiding duplicate or overlapping intervals.

What happens if the new interval does not overlap with any existing intervals?

The new interval is inserted in the correct sorted position without merging. This is implied in Step 3 and 4 where intervals without overlap are simply added to the result list.

Why do we continue checking intervals after merging the new interval?

Because the merged interval might overlap with subsequent intervals. The algorithm ensures all overlapping intervals are merged before final insertion, as seen in the flow from Step 2 to Step 3.

Visual Quiz - 3 Questions

Look at the execution_table at Step 2, what is the new merged interval after merging?

A [1,3]

B [2,5]

C [1,5]

D [6,9]

💡 Hint

Check the 'New Interval' and 'Action' columns at Step 2 in the execution_table.

At which step does the algorithm add the interval [6,9] to the result list?

A Step 3

B Step 2

C Step 4

D Step 5

💡 Hint

Look at the 'Action' and 'Intervals List State' columns in the execution_table for when [6,9] appears in the result.

If the new interval was [10,12], how would the final intervals list look?

A [[1,3],[6,9]]

B [[1,3],[6,9],[10,12]]

C [[1,3],[6,12]]

D [[10,12],[1,3],[6,9]]

💡 Hint

Consider that [10,12] does not overlap and should be inserted at the end.

Concept Snapshot

Insert Interval into Sorted List:
- Input: sorted list of intervals and a new interval
- Traverse intervals to find overlap
- Merge overlapping intervals by updating start/end
- Insert merged/new interval in correct position
- Return updated sorted intervals list

Full Transcript

This visualization shows how to insert a new interval into a sorted list of intervals. We start with the original intervals and the new interval. We check each interval for overlap with the new interval. If they overlap, we merge them by updating the start and end of the new interval. If no overlap, we add the current interval to the result. After processing all intervals, we insert the merged new interval if not already added. The final list is sorted and merged without overlaps.

Practice

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

easy

A. To add the new interval and merge any overlapping intervals to keep the list sorted and non-overlapping

B. To replace the first interval with the new interval regardless of overlap

C. To insert the new interval at the end without checking for overlaps

D. To delete all intervals that come after the new interval

Solution

1. Step 1: Understand the problem requirement

   The goal is to insert a new interval into a sorted list of intervals without overlaps.

2. Step 2: Merge overlapping intervals after insertion

   After inserting, merge any intervals that overlap to maintain the sorted, non-overlapping property.

3. Final Answer:

   To add the new interval and merge any overlapping intervals to keep the list sorted and non-overlapping -> Option A

4. Quick Check:

   Insert and merge intervals = To add the new interval and merge any overlapping intervals to keep the list sorted and non-overlapping [OK]

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

Common Mistakes:

• Ignoring merging after insertion
• Inserting without maintaining order
• Replacing intervals incorrectly

2. Which of the following Python code snippets correctly inserts a new interval into a sorted list of intervals without merging?

easy

A. intervals.remove(new_interval)

B. intervals.append(new_interval)

C. intervals.sort()

D. intervals.insert(2, new_interval)

Solution

1. Step 1: Identify correct insertion method

   Using insert(index, element) places the new interval at the correct position without losing order.

2. Step 2: Understand other options

   append adds at end without order, sort only sorts but doesn't insert, remove deletes an element.

3. Final Answer:

   intervals.insert(2, new_interval) -> Option D

4. Quick Check:

   Use insert() to add at specific position [OK]

Hint: Use insert(index, value) to place interval correctly [OK]

Common Mistakes:

• Using append without sorting
• Using remove instead of insert
• Relying on sort without insertion

3. What is the output of the following code?

intervals = [[1,3],[6,9]]
new_interval = [2,5]

# Insert new_interval and merge
result = []
i = 0
while i < len(intervals) and intervals[i][1] < new_interval[0]:
    result.append(intervals[i])
    i += 1
while i < len(intervals) and intervals[i][0] <= new_interval[1]:
    new_interval[0] = min(new_interval[0], intervals[i][0])
    new_interval[1] = max(new_interval[1], intervals[i][1])
    i += 1
result.append(new_interval)
while i < len(intervals):
    result.append(intervals[i])
    i += 1
print(result)

medium

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

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

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

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

Solution

1. Step 1: Add intervals before new_interval

   The first while loop checks if intervals[i][1] < new_interval[0]. For i=0, 3 < 2 is false, so no intervals added before. result = [].

2. Step 2: Merge overlapping intervals

   Intervals overlapping with new_interval [2,5] are [1,3] and [2,5] merged to [1,5].

3. Step 3: Add remaining intervals

   Remaining interval [6,9] is added after merged interval.

4. Final Answer:

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

5. Quick Check:

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

Hint: Merge intervals overlapping new_interval boundaries [OK]

Common Mistakes:

• Not merging overlapping intervals
• Appending new_interval without merging
• Incorrect loop conditions

4. The following code tries to insert and merge a new interval but produces incorrect output. What is the bug?

def insert_interval(intervals, new_interval):
    result = []
    for interval in intervals:
        if interval[1] < new_interval[0]:
            result.append(interval)
        elif interval[0] > new_interval[1]:
            result.append(new_interval)
        else:
            new_interval[0] = min(new_interval[0], interval[0])
            new_interval[1] = max(new_interval[1], interval[1])
    result.append(new_interval)
    return result

print(insert_interval([[1,3],[6,9]], [2,5]))

medium

A. Appending new_interval inside loop causes duplicates

B. Not updating new_interval correctly during merge

C. Missing return statement

D. Incorrect comparison operators in conditions

Solution

1. Step 1: Analyze loop behavior

   Appending new_interval inside the loop when interval[0] > new_interval[1] causes multiple appends.

2. Step 2: Understand consequences

   This leads to duplicates and incorrect order in the result list.

3. Final Answer:

   Appending new_interval inside loop causes duplicates -> Option A

4. Quick Check:

   Append new_interval once after loop [OK]

Hint: Append merged interval only once after loop ends [OK]

Common Mistakes:

• Appending inside loop multiple times
• Not merging intervals properly
• Confusing interval boundaries

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

hard

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

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

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

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

Solution

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

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

2. Step 2: Merge overlapping intervals

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

3. Step 3: Combine with non-overlapping intervals

   Keep [1,2] and [12,16] as is, final list is [[1,2],[3,10],[12,16]].

4. Final Answer:

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

5. Quick Check:

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

Hint: Merge all intervals overlapping new interval boundaries [OK]

Common Mistakes:

• Not merging all overlapping intervals
• Appending new interval without merging
• Incorrectly splitting intervals