Last updated on January 19th, 2025 at 05:45 pm

Here, we see an Insert Interval LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Array, Sort

Companies

Facebook, Google, LinkedIn

Level of Question

Medium

Insert Interval LeetCode Solution

1. Problem Statement

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 new Interval = [start, end] that represents the start and end of another interval.

Insert new Interval 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.

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

Example 2:
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Merge Intervals”. This pattern is commonly used when working with overlapping intervals, where the goal is to merge or manipulate intervals based on their start and end points.

3. Code Implementation in Different Languages

3.1 Insert Interval C++

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int n = intervals.size(), i = 0;
        vector<vector<int>> res;
        
        while(i < n && intervals[i][1] < newInterval[0])    res.push_back(intervals[i++]);
		
        while(i < n && newInterval[1] >= intervals[i][0]){
            newInterval[0] = min(newInterval[0], intervals[i][0]);
            newInterval[1] = max(newInterval[1], intervals[i][1]);
            i++;
        }
        res.push_back(newInterval);
        while(i < n)    res.push_back(intervals[i++]);
        return res;        
    }
};

3.2 Insert Interval Java

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        for(int[] slot : intervals)
        {
            if(newInterval[1] < slot[0])
            {
                result.add(newInterval);
                newInterval = slot;
            } 
            else if(slot[1] < newInterval[0])
            {
                result.add(slot);
            } 
            else {
                newInterval[0] = Math.min(newInterval[0],slot[0]);
                newInterval[1] = Math.max(newInterval[1],slot[1]);
            }
        }
        result.add(newInterval);
        return result.toArray(new int[result.size()][]);        
    }
}

3.3 Insert Interval JavaScript

var insert = function(intervals, newInterval) {
    const result = [];
    for (let i = 0; i < intervals.length; i++) {
        let interval = intervals[i];
        if (Math.max(interval[0], newInterval[0]) <= Math.min(interval[1], newInterval[1])) {
            newInterval = [Math.min(interval[0], newInterval[0]), Math.max(interval[1], newInterval[1])];
            continue;
        }
        if (interval[0] > newInterval[1]) {
            result.push(newInterval, ...intervals.slice(i));
            return result;
        }
        result.push(interval);
    }
    result.push(newInterval);
    return result; 
};

3.4 Insert Interval Python

class Solution(object):
    def insert(self, intervals, newInterval):
        START, END = 0, 1
        s, e = newInterval[START], newInterval[END]
        left, right = [], []
        for cur_interval in intervals:
            if cur_interval[END] < s:
                left += [ cur_interval ]
            elif cur_interval[START] > e:
                right += [ cur_interval ]
            else:
                s = min(s, cur_interval[START])
                e = max(e, cur_interval[END])
        return left + [ [s, e] ] + right  

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n)	O(n)
Java	O(n)	O(n)
JavaScript	O(n)	O(n)
Python	O(n)	O(n)

• The algorithm is efficient because it processes the intervals in a single pass.
• The use of the “Merge Intervals” pattern ensures that overlapping intervals are handled correctly and efficiently.
• The space complexity is proportional to the size of the input because the result is stored in a new data structure.