Coding Interview Questions | Insert Interval

January 6th, 2024

Insert Interval Problem Introduction:

This summary will talk about my solution to the insert interval problem as seen on leetcode here.

How do you solve the Insert Interval Problem in O(n) time?:

Solution:

const isOverlap = (a: [number, number], b: [number, number]) => {
  return a[1] >= b[0] && b[1] >= a[0];
};

function insert(intervals: number[][], newInterval: number[]): number[][] {
  if (!intervals.length) {
    return [newInterval];
  }
  const overlappingIntervals = Array.from(intervals, () => false);

  // Populate if intervals overlap with new interval
  for (let intervalIdx = 0; intervalIdx < intervals.length; intervalIdx++) {
    const interval = intervals[intervalIdx];
    if (
      isOverlap(interval as [number, number], newInterval as [number, number])
    ) {
      overlappingIntervals[intervalIdx] = true;
    }
  }

  const nonOverlappingIntervals: number[][] = [];
  const hasOverlap = overlappingIntervals.some((overlap) => overlap);

  if (!hasOverlap) {
    let inserted = false;
    for (const interval of intervals) {
      if (interval[0] > newInterval[0] && !inserted) {
        nonOverlappingIntervals.push(newInterval);
        inserted = true;
      }
      nonOverlappingIntervals.push(interval);
    }

    if (!inserted) {
      nonOverlappingIntervals.push(newInterval);
    }

    return nonOverlappingIntervals;
  }

  let intervalIdx = 0;
  while (intervalIdx < intervals.length) {
    if (!overlappingIntervals[intervalIdx]) {
      nonOverlappingIntervals.push(intervals[intervalIdx]);
      intervalIdx++;
    } else {
      const mergeIntervalStart = Math.min(
        intervals[intervalIdx][0],
        newInterval[0]
      );

      // Iterate until the new interval does not overlap with old intervals
      while (overlappingIntervals[intervalIdx]) {
        intervalIdx++;
      }
      const mergeIntervalEnd = Math.max(
        intervals[intervalIdx - 1][1],
        newInterval[1]
      );
      nonOverlappingIntervals.push([mergeIntervalStart, mergeIntervalEnd]);
    }
  }

  return nonOverlappingIntervals;
}

Insert Interval Solution Summary:

Below is a breakdown of the key aspects of the solution above:

1. Base Case Handling: The algorithm checks if the array of intervals is empty. If so, it directly returns an array containing the new interval, as there are no existing intervals to consider.

2. Overlap Detection: The solution defines a function isOverlap to check if two intervals overlap. It uses this function to identify intervals in the given array that overlap with the new interval.

3. Non-Overlap Insertion: If there is no overlap with any existing intervals, the algorithm inserts the new interval into the correct position in the sorted array of intervals while maintaining the order.

4. Overlap Resolution: In case of overlaps, the algorithm iterates through the existing intervals, merging overlapping ones with the new interval. It calculates the merged interval’s start and end by considering the minimum start and maximum end among the overlapping intervals.

Complexities:

1. Time Complexity: The time complexity of the solution is O(n), where n is the number of intervals. This is because the algorithm iterates through the intervals once.

2. Space Complexity: The space complexity is O(n), as additional space is used to store information about overlapping intervals.