Insert Interval - Practice Coding Problems

Insert Interval - Problem

Array Medium

You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i] represent the start and the end of the i-th interval and intervals is sorted in ascending order by start_i.

You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by start_i and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Input & Output

Example 1 — Basic Overlap

$ Input: intervals = [[1,3],[6,9]], newInterval = [2,5]

› Output: [[1,5],[6,9]]

💡 Note: newInterval [2,5] overlaps with [1,3], so we merge them to [1,5]. The interval [6,9] doesn't overlap, so it remains unchanged.

Example 2 — Multiple Overlaps

$ Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]

› Output: [[1,2],[3,10],[12,16]]

💡 Note: newInterval [4,8] overlaps with [3,5], [6,7], and [8,10], so we merge them all into [3,10]. Intervals [1,2] and [12,16] remain separate.

Example 3 — No Overlap

$ Input: intervals = [[1,5]], newInterval = [6,8]

› Output: [[1,5],[6,8]]

💡 Note: newInterval [6,8] doesn't overlap with [1,5] since 6 > 5, so we simply add it to the end.

Constraints

0 ≤ intervals.length ≤ 10⁴
intervals[i].length == 2
0 ≤ start_i ≤ end_i ≤ 10⁵
intervals is sorted by start_i in ascending order
newInterval.length == 2
0 ≤ start ≤ end ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Sorted non-overlapping intervals + new interval to insert

Process

Find overlaps and merge intervals while maintaining sorted order

Output

New sorted array with merged intervals

Key Takeaway

🎯 Key Insight: Process intervals in three phases - before, overlapping, and after the new interval

Asked in

f Facebook 45 G Google 38 a Amazon 32 M Microsoft 28

The key insight is to process intervals in three distinct phases: add non-overlapping intervals before the new interval, merge all overlapping intervals with the new interval, then add remaining intervals. The optimal approach uses a single linear scan through the intervals array. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Overlaps	O(n²)	O(n)	Insert new interval and check all pairs for overlaps to merge
One Pass Linear Scan	O(n)	O(n)	Single pass through intervals with three phases: before, overlapping, after

Brute Force - Check All Overlaps — Algorithm Steps

Step 1: Insert newInterval at correct sorted position
Step 2: Scan all pairs of intervals to find overlaps
Step 3: Merge overlapping intervals and repeat until no more overlaps

Visualization

Tap to expand

Step-by-Step Walkthrough

Insert

Insert newInterval [2,5] into sorted position

Scan

Check all adjacent pairs for overlaps

Merge

Merge overlapping intervals [1,3] and [2,5]

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int** solution(int** intervals, int intervalsSize, int* intervalColSize, int* newInterval, int newIntervalSize, int* returnSize, int** returnColumnSizes) {
    int** result = (int**)malloc(sizeof(int*) * (intervalsSize + 1));
    int resultSize = 0;
    int inserted = 0;
    
    // Insert newInterval at correct position
    for (int i = 0; i < intervalsSize; i++) {
        if (!inserted && newInterval[0] <= intervals[i][0]) {
            result[resultSize] = (int*)malloc(sizeof(int) * 2);
            result[resultSize][0] = newInterval[0];
            result[resultSize][1] = newInterval[1];
            resultSize++;
            inserted = 1;
        }
        result[resultSize] = (int*)malloc(sizeof(int) * 2);
        result[resultSize][0] = intervals[i][0];
        result[resultSize][1] = intervals[i][1];
        resultSize++;
    }
    
    if (!inserted) {
        result[resultSize] = (int*)malloc(sizeof(int) * 2);
        result[resultSize][0] = newInterval[0];
        result[resultSize][1] = newInterval[1];
        resultSize++;
    }
    
    // Merge overlapping intervals
    int** merged = (int**)malloc(sizeof(int*) * resultSize);
    int mergedSize = 0;
    
    for (int i = 0; i < resultSize; i++) {
        if (mergedSize == 0 || merged[mergedSize-1][1] < result[i][0]) {
            merged[mergedSize] = (int*)malloc(sizeof(int) * 2);
            merged[mergedSize][0] = result[i][0];
            merged[mergedSize][1] = result[i][1];
            mergedSize++;
        } else {
            if (merged[mergedSize-1][1] < result[i][1]) {
                merged[mergedSize-1][1] = result[i][1];
            }
        }
    }
    
    // Clean up temporary result array
    for (int i = 0; i < resultSize; i++) {
        free(result[i]);
    }
    free(result);
    
    *returnSize = mergedSize;
    *returnColumnSizes = (int*)malloc(sizeof(int) * mergedSize);
    for (int i = 0; i < mergedSize; i++) {
        (*returnColumnSizes)[i] = 2;
    }
    
    return merged;
}

int main() {
    // Simplified parsing for demonstration
    int intervals[][2] = {{1,3},{6,9}};
    int* intervalPtrs[2] = {intervals[0], intervals[1]};
    int newInterval[] = {2, 5};
    int returnSize, *returnColumnSizes;
    
    int** result = solution(intervalPtrs, 2, NULL, newInterval, 2, &returnSize, &returnColumnSizes);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("[%d,%d]", result[i][0], result[i][1]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Inserting takes O(n), then checking all pairs for overlaps takes O(n²) in worst case

⚠ Quadratic Growth

Space Complexity

O(n)

Creates new result array to store merged intervals

⚡ Linearithmic Space

125.0K Views

High Frequency

~25 min Avg. Time

3.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Overlaps — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler