100 Days to crack FAANG interview Day 6— Insert Interval

Welcome to Day 6 of my FAANG interview preparation journey! This is a medium-level problem on 2D Arrays.

Problem Statement:

Insert Interval — https://leetcode.com/problems/insert-interval/

Insert a new interval(newInterval = [start, end]) into a list of non-overlapping intervals(intervals[i] = [start, end]) sorted in ascending order.

Example :

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

Approach

The approach is fairly straightforward. Maintain a resultList of int[]. Loop through the input intervals and compare each interval with the newInterval.

If the newInterval is before intervals[i], add the newInterval to the resultList and then add the remaining elements of the intervals array.

If intervals[i] is before newInterval, add intervals[i] to the resultList and then continue the loop.

If there is an overlap between the newInterval and intervals[i], merge them, assign the merged interval to newInterval, and then continue the loop.

Complexity

Space Complexity: A new List<int[]> is used to store the result, so the space complexity is O(n)

Time Complexity: We loop through the input intervals array and in each iteration we perform comparison and assignments, which take constant time. Therefore, the overall time complexity is O(n)

Code Implementation

public static int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> resultList = new ArrayList<>();
		
    for (int i=0; i<intervals.length;i++) {
      if(newInterval[1] < intervals[i][0]) {
        resultList.add(newInterval);
        newInterval = intervals[i];
      } else if (intervals[i][1] < newInterval[0]) {
        resultList.add(intervals[i]);
      } else {
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
      }
    
    resultList.add(newInterval);
    
    int[][] result = new int[resultList.size()][];
    int i = 0;
    for(int[] arr: resultList) {
      result[i++] = arr;
    }
    return result;
  }

Thanks for reading and any feedback is appreciated!

Visit https://100daysofcode.io/ for more content and resources to support your coding journey!