Data Structures & Algorithms in Java – Intervals- Insert new interval

Problem:

Given an array of sorted intervals , insert a new interval at the correct position. If the new interval overlaps with the previous interval merge them into one interval and do the same for the subsequent intervals after the new interval.

For example,

Given the below array of intervals:

[[1,2] ,[3,5],[6,7],[8,10],[12,16]] and

the new interval

[4,8]

The output should be [[1,2],[3,10],[12,16]]

Try out the solution here:

https://leetcode.com/problems/insert-interval/

Solution:

This problem can be solved in three steps.

STEP 1:

Add all the intervals which start before the new interval to an output array

STEP 2:

See if the last element in the output array overlaps with the new interval.

That is if the start of the new interval is less than or equal to the end of the last element in the output array then merge them . Make the new end the maximum of either of the intervals.

STEP 3:

For subsequent intervals keep adding them or merging them if the intervals overlap.

ALGORITHM:

STEP 1: If length of the input array is zero , return an array with only the new interval in it.

STEP 2: Create an output array

STEP 3: Initialize an index variable to iterate through the input array.

STEP 4: Add all intervals which start earlier than the new interval to the output array

STEP 5: If the output size is less than zero then it means the new interval is less than all other intervals in the given input , so add it first to the output

STEP 6: If the output size is greater than zero then check if the end of the last element in the output overlaps with the start of the new interval .If YES , merge them else add the new interval to the output

STEP 7: For the remaining intervals in the input , add or merge to the output based on whether the end of the last interval in the output and the start of the new interval overlap.

STEP 8: Return the output.

Code:

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        
        if(intervals.length == 0) return new int[][]{newInterval};
        
        List<int[]> output = new ArrayList<int[]>();
        
        int index = 0;
        
        
            
            
            while(index < intervals.length && intervals[index][0] <= newInterval[0]){
                
                
                output.add(intervals[index++]);
                
                
            }
        
        
     if(output.size() > 0){
        int[] last = output.get(output.size()-1);
        
 
        
        if(newInterval[0] <= last[1]){
            
            
            output.get(index-1)[1] = Math.max(newInterval[1],output.get(output.size()-1)[1]);
        }else{
            
            
            output.add(newInterval);
        }
        
     }else{
         
         
         output.add(newInterval);
     }
     
        while(index < intervals.length){
            
            
            int lastIndex = output.size() - 1;
            if(intervals[index][0] <= output.get(lastIndex)[1]){
                
                
                output.get(lastIndex)[1] = Math.max(intervals[index++][1],output.get(lastIndex)[1]);
                
            }else{
                
                
                output.add(intervals[index++]);
                
                
            }
            
            
        }
        
    
        return output.toArray(new int[output.size()][2]);
    }
}

Time complexity is O(n) where n is the size of the input array.

Space complexity is also O(n) since we create an output array of the same size.

That’s it!