986. Interval List Intersections LeetCode Solution

Last updated: February 21, 2025

In this guide, you will get 986. Interval List Intersections LeetCode Solution with the best time and space complexity. The solution to Interval List Intersections problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Interval List Intersections solution in C++
Interval List Intersections solution in Java
Interval List Intersections solution in Python
Additional Resources

986. Interval List Intersections LeetCode Solution image

Problem Statement of Interval List Intersections

You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. 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 = 1
0 <= starti < endi <= 109
endi < starti+1
0 <= startj < endj <= 109
endj < startj+1

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

986. Interval List Intersections LeetCode Solution in C++

class Solution {
 public:
  vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList,
                                           vector<vector<int>>& secondList) {
    vector<vector<int>> ans;
    short i = 0;
    short j = 0;

    while (i < firstList.size() && j < secondList.size()) {
      // lo := the start of the intersection
      // hi := the end of the intersection
      const int lo = max(firstList[i][0], secondList[j][0]);
      const int hi = min(firstList[i][1], secondList[j][1]);
      if (lo <= hi)
        ans.push_back({lo, hi});
      firstList[i][1] < secondList[j][1] ? ++i : ++j;
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

986. Interval List Intersections LeetCode Solution in Java

class Solution {
  public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
    List<int[]> ans = new ArrayList<>();
    short i = 0;
    short j = 0;

    while (i < firstList.length && j < secondList.length) {
      // lo := the start of the intersection
      // hi := the end of the intersection
      final int lo = Math.max(firstList[i][0], secondList[j][0]);
      final int hi = Math.min(firstList[i][1], secondList[j][1]);
      if (lo <= hi)
        ans.add(new int[] {lo, hi});
      if (firstList[i][1] < secondList[j][1])
        ++i;
      else
        ++j;
    }

    return ans.toArray(new int[ans.size()][]);
  }
}
// code provided by PROGIEZ

986. Interval List Intersections LeetCode Solution in Python

class Solution:
  def intervalIntersection(self, firstList: list[list[int]],
                           secondList: list[list[int]]) -> list[list[int]]:
    ans = []
    i = 0
    j = 0

    while i < len(firstList) and j < len(secondList):
      # lo := the start of the intersection
      # hi := the end of the intersection
      lo = max(firstlist[i][0], secondlist[j][0])
      hi = min(firstlist[i][1], secondlist[j][1])
      if lo <= hi:
        ans.append([lo, hi])
      if firstlist[i][1] < secondlist[j][1]:
        i += 1
      else:
        j += 1

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents