How to Find Gaps Between Sorted Intervals in Python

This code finds gap ranges between sorted intervals using pairwise iteration, returning ranges where no interval covers.

Easy Python 3.10+ Aug 9, 2026 Algorithms & data structures 14 views 0 copies

intervals pairwise sorting gap-detection

Python code

13 lines
Python 3.10+
Run it 
from itertools import pairwise

def find_gaps(intervals):
    intervals = sorted(intervals)
    gaps = []
    for prev, curr in pairwise(intervals):
        if prev[1] < curr[0]:
            gaps.append((prev[1] + 1, curr[0] - 1))
    return gaps

if __name__ == "__main__":
    intervals = [(1, 3), (5, 7), (10, 12), (15, 18)]
    print(find_gaps(intervals))

Output

stdout 
[(4, 4), (8, 9), (13, 14)]

How it works

The sorted call ensures intervals are ordered by start time. pairwise from itertools yields consecutive pairs of intervals. For each pair, comparing the previous interval's end with the next interval's start detects non-overlapping gaps. If a gap exists, the code computes the gap range from prev[1] + 1 to curr[0] - 1. This approach works only when intervals don't overlap and are sorted.

Common mistakes

  • Assuming intervals are already sorted before calling the function
  • Not handling overlapping intervals — the logic may produce incorrect gaps
  • Forgetting that gaps are exclusive of the interval endpoints, using wrong +1/-1 adjustments
  • Using pairwise only on Python 3.10+; needing to fall back to zip for older versions

Variations

  1. Use a for loop with index instead of pairwise: for i in range(len(intervals)-1)
  2. Merge overlapping intervals first before finding gaps

Real-world use cases

  • Finding free time slots in a calendar scheduler given busy intervals.
  • Identifying unassigned port ranges in network infrastructure after reservations.
  • Locating missing date ranges in time-series data during ETL validation.

Sponsored

Run this sample

Open the browser IDE to tweak the example and see results without installing anything.

Open editor

More from Algorithms & data structures

Keep learning

Related tutorials and quizzes for this topic.

Tutorials

Quizzes