Insert Interval into Sorted List in DSA Javascript - Deep Dive

Overview - Insert Interval into Sorted List

What is it?

Insert Interval into Sorted List means adding a new time range into a list of existing time ranges that are sorted and do not overlap. The goal is to keep the list sorted and merge any overlapping intervals after insertion. This helps manage schedules, bookings, or any ranges where overlaps are not allowed. It is a common problem in programming that deals with intervals and sorting.

Why it matters

Without this concept, managing overlapping time ranges or intervals would be complicated and error-prone. For example, scheduling meetings or booking rooms would be difficult if you cannot efficiently add new intervals and merge overlaps. This concept helps keep data clean, organized, and easy to query, which is essential in many real-world applications like calendars, resource allocation, and event planning.

Where it fits

Before learning this, you should understand arrays, sorting, and basic interval concepts. After this, you can explore more complex interval problems like interval trees or segment trees for efficient querying and updates.

Mental Model

Core Idea

Insert the new interval in the right place, then merge all overlapping intervals to keep the list sorted and non-overlapping.

Think of it like...

Imagine you have a row of books sorted by their thickness, and you want to add a new book. You place it in the right spot and then push or combine any books that overlap in size so the row stays neat and ordered.

Intervals list before insertion:
┌─────────┐ ┌─────────────┐ ┌─────────┐
│ 1 - 3   │ │ 6 - 9       │ │ 12 - 15 │
└─────────┘ └─────────────┘ └─────────┘

Insert new interval: 4 - 10

Step 1: Insert in order:
┌─────────┐ ┌─────────────┐ ┌─────────┐ ┌─────────┐
│ 1 - 3   │ │ 4 - 10      │ │ 6 - 9   │ │ 12 - 15 │
└─────────┘ └─────────────┘ └─────────┘ └─────────┘

Step 2: Merge overlaps:
┌─────────┐ ┌─────────────┐ ┌─────────┐
│ 1 - 3   │ │ 4 - 10      │ │ 12 - 15 │
└─────────┘ └─────────────┘ └─────────┘

Merge 4-10 and 6-9 -> 4-10

Final list:
┌─────────┐ ┌─────────────┐ ┌─────────┐
│ 1 - 3   │ │ 4 - 10      │ │ 12 - 15 │
└─────────┘ └─────────────┘ └─────────┘

Build-Up - 6 Steps

1

Foundation

Understanding Intervals and Sorting

Concept: Intervals are pairs of numbers representing ranges, and sorting means arranging them by their start times.

An interval is like a time slot with a start and end. For example, [1, 3] means from time 1 to time 3. A list of intervals sorted by start time looks like [[1,3], [6,9], [12,15]]. This order helps us find where to insert new intervals easily.

Result

You can identify where a new interval fits by comparing its start time with existing intervals.

Knowing intervals and sorting lets you quickly find the right place to insert new intervals without scanning the whole list.

2

Foundation

What is Overlapping Between Intervals

Concept: Two intervals overlap if they share any common points in their ranges.

For example, intervals [4, 10] and [6, 9] overlap because 6 to 9 is inside 4 to 10. But [1, 3] and [4, 10] do not overlap because 3 ends before 4 starts. Overlapping intervals need to be merged to avoid conflicts.

Result

You can detect overlap by checking if the start of one interval is less than or equal to the end of another.

Understanding overlap is key to merging intervals and keeping the list clean and conflict-free.

3

Intermediate

Inserting Interval in Sorted List

🤔Before reading on: do you think you should insert the new interval at the start, middle, or end of the list? Commit to your answer.

Concept: Insert the new interval in the correct position based on its start time to keep the list sorted.

Since the list is sorted by start time, find the first interval whose start is greater than the new interval's start. Insert the new interval before it. If none is greater, append at the end. This keeps the list sorted.

Result

The new interval is placed in the right order, but overlaps may still exist.

Inserting in order simplifies the next step of merging because intervals are mostly sorted.

4

Intermediate

Merging Overlapping Intervals

🤔Before reading on: do you think merging intervals requires checking all intervals or just neighbors? Commit to your answer.

Concept: Merge intervals that overlap by combining their ranges into one larger interval.

Traverse the list from start to end. For each interval, check if it overlaps with the last interval in the merged list. If yes, update the end of the last merged interval to the maximum end of both. If no, add the current interval to the merged list.

Result

A list of intervals with no overlaps, sorted by start time.

Merging only neighbors works because the list is sorted, making the process efficient and simple.

5

Advanced

Efficient Single-Pass Insert and Merge

🤔Before reading on: do you think it's possible to insert and merge intervals in one pass? Commit to your answer.

Concept: Combine insertion and merging in a single pass through the list for efficiency.

Start with an empty result list. Iterate over existing intervals: - Add all intervals that end before the new interval starts. - Merge all intervals that overlap with the new interval by updating the new interval's start and end. - Add the merged new interval. - Add remaining intervals after the new interval. This avoids multiple passes and extra sorting.

Result

A merged, sorted list with the new interval inserted correctly in one pass.

One-pass insertion and merging saves time and memory, important for large interval lists.

6

Expert

Handling Edge Cases and Large Inputs

🤔Before reading on: do you think empty lists or intervals with same start and end need special handling? Commit to your answer.

Concept: Consider edge cases like empty lists, intervals with zero length, and very large lists for robustness.

If the list is empty, just return the new interval as the only element. If intervals have the same start and end, treat them as valid intervals. For large lists, the one-pass approach is critical to avoid performance issues. Also, carefully handle intervals that touch but do not overlap (e.g., end of one is start of another) based on problem requirements.

Result

Robust insertion and merging that works correctly in all cases.

Anticipating edge cases prevents bugs and ensures your solution works in real-world scenarios.

Under the Hood

The algorithm leverages the sorted order of intervals to efficiently find the insertion point and merge overlaps. It uses comparisons of interval start and end points to detect overlaps. Internally, it iterates through the list once, maintaining a merged list and updating intervals as needed. This avoids repeated sorting or scanning, making it O(n) time complexity.

Why designed this way?

The design uses sorting and merging because intervals naturally form ranges that can overlap. Sorting simplifies overlap detection to neighbors only, reducing complexity. Alternatives like interval trees are more complex and used for dynamic queries, but for static insertion, this approach is simpler and faster.

Input intervals: [1,3], [6,9], [12,15]
New interval: [4,10]

Iteration:
[1,3] ends before 4 -> add [1,3]
[6,9] overlaps with [4,10] -> merge to [4,10]
[12,15] starts after 10 -> add [4,10], then [12,15]

Result:
[1,3] -> [4,10] -> [12,15]

Myth Busters - 3 Common Misconceptions

Quick: Do you think you must sort the entire list again after inserting the new interval? Commit yes or no.

Common Belief: After inserting the new interval, you must sort the entire list again to maintain order.

Reality: Because the original list is already sorted, you only need to insert the new interval in the correct position without sorting the whole list again.

Why it matters: Sorting the entire list again wastes time and resources, especially for large lists, making the solution inefficient.

Quick: Do you think merging intervals requires checking all pairs of intervals? Commit yes or no.

Common Belief: You must compare every interval with every other interval to merge overlaps.

Reality: Since the list is sorted, you only need to compare each interval with the last merged interval, reducing comparisons drastically.

Why it matters: Misunderstanding this leads to inefficient O(n^2) solutions instead of optimal O(n) solutions.

Quick: Do you think intervals that just touch (end equals start) always merge? Commit yes or no.

Common Belief: Intervals that touch at a point, like [1,3] and [3,5], always merge into one interval.

Reality: Whether touching intervals merge depends on the problem definition; sometimes they are considered overlapping, sometimes not.

Why it matters: Assuming always merge can cause incorrect interval lists and bugs in scheduling or booking systems.

Expert Zone

1

Merging intervals in-place can save memory but requires careful index management to avoid skipping intervals.

2

Handling intervals with open or closed boundaries (e.g., inclusive or exclusive ends) changes overlap logic subtly but importantly.

3

In real-time systems, incremental updates to intervals may require data structures like balanced trees instead of simple lists.

When NOT to use

This approach is not suitable when you need fast queries for overlapping intervals or frequent insertions and deletions. In such cases, use interval trees or segment trees for better performance.

Production Patterns

In production, this pattern is used in calendar apps to add events, in booking systems to manage reservations, and in network scheduling to allocate time slots without conflicts.

Connections

Interval Trees

Builds-on

Understanding simple interval insertion and merging is foundational before learning interval trees, which handle dynamic interval queries efficiently.

Merge Sort Algorithm

Shares pattern

Both involve merging sorted sequences efficiently, teaching the power of sorting to simplify complex problems.

Project Management Scheduling

Application domain

Knowing how to insert and merge intervals helps manage project tasks and timelines without conflicts.

Common Pitfalls

#1 Inserting the new interval at the end without checking order.

Wrong approach:

intervals.push(newInterval);

Correct approach:

Find correct position by comparing start times and insert there.

Root cause:

Assuming new interval always belongs at the end ignores sorting requirement.

#2 Merging intervals by comparing all pairs instead of neighbors.

Wrong approach:

for (let i = 0; i < intervals.length; i++) {
for (let j = i + 1; j < intervals.length; j++) {
if (overlap(intervals[i], intervals[j])) {
merge(intervals[i], intervals[j]);
}
}
}

Correct approach:

Iterate once, merge current interval with last merged interval if overlapping.

Root cause:

Not leveraging sorted order leads to inefficient nested loops.

#3 Merging intervals that only touch without problem definition check.

Wrong approach:

if (interval1.end >= interval2.start) merge(interval1, interval2);

Correct approach:

Check problem rules; sometimes use if (interval1.end > interval2.start) to merge only overlapping intervals.

Root cause:

Ignoring problem-specific definitions of overlap causes incorrect merges.

Key Takeaways

Inserting an interval into a sorted list requires placing it in the correct order by start time.

Merging overlapping intervals after insertion keeps the list clean and conflict-free.

Because the list is sorted, merging only needs to compare neighbors, making it efficient.

A one-pass approach can insert and merge intervals together, saving time and memory.

Handling edge cases and problem-specific overlap definitions is crucial for robust solutions.

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