Intervals
The Intervals Pattern
Intervals are sorted by one endpoint, then swept in order while tracking what is currently open. Almost every interval problem reduces to sorting correctly and then handling one comparison between the current interval and the previous one.
Interactive problems
Free to open
How do you recognise a intervals problem?
The input is a list of start/end pairs — meetings, bookings, ranges — and the question involves merging, overlap, insertion or counting concurrency. If the input looks like [[1,3],[2,6],[8,10]], this is the pattern.
What is the time complexity of the intervals pattern?
O(n log n), dominated by the sort; the sweep itself is O(n). Choosing the wrong sort key is the most common failure, and it is usually end time rather than start time.
Intervals practice problems
Each problem pairs a worked explanation with an interactive visualizer you step through yourself, plus the implementation in JavaScript, Python, Java and C++.
Intervals problems by difficulty and complexity
The difficulty, running time and extra space of every intervals solution on this page, as each lesson derives them.
| Lesson | Difficulty | Best | Average | Worst | Space |
|---|---|---|---|---|---|
| Intervals Overview | Medium | Ω(n log n) | Θ(n log n) | O(n log n) | O(n) |
| Merge Intervals | Medium | Ω(n log n) | Θ(n log n) | O(n log n) | O(n) |
| Insert Interval | Medium | Ω(n) | Θ(n) | O(n) | O(n) |
| Non-overlapping Intervals | Medium | Ω(n log n) | Θ(n log n) | O(n log n) | O(log n) |
| Meeting Rooms | Easy | Ω(n log n) | Θ(n log n) | O(n log n) | O(log n) |
| Meeting Rooms II | Medium | Ω(n log n) | Θ(n log n) | O(n log n) | O(n) |
| Min Arrows to Burst Balloons | Medium | Ω(n log n) | Θ(n log n) | O(n log n) | O(log n) |
Related patterns and concepts
Intervals is one of the 17 coding interview patterns, and its problems also appear in the DSA 75 interview sprint.
Every other coding interview pattern
Depth-First Search · 25 lessons
- Introduction to DFSFree
- DFS FundamentalsFree
- Return Values in DFS
- Invert Binary Tree
- Maximum Depth of Binary Tree
- Path Sum
- Passing Values Down (State)
- Validate Binary Search Tree
- Kth Smallest Element in a BST
- Construct Binary Tree from Preorder and Inorder Traversal
- Binary Tree Tilt
- Diameter of Binary Tree
- Lowest Common Ancestor of a Binary Tree
- Path Sum II
- Longest Univalue Path
- Graphs Overview
- Graph Representation: Adjacency List
- Clone Graph
- Graph Valid Tree
- Matrices as Graphs
- Flood Fill
- Types of DFS (Tree Traversals)
- Number of Islands
- Surrounded Regions
- Pacific Atlantic Water FlowFree