Interval List Intersections - Practice Coding Problems

Interval List Intersections - Problem

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].

Input & Output

Example 1 — Basic Intersection

$ 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]]

💡 Note: Step by step: [0,2]∩[1,5]=[1,2], [5,10]∩[1,5]=[5,5], [5,10]∩[8,12]=[8,10], [13,23]∩[15,24]=[15,23], [24,25]∩[15,24]=[24,24], [24,25]∩[25,26]=[25,25]

Example 2 — No Intersections

$ Input: firstList = [[1,3],[5,9]], secondList = [[4,4],[10,12]]

› Output: []

💡 Note: No overlap: [1,3] and [4,4] don't intersect, [1,3] and [10,12] don't intersect, [5,9] and [4,4] don't intersect, [5,9] and [10,12] don't intersect

Example 3 — Single Point Intersection

$ Input: firstList = [[1,7]], secondList = [[3,10]]

› Output: [[3,7]]

💡 Note: Overlap exists: max(1,3)=3, min(7,10)=7, so intersection is [3,7]

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

Visualization

Tap to expand

Understanding the Visualization

Input

Two sorted lists of disjoint intervals

Process

Find overlapping regions between intervals

Output

List of intersection intervals

Key Takeaway

🎯 Key Insight: Use two pointers and advance whichever interval ends first to efficiently find all intersections in O(m+n) time

Asked in

G Google 45 f Facebook 38 a Amazon 32 M Microsoft 28

The key insight is that two intervals [a,b] and [c,d] intersect if max(a,c) ≤ min(b,d). Best approach uses two pointers to traverse both sorted lists simultaneously, advancing the pointer of whichever interval ends first. Time: O(m+n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers - Optimal Solution	O(m+n)	O(1)	Use two pointers to traverse both lists simultaneously, leveraging sorted order
Brute Force - Compare All Pairs	O(m×n)	O(1)	Check every interval in firstList against every interval in secondList

Two Pointers - Optimal Solution — Algorithm Steps

Initialize two pointers, one for each list
Calculate intersection of current intervals
Advance pointer of interval that ends first
Continue until one list is exhausted

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Pointers

Start with i=0, j=0 pointing to first intervals

Find Intersection

Calculate overlap and add to result if valid

Advance Pointer

Move pointer of interval that ends first

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

int min(int a, int b) {
    return (a < b) ? a : b;
}

void solution(int firstList[][2], int m, int secondList[][2], int n, int result[][2], int* resultSize) {
    *resultSize = 0;
    int i = 0, j = 0;
    
    while (i < m && j < n) {
        // Find intersection
        int start = max(firstList[i][0], secondList[j][0]);
        int end = min(firstList[i][1], secondList[j][1]);
        
        // If valid intersection exists
        if (start <= end) {
            result[*resultSize][0] = start;
            result[*resultSize][1] = end;
            (*resultSize)++;
        }
        
        // Move pointer of interval that ends first
        if (firstList[i][1] < secondList[j][1]) {
            i++;
        } else {
            j++;
        }
    }
}

int main() {
    // Simple parsing for demo - assumes specific format
    int firstList[100][2], secondList[100][2], result[200][2];
    int m = 3, n = 4; // Example sizes
    int resultSize;
    
    // Example input
    firstList[0][0] = 0; firstList[0][1] = 2;
    firstList[1][0] = 5; firstList[1][1] = 10;
    firstList[2][0] = 13; firstList[2][1] = 23;
    
    secondList[0][0] = 1; secondList[0][1] = 5;
    secondList[1][0] = 8; secondList[1][1] = 12;
    secondList[2][0] = 15; secondList[2][1] = 24;
    secondList[3][0] = 25; secondList[3][1] = 26;
    
    solution(firstList, m, secondList, n, result, &resultSize);
    
    printf("[");
    for (int i = 0; i < resultSize; i++) {
        printf("[%d,%d]", result[i][0], result[i][1]);
        if (i < resultSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m+n)

Single pass through both lists with two pointers, each interval visited once

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables for pointers, result array doesn't count toward space complexity

✓ Linear Space

156.0K Views

Medium Frequency

~25 min Avg. Time

3.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pointers - Optimal Solution — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler