Insert Interval into Sorted List in DSA Javascript

Mental Model

We add a new time slot into a list of sorted, non-overlapping time slots and merge any that overlap.

Analogy: Imagine booking a meeting room with existing reservations. You want to add your meeting without conflicts by merging overlapping times.

Intervals list:
[1,3] -> [6,9] -> null
Insert interval:
[2,5]

Dry Run Walkthrough

Input: intervals: [1,3] -> [6,9], insert [2,5]

Goal: Insert [2,5] into the sorted list and merge overlapping intervals

Step 1: Add all intervals before [2,5] without overlap

null

Why: 1,3 ends after 2 starts, so it overlaps; no intervals added before insert

Step 2: Merge [2,5] with [1,3] because they overlap

[1,5] -> null

Why: Intervals overlap, so merge to [1,5]

Step 3: Check next interval [6,9], no overlap with [1,5], add it

[1,5] -> [6,9] -> null

Why: 6 is after 5, so no overlap; add as is

Result:

[1,5] -> [6,9] -> null

Annotated Code

DSA Javascript

class Interval {
  constructor(start, end) {
    this.start = start;
    this.end = end;
  }
}

function insertInterval(intervals, newInterval) {
  const result = [];
  let i = 0;
  // Add all intervals ending before newInterval starts
  while (i < intervals.length && intervals[i].end < newInterval.start) {
    result.push(intervals[i]);
    i++;
  }
  // Merge overlapping intervals
  while (i < intervals.length && intervals[i].start <= newInterval.end) {
    newInterval.start = Math.min(newInterval.start, intervals[i].start);
    newInterval.end = Math.max(newInterval.end, intervals[i].end);
    i++;
  }
  result.push(newInterval);
  // Add remaining intervals
  while (i < intervals.length) {
    result.push(intervals[i]);
    i++;
  }
  return result;
}

// Driver code
const intervals = [new Interval(1,3), new Interval(6,9)];
const newInterval = new Interval(2,5);
const merged = insertInterval(intervals, newInterval);
// Print result
let output = '';
for (const interval of merged) {
  output += `[${interval.start},${interval.end}] -> `;
}
output += 'null';
console.log(output);

while (i < intervals.length && intervals[i].end < newInterval.start) {

Add intervals that end before new interval starts -- no overlap

while (i < intervals.length && intervals[i].start <= newInterval.end) {

Merge all intervals overlapping with new interval

newInterval.start = Math.min(newInterval.start, intervals[i].start);

Update start of merged interval to earliest start

newInterval.end = Math.max(newInterval.end, intervals[i].end);

Update end of merged interval to latest end

result.push(newInterval);

Add merged interval to result

while (i < intervals.length) {

Add remaining intervals after merged interval

Output

[1,5] -> [6,9] -> null

Complexity Analysis

Time: O(n) because we scan through the list of intervals once

Space: O(n) because we create a new list to store merged intervals

vs Alternative: Naive approach might insert and then sort or merge repeatedly, costing O(n log n) or more

Edge Cases

Empty intervals list

Returns list with only the new interval

DSA Javascript

while (i < intervals.length && intervals[i].end < newInterval.start) {

New interval does not overlap any existing intervals

Inserted in correct position without merging

DSA Javascript

while (i < intervals.length && intervals[i].end < newInterval.start) {

New interval overlaps all existing intervals

All intervals merged into one big interval

DSA Javascript

while (i < intervals.length && intervals[i].start <= newInterval.end) {

When to Use This Pattern

When you see a problem about inserting a time slot into sorted, non-overlapping intervals and merging overlaps, use the Insert Interval pattern to merge efficiently.

Common Mistakes

Mistake: Not merging all overlapping intervals, only the first one
Fix: Use a loop to merge all intervals overlapping with the new interval

Mistake: Inserting new interval before merging, causing incorrect order
Fix: Merge first, then insert the merged interval into the result

Summary

Inserts a new interval into a sorted list of non-overlapping intervals and merges overlaps.

Use when adding a new time slot into existing sorted intervals without conflicts.

The key is to add intervals before, merge overlapping ones, then add the rest.

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