Interval List Intersections

MEDIUM

Description

You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [start_i, end_i] and secondList[j] = [start_j, end_j]. Each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

A closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.

The intersection of two closed intervals is a set of real numbers that are either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].

Example 1:

Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Example 2:

Input: firstList = [[1,3],[5,9]], secondList = []
Output: []

Constraints:

0 <= firstList.length, secondList.length <= 1000
firstList.length + secondList.length >= 1
0 <= start_i < end_i <= 10⁹
end_i < start_i+1
0 <= start_j < end_j <= 10⁹
end_j < start_j+1

Approaches

Checkout 2 different approaches to solve Interval List Intersections. Click on different approaches to view the approach and algorithm in detail.

Brute Force (Nested Loops)

This approach involves iterating through every interval in the first list and comparing it with every interval in the second list to find all possible intersections. It's straightforward but inefficient as it doesn't leverage the sorted nature of the input lists.

Algorithm

Initialize an empty list, result, to store the intersection intervals.
Use a nested loop. The outer loop iterates through each interval A from firstList.
The inner loop iterates through each interval B from secondList.
For each pair (A, B), calculate the potential intersection. The start of the intersection is the maximum of the start points of A and B. The end of the intersection is the minimum of the end points of A and B.
Let A = [startA, endA] and B = [startB, endB]. The intersection is [max(startA, startB), min(endA, endB)].
If the calculated start is less than or equal to the calculated end, it's a valid, non-empty intersection. Add this new interval to the result list.
After both loops complete, return the result list.

The core idea of the brute-force approach is to check every possible pair of intervals, one from each list. We use nested loops to achieve this. The outer loop iterates through firstList, and the inner loop iterates through secondList. For each pair of intervals, we calculate their potential intersection.

An intersection between two intervals [a, b] and [c, d] exists if they overlap. The resulting intersection interval would be [max(a, c), min(b, d)]. A valid intersection exists only if the start of this new interval is less than or equal to its end. If it is, we add this intersection interval to our result list.

This method is exhaustive and guarantees finding all intersections, but it performs many unnecessary comparisons. For example, if firstList[i] ends before secondList[j] starts, this approach will still check firstList[i] against all subsequent intervals in secondList unnecessarily.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> intersections = new ArrayList<>();
        if (firstList == null || firstList.length == 0 || secondList == null || secondList.length == 0) {
            return new int[0][];
        }

        for (int[] interval1 : firstList) {
            for (int[] interval2 : secondList) {
                // Calculate the intersection
                int start = Math.max(interval1[0], interval2[0]);
                int end = Math.min(interval1[1], interval2[1]);

                // Check if there is a valid overlap
                if (start <= end) {
                    intersections.add(new int[]{start, end});
                }
            }
        }

        return intersections.toArray(new int[intersections.size()][]);
    }
}

Complexity Analysis

Time Complexity: O(N * M), where N is the length of `firstList` and M is the length of `secondList`. This is because for each of the N intervals in the first list, we iterate through all M intervals in the second list.Space Complexity: O(K), where K is the number of intersections found. This space is used to store the resulting list of intervals. In the worst case, K can be up to N + M. If the output array is not considered, the space complexity is O(1).

Pros and Cons

Pros:

Simple to conceptualize and implement.
Correctly finds all intersections regardless of input order (though the problem specifies sorted input).

Cons:

Highly inefficient, especially for large lists, with a quadratic time complexity.
Ignores the crucial information that the input lists are sorted and disjoint, leading to many redundant comparisons.

Code Solutions

Checking out 3 solutions in different languages for Interval List Intersections. Click on different languages to view the code.

class Solution {
public
  int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
    List<int[]> ans = new ArrayList<>();
    int m = firstList.length, n = secondList.length;
    for (int i = 0, j = 0; i < m && j < n;) {
      int l = Math.max(firstList[i][0], secondList[j][0]);
      int r = Math.min(firstList[i][1], secondList[j][1]);
      if (l <= r) {
        ans.add(new int[]{l, r});
      }
      if (firstList[i][1] < secondList[j][1]) {
        ++i;
      } else {
        ++j;
      }
    }
    return ans.toArray(new int[ans.size()][]);
  }
}

Video Solution

Watch the video walkthrough for Interval List Intersections

Patterns:

Two PointersLine Sweep

Data Structures:

Array

Companies:

DoorDash |Yandex |Verkada |Nuro |