LeetCode 986: Interval List Intersections Solution

Master LeetCode problem 986 (Interval List Intersections), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

986. Interval List Intersections

Medium

Array Two Pointers Line Sweep

Problem Explanation

Explanation

To find the intersection of two lists of closed intervals, we can iterate through the intervals of both lists and check for overlaps. We can then construct the resulting list of intersections. The key idea is to find the intersection of two intervals by comparing their start and end points.

Start with two pointers, i pointing to the current interval in firstList and j pointing to the current interval in secondList.
Check for overlap between the intervals at indices i and j. If there is an overlap, add the intersection to the result.
Move the pointer of the interval with the smaller end value.
Repeat steps 2 and 3 until we reach the end of either list.

Time Complexity: O(m + n) where m and n are the lengths of the two input lists. Space Complexity: O(m + n) to store the resulting list of intersections.

Solution Code

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

        while (i < firstList.length && j < secondList.length) {
            int start = Math.max(firstList[i][0], secondList[j][0]);
            int end = Math.min(firstList[i][1], secondList[j][1]);

            if (start <= end) {
                result.add(new int[]{start, end});
            }

            if (firstList[i][1] < secondList[j][1]) {
                i++;
            } else {
                j++;
            }
        }

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 986 (Interval List Intersections)?

This page provides optimized solutions for LeetCode problem 986 (Interval List Intersections) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 986 (Interval List Intersections)?

The time complexity for LeetCode 986 (Interval List Intersections) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 986 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 986 in Java, C++, or Python.

Back to LeetCode Solutions