Insert Interval into Sorted List in DSA Java - Execution Trace

Concept Flow - Insert Interval into Sorted List

Create new interval node

↓

Start at head of sorted list

↓

Traverse list to find insert position

↓

Check overlap with current node

↓

Merge intervals

↓

Insert merged/new interval

↓

Adjust pointers to maintain list

↓

Done

Create the new interval, find where it fits in the sorted list, merge overlapping intervals, then insert and adjust pointers.

Execution Sample

DSA Java

class Interval {
  int start, end;
  Interval next;
  public Interval(int start, int end) {
    this.start = start;
    this.end = end;
  }
}

class Solution {
  public Interval insertInterval(Interval head, Interval newInterval) {
    Interval dummy = new Interval(-1, -1);
    dummy.next = head;
    Interval prev = dummy;
    Interval curr = head;
    while (curr != null && newInterval.start > curr.end) {
      prev = curr;
      curr = curr.next;
    }
    while (curr != null && newInterval.end >= curr.start) {
      newInterval.start = Math.min(newInterval.start, curr.start);
      newInterval.end = Math.max(newInterval.end, curr.end);
      curr = curr.next;
    }
    newInterval.next = curr;
    prev.next = newInterval;
    return dummy.next;
  }
}

// Insert new interval into sorted linked list of intervals, merging overlaps if necessary.

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

Execution Table

Step	Operation	Current Node	New Interval	Pointer Changes	Visual State
1	Create new interval	null	[4, 9]	newNode=null	[1,3] -> [6,7] -> [8,10] -> [12,16] -> null
2	Start at head	[1,3]	[4,9]	current=[1,3]	[1,3] -> [6,7] -> [8,10] -> [12,16] -> null
3	Check if new interval before current	[1,3]	[4,9]	No	[1,3] -> [6,7] -> [8,10] -> [12,16] -> null
4	Move to next node	[6,7]	[4,9]	current=[6,7]	[1,3] -> [6,7] -> [8,10] -> [12,16] -> null
5	Check overlap with current	[6,7]	[4,9]	Yes, merge	[1,3] -> [4,9] (merged) -> [8,10] -> [12,16] -> null
6	Merge intervals	[4,9]	[4,9]	newInterval=[4,9]	[1,3] -> [4,9] -> [8,10] -> [12,16] -> null
7	Move to next node	[8,10]	[4,9]	current=[8,10]	[1,3] -> [4,9] -> [8,10] -> [12,16] -> null
8	Check overlap with current	[8,10]	[4,9]	Yes, merge	[1,3] -> [4,10] (merged) -> [12,16] -> null
9	Merge intervals	[4,10]	[4,10]	newInterval=[4,10]	[1,3] -> [4,10] -> [12,16] -> null
10	Move to next node	[12,16]	[4,10]	current=[12,16]	[1,3] -> [4,10] -> [12,16] -> null
11	Check overlap with current	[12,16]	[4,10]	No	[1,3] -> [4,10] -> [12,16] -> null
12	Insert new interval before current	[12,16]	[4,10]	newInterval.next = current	[1,3] -> [4,10] -> [12,16] -> null
13	Adjust previous node's next	[4,10]	[4,10]	previous.next = newInterval	[1,3] -> [4,10] -> [12,16] -> null
14	Done	null	null	List updated	[1,3] -> [4,10] -> [12,16] -> null

💡 Traversal ends when current is null or no more overlaps; new interval inserted and list updated.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 7	After Step 10	Final
current	null	[1,3]	[6,7]	[8,10]	[12,16]	null
newInterval	null	[4,9]	[4,9]	[4,9]	[4,10]	[4,10]
previous	null	null	[1,3]	[4,9]	[4,10]	[4,10]
list	[1,3]->[6,7]->[8,10]->[12,16]->null	[1,3]->[6,7]->[8,10]->[12,16]->null	[1,3]->[6,7]->[8,10]->[12,16]->null	[1,3]->[4,10]->[12,16]->null	[1,3]->[4,10]->[12,16]->null	[1,3]->[4,10]->[12,16]->null

Key Moments - 3 Insights

Why do we merge intervals when they overlap instead of inserting separately?

Because overlapping intervals represent continuous ranges, merging them keeps the list sorted and non-overlapping, as shown in steps 5, 8, and 9 where merges happen.

How do we know where to insert the new interval in the list?

We traverse the list until we find a node where the new interval should be inserted before or merged with, as seen in steps 3, 4, and 11 where comparisons guide traversal.

What happens if the new interval overlaps multiple nodes?

We merge with each overlapping node, updating the new interval's range, as shown in steps 5-9 where merges with [6,7] and [8,10] happen before insertion.

Visual Quiz - 3 Questions

Look at the execution table, what is the 'newInterval' after step 9?

A [4,9]

B [4,10]

C [6,7]

D [8,10]

💡 Hint

Check the 'New Interval' column in row for step 9 in execution_table.

At which step does the traversal move from node [6,7] to [8,10]?

A Step 4

B Step 5

C Step 7

D Step 10

💡 Hint

Look at the 'Current Node' column in execution_table rows for steps 4 and 7.

If the new interval was [5,6] instead of [4,9], how would the visual state change after step 5?

A No merge, inserted between [1,3] and [6,7]

B Merge with [1,3]

C Merge with [6,7] to form [4,9]

D Merge with [8,10]

💡 Hint

Refer to the 'Operation' and 'Visual State' columns in execution_table step 5 and consider overlap conditions.

Concept Snapshot

Insert Interval into Sorted List:
- Traverse sorted list to find insert position
- Merge overlapping intervals into one
- Insert merged/new interval maintaining order
- Adjust pointers to keep list connected
- Result: sorted, non-overlapping intervals list

Full Transcript

To insert a new interval into a sorted linked list of intervals, we first create the new interval node. We start traversing from the head of the list to find the correct position. At each node, we check if the new interval overlaps with the current node's interval. If yes, we merge them by updating the new interval's start and end to cover both. We continue merging with subsequent overlapping nodes. When no more overlaps exist, we insert the merged interval into the list by adjusting pointers. This process keeps the list sorted and non-overlapping. The execution table shows each step, the current node, the new interval state, pointer changes, and the visual state of the list. Key moments clarify why merging is necessary, how insertion position is found, and handling multiple overlaps. The visual quiz tests understanding of interval states and traversal steps. The snapshot summarizes the process in simple steps.

Practice

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

easy

A. Merge the new interval with overlapping intervals and keep the list sorted

B. Add the new interval at the end without checking overlaps

C. Remove all intervals that come after the new interval

D. Sort the list again after adding the new interval anywhere

Solution

1. Step 1: Understand the problem context

   The list contains sorted, non-overlapping intervals. When inserting a new interval, we must keep the list sorted and merge any overlapping intervals.

2. Step 2: Identify correct insertion behavior

   Simply adding the new interval without merging or sorting breaks the list's properties. Proper merging keeps intervals non-overlapping and sorted.

3. Final Answer:

   Merge the new interval with overlapping intervals and keep the list sorted -> Option A

4. Quick Check:

   Insert interval = Merge and sort [OK]

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

Common Mistakes:

• Inserting without merging overlaps
• Appending interval without sorting
• Removing intervals unnecessarily

2. Which of the following Java method signatures correctly represents a function to insert an interval into a sorted list of intervals?

easy

A. public void insertInterval(int intervals[], int newInterval[])

B. public List insertInterval(List intervals, int[] newInterval)

C. public int insertInterval(List<int> intervals, int newInterval)

D. public List<int> insertInterval(int[] intervals, int[] newInterval)

Solution

1. Step 1: Analyze parameter types for intervals

   Intervals are pairs of integers, so List is appropriate to hold multiple intervals. The new interval is an int[] of size 2.

2. Step 2: Check return type and parameters

   The method returns a List after insertion. public List insertInterval(List intervals, int[] newInterval) matches this signature correctly.

3. Final Answer:

   public List insertInterval(List intervals, int[] newInterval) -> Option B

4. Quick Check:

   Correct method signature uses List and int[] [OK]

Hint: Use List for intervals and int[] for new interval [OK]

Common Mistakes:

• Using int[] instead of List for intervals
• Wrong return type like void or int
• Using List<int> instead of List

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

medium

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

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

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

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

Solution

1. Step 1: Identify overlapping intervals

   The new interval [2,5] overlaps with [1,3] because 2 ≤ 3. So they merge into [1,5].

2. Step 2: Merge and keep other intervals

   After merging, the list becomes [[1,5],[6,9]] as [6,9] does not overlap.

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 ≤ current end [OK]

Common Mistakes:

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

4. Consider this Java code snippet for inserting an interval:

List insertInterval(List intervals, int[] newInterval) {
  List result = new ArrayList<>();
  for (int[] interval : intervals) {
    if (interval[1] < newInterval[0]) {
      result.add(interval);
    } else if (interval[0] > newInterval[1]) {
      result.add(newInterval);
      newInterval = interval;  // Fix to avoid multiple additions
    } else {
      newInterval[0] = Math.min(newInterval[0], interval[0]);
      newInterval[1] = Math.max(newInterval[1], interval[1]);
    }
  }
  result.add(newInterval);
  return result;
}

What is the bug in this code?

medium

A. It adds newInterval multiple times if intervals after it exist

B. It never adds intervals that come before newInterval

C. It modifies the input intervals list directly

D. It does not merge overlapping intervals correctly

Solution

1. Step 1: Analyze insertion of newInterval in else-if block

   When interval[0] > newInterval[1], it adds newInterval to result, but continues looping, causing newInterval to be added again later.

2. Step 2: Identify repeated addition of newInterval

   Because newInterval is added again after the loop, it can be added multiple times, causing duplicates.

3. Final Answer:

   It adds newInterval multiple times if intervals after it exist -> Option A

4. Quick Check:

   Repeated addition of newInterval causes duplicates [OK]

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

Common Mistakes:

• Adding newInterval inside loop multiple times
• Not updating newInterval correctly
• Forgetting to add remaining intervals

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

hard

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

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

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

D. [[1,2],[3,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 overlapping intervals

   Merge [3,5], [6,7], [8,10], and [4,8] into one interval [3,10]. The others remain unchanged.

3. Step 3: Construct final list

   The final list is [[1,2],[3,10],[12,16]].

4. Final Answer:

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

5. Quick Check:

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

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

Common Mistakes:

• Not merging all overlapping intervals
• Leaving duplicates of overlapping intervals
• Incorrectly splitting merged intervals