Insert Interval into Sorted List in DSA Go

Mental Model

We have a list of sorted intervals and want to add a new interval, merging any overlaps so the list stays sorted and non-overlapping.

Analogy: Imagine booking meeting rooms in a day. You have existing booked times sorted by start time. When you add a new meeting, you merge it with any overlapping bookings to avoid double-booking.

Intervals: [1,3] -> [6,9] -> null
New interval: [2,5]
Goal: Insert and merge overlaps

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: Start with empty result list, check first interval [1,3]

[1,3] -> [6,9] -> null
result: []

Why: We need to compare new interval with existing intervals to find overlaps

Step 2: Since [1,3] overlaps with [2,5], merge them into [1,5]

Merged interval: [1,5]
Remaining intervals: [6,9] -> null
result: []

Why: Overlapping intervals must be combined into one

Step 3: Move to next interval [6,9], which does not overlap with [1,5], add merged interval [1,5] to result

result: [1,5] -> null
Remaining intervals: [6,9] -> null

Why: Non-overlapping intervals are added as is

Step 4: Add remaining interval [6,9] to result

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

Why: All intervals processed, final merged list ready

Result:

Final intervals: [1,5] -> [6,9] -> null

Annotated Code

DSA Go

package main

import (
	"fmt"
)

type Interval struct {
	Start int
	End   int
}

func insertInterval(intervals []Interval, newInterval Interval) []Interval {
	result := []Interval{}
	i := 0
	// Add all intervals ending before newInterval starts
	for i < len(intervals) && intervals[i].End < newInterval.Start {
		result = append(result, intervals[i])
		i++
	}
	// Merge overlapping intervals
	for i < len(intervals) && intervals[i].Start <= newInterval.End {
		if intervals[i].Start < newInterval.Start {
			newInterval.Start = intervals[i].Start
		}
		if intervals[i].End > newInterval.End {
			newInterval.End = intervals[i].End
		}
		i++
	}
	// Add merged interval
	result = append(result, newInterval)
	// Add remaining intervals
	for i < len(intervals) {
		result = append(result, intervals[i])
		i++
	}
	return result
}

func printIntervals(intervals []Interval) {
	for _, iv := range intervals {
		fmt.Printf("[%d,%d] ", iv.Start, iv.End)
	}
	fmt.Println()
}

func main() {
	intervals := []Interval{{1, 3}, {6, 9}}
	newInterval := Interval{2, 5}
	result := insertInterval(intervals, newInterval)
	printIntervals(result)
}

for i < len(intervals) && intervals[i].End < newInterval.Start {

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

for i < len(intervals) && intervals[i].Start <= newInterval.End {

Merge all intervals overlapping with new interval

if intervals[i].Start < newInterval.Start { newInterval.Start = intervals[i].Start }

Update start of merged interval to earliest start

if intervals[i].End > newInterval.End { newInterval.End = intervals[i].End }

Update end of merged interval to latest end

result = append(result, newInterval)

Add merged interval to result

for i < len(intervals) { result = append(result, intervals[i]); i++ }

Add remaining intervals after merged interval

Output

[1,5] [6,9] 

Complexity Analysis

Time: O(n) because we scan 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 repeatedly merge, costing O(n log n) or more

Edge Cases

Empty intervals list

Returns list with only the new interval

DSA Go

for i < len(intervals) && intervals[i].End < newInterval.Start {

New interval does not overlap and goes at the end

New interval appended after all existing intervals

DSA Go

for i < len(intervals) && intervals[i].End < newInterval.Start {

New interval overlaps all intervals

All intervals merged into one big interval

DSA Go

for i < len(intervals) && intervals[i].Start <= newInterval.End {

When to Use This Pattern

When you see a sorted list of intervals and need to add a new one merging overlaps, use the Insert Interval pattern to efficiently merge in one pass.

Common Mistakes

Mistake: Not merging all overlapping intervals, only merging the first overlap
Fix: Continue merging while intervals overlap, not just once

Mistake: Inserting new interval without maintaining sorted order
Fix: Add intervals before new interval first, then merged interval, then remaining intervals

Summary

Inserts a new interval into a sorted list of intervals and merges any overlaps.

Use when you have sorted intervals and want to add a new one without breaking order or overlapping.

The key is to add all intervals before the new one, merge overlaps, 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 merge overlapping intervals and keep the list sorted

B. To add the new interval at the end without merging

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

D. To sort the list again after insertion

Solution

1. Step 1: Understand the problem context

   The list contains sorted, non-overlapping intervals. Inserting a new interval may cause overlaps.

2. Step 2: Determine the correct action

   We must merge any overlapping intervals with the new one to keep the list sorted and non-overlapping.

3. Final Answer:

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

4. Quick Check:

   Insert interval = merge and keep sorted [OK]

Hint: Merge overlaps to keep intervals sorted and non-overlapping [OK]

Common Mistakes:

• Just appending without merging
• Removing intervals incorrectly
• Sorting again after insertion

2. Which Go syntax correctly declares a slice of intervals where each interval is a slice of two integers?

easy

A. intervals := [][2]int{{1, 3}, {6, 9}}

B. intervals := [][]int{1, 3, 6, 9}

C. intervals := []int{1, 3, 6, 9}

D. intervals := [][]int{{1, 3}, {6, 9}}

Solution

1. Step 1: Identify slice of slices syntax

   In Go, [][]int means a slice of slices of int, suitable for intervals like [start, end].

2. Step 2: Check each option

   intervals := [][]int{{1, 3}, {6, 9}} correctly uses [][]int with nested slices for intervals. intervals := [][2]int{{1, 3}, {6, 9}} uses array [2]int which is valid but less common. intervals := []int{1, 3, 6, 9} is a flat slice, not intervals. intervals := [][]int{1, 3, 6, 9} is invalid syntax.

3. Final Answer:

   intervals := [][]int{{1, 3}, {6, 9}} -> Option D

4. Quick Check:

   Slice of slices = [][]int{{start,end}} [OK]

Hint: Use [][]int for slice of intervals in Go [OK]

Common Mistakes:

• Using flat []int instead of [][]int
• Incorrect array vs slice syntax
• Missing curly braces for nested slices

3. What is the output of the following Go code snippet after inserting interval [2,5] into intervals [[1,2],[6,9]]?

intervals := [][]int{{1, 2}, {6, 9}}
newInterval := []int{2, 5}
// After insertion and merging
result := [][]int{{1, 5}, {6, 9}}
fmt.Println(result)

medium

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

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

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

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

Solution

1. Step 1: Insert and check overlap

   New interval [2,5] overlaps with [1,2] because 2 <= 2. Merge them to [1,5].

2. Step 2: Keep other intervals

   [6,9] does not overlap with [1,5], so it stays as is.

3. Final Answer:

   [[1 5] [6 9]] -> Option C

4. Quick Check:

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

Hint: Merge overlapping intervals to combine ranges [OK]

Common Mistakes:

• Not merging overlapping intervals
• Appending new interval without sorting
• Incorrect interval order

4. Given this Go function snippet to insert an interval, what is the bug?

func insert(intervals [][]int, newInterval []int) [][]int {
    var result [][]int
    for _, interval := range intervals {
        if interval[1] < newInterval[0] {
            result = append(result, interval)
        } else if interval[0] > newInterval[1] {
            result = append(result, newInterval)
            newInterval = interval
        } else {
            newInterval[0] = min(newInterval[0], interval[0])
            newInterval[1] = max(newInterval[1], interval[1])
        }
    }
    result = append(result, newInterval)
    return result
}

medium

A. Appending newInterval multiple times causes duplicates

B. Not updating newInterval correctly during merge

C. Missing return statement

D. Incorrect comparison operators in if conditions

Solution

1. Step 1: Analyze appending logic

   When interval[0] > newInterval[1], newInterval is appended and then replaced by interval. This can cause multiple appends of newInterval.

2. Step 2: Identify duplicate insertion

   Because newInterval is appended inside the loop multiple times, duplicates appear in result.

3. Final Answer:

   Appending newInterval multiple times causes duplicates -> Option A

4. Quick Check:

   Multiple appends = duplicates [OK]

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

Common Mistakes:

• Appending inside loop multiple times
• Not updating newInterval boundaries
• Forgetting to return result

5. You have intervals [[1,3],[6,9]] and want to insert [2,7]. What is the final list after insertion and merging?

hard

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

B. [[1,9]]

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

D. [[1,9],[6,9]]

Solution

1. Step 1: Merge [2,7] with overlapping intervals

   [2,7] overlaps with [1,3] and [6,9]. Merge all three intervals into one covering from min start 1 to max end 9.

2. Step 2: Final merged interval

   The merged interval is [1,9], replacing the original two intervals.

3. Final Answer:

   [[1,9]] -> Option B

4. Quick Check:

   Merge all overlapping = [[1,9]] [OK]

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

Common Mistakes:

• Partial merges leaving overlaps
• Appending without merging
• Incorrect interval boundaries