Teaching Kids Programming – Interval Overlaps via Two Pointer Algorithm


Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a list of closed intervals l0 and another list of intervals l1. Individually, each list is non-overlapping and are sorted in ascending order. Return the overlap of the two intervals sorted in ascending order.

Constraints
n ≤ 100,000 where n is the length of l0
m ≤ 100,000 where m is the length of l1

Example 1
Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
l0 = [
    [1, 3],
    [5, 6],
    [7, 9]
]
l1 = [
    [1, 4],
    [5, 7]
]
Output
[
    [1, 3],
    [5, 6],
    [7, 7]
]
Example 2
Input
l0 = [
    [1, 3],
    [5, 6],
    [7, 9]
]
l1 = [
    [100, 200]
]
Output
[]
l0 = [
    [1, 3],
    [5, 6],
    [7, 9]
]
l1 = [
    [1, 4],
    [5, 7]
]
Output
[
    [1, 3],
    [5, 6],
    [7, 7]
]
Example 2
Input
l0 = [
    [1, 3],
    [5, 6],
    [7, 9]
]
l1 = [
    [100, 200]
]
Output
[]

Two Pointer Algorithm to Compute the Interval Overlapping

Let’s go through the intervals from left to right and consider if two intervals are overlapping by checking the max(starts) and min(ends). Then move the pointer which has a smaller end.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def solve(self, A, B):
        ans = []
        i = 0
        j = 0
        while i < len(A) and j < len(B):
            start = max(A[i][0], B[j][0])
            end = min(A[i][1], B[j][1])
            if start <= end:
                ans.append([start, end])
            if A[i][1] < B[j][1]:
                i += 1
            else:
                j += 1
        return ans
class Solution:
    def solve(self, A, B):
        ans = []
        i = 0
        j = 0
        while i < len(A) and j < len(B):
            start = max(A[i][0], B[j][0])
            end = min(A[i][1], B[j][1])
            if start <= end:
                ans.append([start, end])
            if A[i][1] < B[j][1]:
                i += 1
            else:
                j += 1
        return ans

Time complexity is O(N+M) where N and M are the lengths of two intervals lists – the space complexity is O(1) if we don’t consider the returned list as additional space.

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
319 words
Last Post: GoLang: Insert into a Binary Search Tree via Recursion
Next Post: Teaching Kids Programming - Substrings of Size Three with Distinct Characters

The Permanent URL is: Teaching Kids Programming – Interval Overlaps via Two Pointer Algorithm

Leave a Reply