Insert Interval into Sorted List in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal when inserting an interval into a sorted list of intervals?

To add the new interval into the list so that the list remains sorted and any overlapping intervals are merged into one.

beginner

How do you know if two intervals overlap?

Two intervals overlap if the start of one interval is less than or equal to the end of the other interval, and vice versa.

intermediate

Why is it important that the list of intervals is sorted before inserting a new interval?

Because a sorted list allows us to efficiently find where to insert the new interval and merge overlapping intervals in one pass.

intermediate

What is the time complexity of inserting an interval into a sorted list of intervals and merging overlaps?

O(n), where n is the number of intervals, because we may need to check each interval once to merge overlaps.

beginner

In the context of interval insertion, what does merging intervals mean?

Combining two or more overlapping intervals into a single interval that covers all their ranges.

What should you do if the new interval does not overlap with any existing intervals?

A Merge it with the first interval.

B Insert it in the correct sorted position without merging.

C Discard the new interval.

D Replace the last interval with the new one.

If there is no overlap, the new interval should be inserted in the correct sorted position to keep the list sorted.

Which condition indicates that two intervals [a, b] and [c, d] overlap?

A b < c

B a > d

C b >= c and a <= d

D a > b

Intervals overlap if the end of the first is greater or equal to the start of the second and the start of the first is less or equal to the end of the second.

What is the first step when inserting a new interval into a sorted list?

A Find the position where the new interval fits based on start time.

B Merge all intervals first.

C Remove all intervals that overlap.

D Sort the list again.

You first find where the new interval fits in the sorted order to maintain sorting.

If the new interval overlaps with multiple intervals, what should you do?

A Merge all overlapping intervals including the new one into a single interval.

B Insert the new interval separately.

C Ignore the new interval.

D Delete all overlapping intervals without adding the new one.

All overlapping intervals should be merged into one to maintain correct interval coverage.

What data structure property helps in efficient insertion and merging of intervals?

A The list contains only one interval.

B The list is unsorted.

C The list is sorted by interval end times.

D The list is sorted by interval start times.

Sorting by start times allows linear scanning and merging in one pass.

Explain step-by-step how to insert a new interval into a sorted list of intervals and merge overlaps.

Think about scanning the list from start to end and handling intervals in three parts.

Describe how you detect and merge overlapping intervals when inserting a new interval.

Focus on comparing start and end points to combine intervals.

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