Solving LeetCode’s Interval List Intersections
In this article, we will be solving LeetCode’s Interval List Intersections in JavaScript. This problem uses the two-pointer approach. The two-pointer approach is usually used to keep track of array or string indices to solve a problem. One variation is one pointer being slow and the other pointer being fast meaning that the fast pointer is ahead of the slow pointer while traversing through the array/string. A classic example of this is to remove duplicates from a sorted array. Another variation is one pointer starts from the beginning while the other pointer starts from the end. The pointers move toward each other until they both meet. In our approach for this problem, we will be using a pointer for each array that start at the beginning and move them separately based on what conditions are met.
Problem
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
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]]
Solution
Explanation
This can be very confusing so I will break it down as much as I can. We have one pointer for array firstList and one pointer for array secondList. In the first time in our while loop, we grab the largest start point of the first intervals [0,2] and [1,5]. The largest start point comes from the secondList as 1. We then grab the smallest endpoint from the same intervals which is 2. We want the largest start point and the smallest endpoint of the intervals because that is section of overlap. They cannot intersect if only one exists at that point. For example, if we chose the smallest start point, only the interval in the firstList exists, secondList does not start until 1.
We then check if these intervals overlap. We can see that the largest start point (1) is less than the smallest endpoint (2). [1,2] is the overlap section of [0,2] and [1,5] and we add it to our result array.
We want to advance the current interval with the lowest endpoint value to its next interval. Since the secondList interval ([1,5]) extends farther out than the firstList interval ([0,2]), we keep the secondList interval the same for the next comparison in case it overlaps with the next firstList interval ([5,10]).
The firstList interval is now [5,10] and the secondList interval is [1,5]. Because the endpoint of the secondList interval is 5 and the beginning of the firstList interval is 5, we have the intersection in range from [5, 5] to put in our result array. secondList endpoint is smaller so we move it to its next interval [8,12].
We keep doing this pattern until we have looped through both arrays and then return our result array. Our result array looks like:
[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]Resources
LeetCode Problem: https://leetcode.com/problems/interval-list-intersections/
https://algodaily.com/lessons/using-the-two-pointer-technique
More content at plainenglish.io
