15. Insert Interval

βœ… GFG solution to the Insert Interval problem: efficiently insert and merge overlapping intervals in a sorted array using linear traversal technique. πŸš€

The problem can be found at the following link: πŸ”— Question Link

🧩 Problem Description

Geek has an array of non-overlapping intervals intervals[][] where intervals[i] = [starti, endi] represent the start and the end of the ith event and intervals is sorted in ascending order by starti. He wants to add a new interval newInterval[] = [newStart, newEnd] where newStart and newEnd represent the start and end of this interval.

Help Geek to insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

πŸ“˜ Examples

Example 1

Input: intervals[][] = [[1, 3], [4, 5], [6, 7], [8, 10]], newInterval[] = [5, 6]
Output: [[1, 3], [4, 7], [8, 10]]
Explanation: The newInterval [5, 6] overlaps with [4, 5] and [6, 7]. 
So, they are merged into one interval [4, 7].

Example 2

Input: intervals[][] = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], newInterval[] = [4, 9]
Output: [[1, 2], [3, 10], [12, 16]]
Explanation: The new interval [4, 9] overlaps with [3, 5], [6, 7] and [8, 10]. 
So, they are merged into one interval [3, 10].

πŸ”’ Constraints

  • $1 \le \text{intervals.size()} \le 10^5$

  • $0 \le \text{starti} \le \text{endi} \le 10^9$

  • $0 \le \text{newStart} \le \text{newEnd} \le 10^9$

βœ… My Approach

The optimal approach uses Linear Traversal with Three-Phase Processing to efficiently handle interval insertion and merging:

Three-Phase Linear Processing

  1. Phase 1 - Add Non-overlapping Intervals Before:

    • Traverse intervals from left and add all intervals that end before newInterval starts.

    • Condition: intervals[i][1] < newInterval[0]

    • These intervals don't overlap with newInterval.

  2. Phase 2 - Merge Overlapping Intervals:

    • Process all intervals that overlap with newInterval.

    • Condition: intervals[i][0] <= newInterval[1]

    • Merge by taking minimum start and maximum end.

    • Update newInterval bounds during merging process.

  3. Phase 3 - Add Remaining Intervals:

    • Add all remaining intervals after the overlap region.

    • These intervals start after newInterval ends.

  4. Insert Merged Interval:

    • Add the final merged newInterval between phases 2 and 3.

πŸ“ Time and Auxiliary Space Complexity

  • Expected Time Complexity: O(n), where n is the number of intervals. We traverse the intervals array exactly once, processing each interval in constant time.

  • Expected Auxiliary Space Complexity: O(n), where n is the number of intervals. In the worst case, we need to store all intervals in the result array. The algorithm uses constant extra space beyond the output storage.

πŸ”§ Code (C)

Interval* insertInterval(Interval* intervals, int intervalsSize, Interval newInterval, int* returnSize) {
    Interval* result = (Interval*)malloc((intervalsSize + 1) * sizeof(Interval));
    int i = 0, idx = 0;
    while (i < intervalsSize && intervals[i].end < newInterval.start)
        result[idx++] = intervals[i++];
    
    while (i < intervalsSize && intervals[i].start <= newInterval.end) {
        newInterval.start = (intervals[i].start < newInterval.start) ? intervals[i].start : newInterval.start;
        newInterval.end = (intervals[i].end > newInterval.end) ? intervals[i].end : newInterval.end;
        i++;
    }
    result[idx++] = newInterval;
    
    while (i < intervalsSize) result[idx++] = intervals[i++];
    
    *returnSize = idx;
    return result;
}

πŸ§‘β€πŸ’» Code (C++)

class Solution {
public:
    vector<vector<int>> insertInterval(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> result;
        int i = 0, n = intervals.size();
        
        while (i < n && intervals[i][1] < newInterval[0]) result.push_back(intervals[i++]);
        while (i < n && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = min(newInterval[0], intervals[i][0]);
            newInterval[1] = max(newInterval[1], intervals[i++][1]);
        }
        result.push_back(newInterval);
        while (i < n) result.push_back(intervals[i++]);
        
        return result;
    }
};
⚑ View Alternative Approaches with Code and Analysis

πŸ“Š 2️⃣ Binary Search + Merge Approach

πŸ’‘ Algorithm Steps:

  1. Use binary search to find insertion point for newInterval start.

  2. Use binary search to find all intervals that overlap with newInterval.

  3. Merge overlapping intervals efficiently with single pass.

  4. Construct result with non-overlapping intervals and merged interval.

class Solution {
public:
    vector<vector<int>> insertInterval(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;
        auto it = lower_bound(intervals.begin(), intervals.end(), newInterval, 
            [](const vector<int>& a, const vector<int>& b) { return a[1] < b[0]; });
        res.insert(res.end(), intervals.begin(), it);
        
        while (it != intervals.end() && (*it)[0] <= newInterval[1]) {
            newInterval[0] = min(newInterval[0], (*it)[0]);
            newInterval[1] = max(newInterval[1], (*it)[1]);
            ++it;
        }
        
        res.push_back(newInterval);
        res.insert(res.end(), it, intervals.end());
        return res;
    }
};

πŸ“ Complexity Analysis:

  • Time: ⏱️ O(log n + m) - Binary search + merge overlapping intervals

  • Auxiliary Space: πŸ’Ύ O(1) - Only constant extra space excluding result

βœ… Why This Approach?

  • Efficient for large datasets with few overlaps

  • Leverages STL binary search capabilities

  • Optimal when overlap region is small

πŸ“Š 3️⃣ Single Pass Iterator Approach

πŸ’‘ Algorithm Steps:

  1. Use iterators to traverse intervals array once.

  2. Copy non-overlapping intervals before newInterval directly.

  3. Merge all overlapping intervals in single iteration.

  4. Append remaining intervals after merge region.

class Solution {
public:
    vector<vector<int>> insertInterval(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> ans;
        auto it = intervals.begin();
        while (it != intervals.end() && (*it)[1] < newInterval[0]) 
            ans.push_back(*it++);
        
        while (it != intervals.end() && (*it)[0] <= newInterval[1]) {
            newInterval = {min(newInterval[0], (*it)[0]), max(newInterval[1], (*it)[1])};
            ++it;
        }
        ans.push_back(newInterval);
        ans.insert(ans.end(), it, intervals.end());
        
        return ans;
    }
};

πŸ“ Complexity Analysis:

  • Time: ⏱️ O(n) - Single pass through all intervals

  • Auxiliary Space: πŸ’Ύ O(1) - Constant space excluding result storage

βœ… Why This Approach?

  • Memory efficient with iterator usage

  • Clean STL integration with insert operations

  • Minimal temporary variable usage

πŸ“Š 4️⃣ In-Place Modification Approach

πŸ’‘ Algorithm Steps:

  1. Find the insertion position and overlapping range in one pass.

  2. Merge newInterval with overlapping intervals directly.

  3. Use vector erase and insert operations to modify in-place.

  4. Return reference to modified original vector.

class Solution {
public:
    vector<vector<int>> insertInterval(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int start = 0, end = intervals.size() - 1;
        while (start <= end && intervals[start][1] < newInterval[0]) start++;
        while (end >= start && intervals[end][0] > newInterval[1]) end--;
        
        if (start <= end) {
            newInterval[0] = min(newInterval[0], intervals[start][0]);
            newInterval[1] = max(newInterval[1], intervals[end][1]);
            intervals.erase(intervals.begin() + start, intervals.begin() + end + 1);
        }
        
        intervals.insert(intervals.begin() + start, newInterval);
        return intervals;
    }
};

πŸ“ Complexity Analysis:

  • Time: ⏱️ O(n) - Linear search plus vector operations

  • Auxiliary Space: πŸ’Ύ O(1) - Modifies input vector in-place

βœ… Why This Approach?

  • Space efficient by reusing input vector

  • Good for memory-constrained environments

  • Direct manipulation reduces allocation overhead

πŸ†š πŸ” Comparison of Approaches

πŸš€ Approach

⏱️ Time Complexity

πŸ’Ύ Space Complexity

βœ… Pros

⚠️ Cons

🏷️ Linear Three-Phase

🟒 O(n)

🟑 O(n)

πŸš€ Simple and optimal

πŸ’Ύ Requires result array

πŸ” Binary Search

🟑 O(log n + m)

🟑 O(n)

πŸ“– Efficient for sparse overlaps

πŸ’» Complex STL usage

πŸ“Š Iterator Based

🟒 O(n)

🟑 O(n)

🎯 Clean STL integration

🐌 Iterator overhead

πŸ”„ In-Place

🟒 O(n)

🟒 O(1)

⭐ Memory efficient

πŸ”§ Modifies input

πŸ† Best Choice Recommendation

🎯 Scenario

πŸŽ–οΈ Recommended Approach

πŸ”₯ Performance Rating

πŸ… General use case, interviews

πŸ₯‡ Linear Three-Phase

β˜…β˜…β˜…β˜…β˜…

πŸ“– Large arrays, few overlaps

πŸ₯ˆ Binary Search

β˜…β˜…β˜…β˜…β˜†

πŸ”§ STL preference, modern C++

πŸ₯‰ Iterator Based

β˜…β˜…β˜…β˜…β˜†

🎯 Memory constraints

πŸ… In-Place

β˜…β˜…β˜…β˜…β˜†

β˜• Code (Java)

class Solution {
    public ArrayList<int[]> insertInterval(int[][] intervals, int[] newInterval) {
        ArrayList<int[]> result = new ArrayList<>();
        int i = 0;
        while (i < intervals.length && intervals[i][1] < newInterval[0])
            result.add(intervals[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]);
        }
        result.add(newInterval);
        
        while (i < intervals.length) result.add(intervals[i++]);
        
        return result;
    }
}

🐍 Code (Python)

class Solution:
    def insertInterval(self, intervals, newInterval):
        result = []
        i = 0
        while i < len(intervals) and intervals[i][1] < newInterval[0]:
            result.append(intervals[i])
            i += 1
        
        while i < len(intervals) and intervals[i][0] <= newInterval[1]:
            newInterval[0] = min(newInterval[0], intervals[i][0])
            newInterval[1] = max(newInterval[1], intervals[i][1])
            i += 1
        result.append(newInterval)
        
        while i < len(intervals):
            result.append(intervals[i])
            i += 1
            
        return result

🧠 Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: πŸ“¬ Any Questions?. Let's make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐


πŸ“Visitor Count

Visitor counter

Last updated