Insert Interval Problem Solved (C++, Java, Python)

 

Interval-related questions are frequently asked in technical interviews. Some of the common questions among them are Insert Interval, Merge Interval, Meeting Room, etc. This article will explore various approaches to solving the Insert Interval Problem, with implementation in C++, Java, and Python.

What is the Insert Interval Problem?

In the Insert Interval problem, you are given an array containing intervals in sorted and non-overlapping intervals, And you are also provided with an additional interval, Now the task is to insert this interval into the array such that the given array will still be sorted and in a non-overlapping interval. Return a new array as a result.

Let us understand this with an example:

• Consider you have an array arr = [[2,5], [6,8], [10,13]]. Intervals in the given array look like this,

• And an additional interval = [4,7] will look like this

• After overlapping that new interval into the given array the new array will be 

• So the resultant arr = [[2,8], [10,13]].

Brute Force Approach: Using Sorting 

Before using this method, you may have to go through some sorting algorithms and understand their time complexity. This problem incorporates concepts from sorting.

Sorting can be used to solve the Insert Interval problem. First, create a new array, then copy the given array into the new array result and insert the new interval into the original array. Then sort the whole array and merge the intervals if they are overlapping.

We can take an example:

• Let the given array be [[2,5], [6,8], [10,13]] and interval be interval= [4,7]

•  Now create a new array ans, copy the values in the array, and then push the interval into the ans. 

• Now sort the new array ans, it will look like this

• Now merge the overlapping intervals in this case overlapping intervals are [2,5], [4,7], [6,8], and they are all combined into a single interval [2,8].
• The new array ans=[[2,8], [10,13]] will look like this 

The Time complexity of solving the problem using sorting is Nlog(N) where N is the size of the array. While sorting, we need Nlog(N) to sort the array and N to merge the whole array into a single array, so the total time will be (Nlog(N)+ N) ~  Nlog(N). The Space Complexity is O(N) for the new array as it stores all the values of the array.

Optimized Approach to Solve It

As in the above approach, we are making use of sorting which increases our time complexity to O(Nlog(N)) which can be reduced by taking advantage of the sorted array as we know that the given array arr is already sorted. So insert the element into the resultant array and compare the values. This can easily be done by following the steps,

• First, create a resultant array, so your interval, array, and the new resultant array will look like this 

• Second step, we will keep on inserting the values from the array i.e. arr into the ans if interval[0] > arr[i][1] where i is the current index. So in this case, as arr[0][1] is greater than interval[0] we will not push the interval into the array.

• In the third step, we will keep on updating the interval till arr[i][0] < interval[1], and if not we will add that interval to the ans. 

• At last, we will add all the remaining arr intervals into the ans and return ans as a resultant array. As in this case only interval left is [10,13] so the resultant array will be ans= [[2,8], [10,13]].

C++ Code

Here is the C++ program to solve the Insert Interval problem:

#include <bits/stdc++.h>
using namespace std;

int main(){

    vector<vector<int>>arr = {{2,5},{6,8},{10,13}};
    vector<int>interval={4,7};
    vector<vector<int>>ans;

    int n= arr.size(), i=0;  // n is the size of arr 

    // keep on pushing the intervals of array into the ans till they are not overlapping and index is  less than the current size of array

    while(i<n && (arr[i][1] < interval[0])){
        ans.push_back(arr[i]);
        i++;
    }

    // keep updating values till they are overlapping
    while(i<n && (arr[i][0] <= interval[1])){
        interval[0] = min(arr[i][0], interval[0]);
        interval[1] = max(arr[i][1],interval[1]);
        i++;
    }

    ans.push_back(interval);

    while(i<n){
        ans.push_back(arr[i]);
        i++;
    }

    for(int j=0;j<ans.size();j++){
        cout<<ans[j][0]<<" "<<ans[j][1]<<endl;
    }
    // the array in this case is 
    // Output ans={{2,8}, {10,13}}

    return 0;

}

Java Code

Here is the implementation in Java:

import java.util.ArrayList;

class MergeIntervals {

    public static void main(String[] args) {
        ArrayList<ArrayList<Integer>> arr = new ArrayList<>();
        arr.add(new ArrayList<Integer>() {{ add(2); add(5); }});
        arr.add(new ArrayList<Integer>() {{ add(6); add(8); }});
        arr.add(new ArrayList<Integer>() {{ add(10); add(13); }});

        ArrayList<Integer> interval = new ArrayList<Integer>() {{ add(4); add(7); }};
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();

        int n = arr.size();
        int i = 0;

        while (i < n && arr.get(i).get(1) < interval.get(0)) {
            ans.add(arr.get(i));
            i++;
        }

        while (i < n && arr.get(i).get(0) <= interval.get(1)) {
            interval.set(0, Math.min(arr.get(i).get(0), interval.get(0)));
            interval.set(1, Math.max(arr.get(i).get(1), interval.get(1)));
            i++;
        }

        ans.add(interval);

        while (i < n) {
            ans.add(arr.get(i));
            i++;
        }

        for (ArrayList<Integer> pair : ans) {
            System.out.println(pair.get(0) + " " + pair.get(1));
        }
    }
}

Python Code

You can do it in Python as well:

arr = [[2, 5], [6, 8], [10, 13]]
interval = [4, 7]
ans = []

n = len(arr)
i = 0

# Keep pushing intervals into ans until they are not overlapping and index is less than the current size of an array
while i < n and arr[i][1] < interval[0]:
    ans.append(arr[i])
    i += 1

# Keep updating values until intervals are overlapping
while i < n and arr[i][0] <= interval[1]:
    interval[0] = min(arr[i][0], interval[0])
    interval[1] = max(arr[i][1], interval[1])
    i += 1

ans.append(interval)

# Push the remaining intervals into ans
while i < n:
    ans.append(arr[i])
    i += 1

# Print the result
for j in ans:
    print(j[0], j[1])

Output:

2 8
10 13

In the above approach the time complexity will be O(N) as in this case, we are iterating over the whole array only once. Space Complexity will also be O(N) as we are making an array ans as a resultant array.

Here is a small comparison of both the approaches:

Conclusion

We solved the Insert Interval problem from leetcode in this article, as well as found out how can we approach a problem through different methods. Practice more similar problems to get a good grasp of this concept.