Insert Interval into Sorted List in DSA Javascript - Execution Trace

Concept Flow - Insert Interval into Sorted List

Start with sorted intervals list

↓

Check each interval in list

↓

Does new interval overlap current?

No→Add current interval to result

Yes↓

Merge intervals by updating new interval bounds

↓

Continue checking next intervals

↓

Add merged new interval to result

↓

Add remaining intervals

↓

Return merged intervals list

We scan the sorted intervals, merge overlapping ones with the new interval, and build a new list with merged intervals.

Execution Sample

DSA Javascript

function insertInterval(intervals, newInterval) {
  let result = [];
  let i = 0;
  while (i < intervals.length && intervals[i][1] < newInterval[0]) {
    result.push(intervals[i++]);
  }
  while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
    newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
    newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
    i++;
  }
  result.push(newInterval);
  while (i < intervals.length) {
    result.push(intervals[i++]);
  }
  return result;
}

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

Execution Table

Step	Operation	Current Interval	New Interval	Result List	Pointer i	Visual State
1	Initialize	N/A	[4,8]	[]	0	[[1,3],[6,9]] (input intervals)
2	Check intervals before newInterval	[1,3]	[4,8]	[]	0	1st interval end 3 < new start 4, add to result
3	Add interval to result	[1,3]	[4,8]	[[1,3]]	1	Result updated with [1,3]
4	Check overlap with newInterval	[6,9]	[4,8]	[[1,3]]	1	6 <= 8 overlap detected, merge intervals
5	Merge intervals	[6,9]	[4,8]	[[1,3]]	1	New interval updated to [4,9] (min start 4, max end 9)
6	Move pointer	N/A	[4,9]	[[1,3]]	2	All intervals checked for overlap
7	Add merged newInterval	N/A	[4,9]	[[1,3],[4,9]]	2	Merged interval added to result
8	Add remaining intervals	N/A	[4,9]	[[1,3],[4,9]]	2	No remaining intervals to add
9	Return result	N/A	N/A	[[1,3],[4,9]]	2	Final merged intervals list

💡 All intervals processed, merged new interval inserted, result returned

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	Final
i	0	1	2	2	2
newInterval	[4,8]	[4,8]	[4,9]	[4,9]	[4,9]
result	[]	[[1,3]]	[[1,3]]	[[1,3],[4,9]]	[[1,3],[4,9]]

Key Moments - 3 Insights

Why do we first add intervals that end before the new interval starts?

Because these intervals do not overlap with the new interval, so we can safely add them to the result before merging. See execution_table row 3 where [1,3] is added before merging.

How do we merge overlapping intervals with the new interval?

We update the new interval's start to the minimum start and end to the maximum end of overlapping intervals. See execution_table row 5 where newInterval changes from [4,8] to [4,9].

Why do we add the merged new interval after merging all overlaps?

Because after merging, the new interval represents all overlapping intervals combined. Adding it after ensures the result list stays sorted. See execution_table row 7.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'i' after adding the first interval to the result?

A 0

B 1

C 2

D 3

💡 Hint

Check the 'Pointer i' column at Step 3 in the execution_table.

At which step does the newInterval get updated to include the overlapping interval?

A Step 3

B Step 4

C Step 5

D Step 7

💡 Hint

Look at the 'New Interval' column changes in execution_table rows 4 and 5.

If the newInterval was [2,5], how would the result list change after step 3?

A []

B [[1,3]]

C [[1,3],[6,9]]

D [[6,9]]

💡 Hint

Refer to variable_tracker and execution_table rows 2 and 3 for intervals added before merging.

Concept Snapshot

Insert Interval into Sorted List:
- Scan intervals before new interval (end < new start), add to result
- Merge overlapping intervals by updating new interval bounds
- Add merged new interval to result
- Add remaining intervals
- Result is sorted, merged intervals list

Full Transcript

This concept shows how to insert a new interval into a sorted list of intervals. We first add all intervals that end before the new interval starts because they do not overlap. Then, we merge all intervals that overlap with the new interval by updating the new interval's start and end to cover all overlaps. After merging, we add the new merged interval to the result list. Finally, we add any remaining intervals that start after the new interval ends. The final result is a sorted list of intervals with no 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 at the end without checking overlaps

B. To merge overlapping intervals and keep the list sorted

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

D. To sort the intervals again after insertion without merging

Solution

1. Step 1: Understand the problem context

   We have a sorted list of intervals with no overlaps, and we want to insert a new interval.

2. Step 2: Identify the correct approach

   We must merge any intervals that overlap with the new one and keep the list sorted.

3. Final Answer:

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

4. Quick Check:

   Insert interval = merge and sort [OK]

Hint: Merge overlapping intervals to keep list sorted after insertion [OK]

Common Mistakes:

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

2. Which of the following is the correct syntax to insert an interval [3,5] into a JavaScript array named intervals?

easy

A. intervals.push([3,5])

B. intervals.insert([3,5])

C. intervals.add([3,5])

D. intervals.append([3,5])

Solution

1. Step 1: Recall JavaScript array methods

   JavaScript arrays use push() to add elements at the end.

2. Step 2: Match method to syntax

   push() is correct; insert(), add(), and append() are not valid JavaScript array methods.

3. Final Answer:

   intervals.push([3,5]) -> Option A

4. Quick Check:

   Use push() to add elements in JS arrays [OK]

Hint: Use push() to add elements to JavaScript arrays [OK]

Common Mistakes:

• Using insert() which is not a JS array method
• Using add() or append() from other languages
• Forgetting to add as an array element

3. What is the output of the following code?

const intervals = [[1,2],[5,6]];
const newInterval = [3,5];
function insertInterval(intervals, newInterval) {
  const result = [];
  let i = 0;
  while (i < intervals.length && intervals[i][1] < newInterval[0]) {
    result.push(intervals[i]);
    i++;
  }
  while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
    newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
    newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
    i++;
  }
  result.push(newInterval);
  while (i < intervals.length) {
    result.push(intervals[i]);
    i++;
  }
  return result;
}
console.log(insertInterval(intervals, newInterval));

medium

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

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

C. [[1,6]]

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

Solution

1. Step 1: Process intervals before newInterval

   Intervals before newInterval are [[1,2]] because 2 < 3, so push [1,2].

2. Step 2: Merge overlapping intervals

   Intervals overlapping with newInterval are [5,6] because 5 <= 5. Merge [3,5] and [5,6] to get [3,6].

3. Step 3: Add merged interval and remaining intervals

   Push merged [3,6]. No intervals left after merging.

4. Final Answer:

   [[1,2],[3,6]] -> Option D

5. Quick Check:

   Merged intervals = [[1,2],[3,6]] [OK]

Hint: Merge intervals overlapping newInterval, keep others as is [OK]

Common Mistakes:

• Not merging overlapping intervals
• Adding newInterval multiple times
• Incorrectly ordering intervals after merge

4. Identify the bug in this code snippet that inserts a new interval into a sorted list:

function insert(intervals, newInterval) {
  let result = [];
  let i = 0;
  while (i < intervals.length && intervals[i][1] < newInterval[0]) {
    result.push(intervals[i]);
    i++;
  }
  while (i < intervals.length && intervals[i][0] < newInterval[1]) {
    newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
    newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
    i++;
  }
  result.push(newInterval);
  while (i < intervals.length) {
    result.push(intervals[i]);
    i++;
  }
  return result;
}

medium

A. The newInterval is pushed before merging

B. The first while condition should use < instead of <=

C. The second while condition should use <= instead of <

D. The result array is not initialized

Solution

1. Step 1: Analyze the second while loop condition

   The second loop merges overlapping intervals. It uses intervals[i][0] < newInterval[1], which misses intervals starting exactly at newInterval[1].

2. Step 2: Correct the condition

   Change < to <= to include intervals starting at newInterval[1] for proper merging.

3. Final Answer:

   The second while condition should use <= instead of < -> Option C

4. Quick Check:

   Use <= to merge intervals starting at newInterval[1] [OK]

Hint: Use <= to include intervals starting exactly at newInterval end [OK]

Common Mistakes:

• Using < instead of <= in merge condition
• Pushing newInterval too early
• Not initializing result array

5. Given intervals = [[1,3],[6,9]] and newInterval = [2,5], what is the correct output after inserting and merging intervals?

hard

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

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

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

D. [[1,9]]

Solution

1. Step 1: Identify intervals before newInterval

   Interval [1,3] overlaps with newInterval [2,5] because 3 >= 2, so no intervals come before without overlap.

2. Step 2: Merge overlapping intervals

   Merge [1,3] and [2,5] to get [1,5]. Interval [6,9] does not overlap and stays as is.

3. Final Answer:

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

4. Quick Check:

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

Hint: Merge all overlapping intervals including newInterval [OK]

Common Mistakes:

• Not merging overlapping intervals
• Adding newInterval without merging
• Merging unrelated intervals