Remove Covered Intervals - Solution & Explanation
Problem Statement
Given an array intervals where intervals[i] = [li, ri] represent the interval [li, ri), remove all intervals that are covered by another interval in the list.
The interval [a, b) is covered by the interval [c, d) if and only if c <= a and b <= d.
Return the number of remaining intervals.
Example 1:
Input: intervals = [[1,4],[3,6],[2,8]] Output: 2 Explanation: Interval [3,6] is covered by [2,8], therefore it is removed.
Example 2:
Input: intervals = [[1,4],[2,3]] Output: 1
Constraints:
1 <= intervals.length <= 1000intervals[i].length == 20 <= li < ri <= 105- All the given intervals are unique.
Approach Overview
Problem Overview: You are given a list of intervals where each interval is represented as [start, end]. An interval is considered covered if another interval fully contains it. The task is to remove all covered intervals and return the number of remaining intervals.
Approach 1: Graph-Based Comparison (Implicit Graph) (O(n²) time, O(1) extra space)
Treat every interval as a node and check coverage relationships between all pairs. For each interval i, iterate through every other interval j. If j.start ≤ i.start and j.end ≥ i.end, interval i is covered and should not be counted. This brute-force comparison effectively builds an implicit coverage graph without storing edges. The method is straightforward and helps you reason about the definition of coverage, but the nested iteration leads to O(n²) time complexity. Space stays O(1) because only counters and temporary variables are used.
Approach 2: Sort by Start, End Descending (O(n log n) time, O(1) space)
The optimal solution relies on sorting. Sort intervals by start in ascending order. When two intervals share the same start, sort by end in descending order. This ordering guarantees that larger covering intervals appear before the smaller ones they might contain.
After sorting, scan the array once while tracking the maximum end value seen so far. If the current interval's end is less than or equal to that maximum, it is covered by a previous interval. Otherwise, it is a valid interval that should be counted, and the maximum end gets updated. Because sorting groups potential coverings together, a single linear pass is enough to detect coverage relationships.
This approach combines array traversal with sorting order to eliminate the need for pairwise comparisons. Sorting costs O(n log n), and the scan is O(n). No additional data structures are required beyond a few variables, so extra space remains O(1) (ignoring sort implementation details).
Recommended for interviews: The sorting approach is the expected solution. It shows you recognize that ordering intervals can simplify containment checks and reduce the complexity from O(n²) to O(n log n). Explaining the brute-force comparison first demonstrates clear understanding of the coverage rule, while the optimized sorting strategy shows strong algorithmic thinking using sorting and interval scanning patterns.
Approach 1: Sorting by Start and then by End Descending
First, sort the intervals by their starting point. If two intervals have the same start, sort them by their ending point in descending order. This helps in ensuring that when you iterate, you can simply keep a check on the maximum end encountered and compare each interval to determine if it is covered.
This C solution includes sorting the 2D array of intervals based on custom rules as mentioned. After sorting, it iterates through each interval, and incrementally counts those that are not covered by keeping a check on the last maximum end encountered.
Complexity
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) since sorting is done in place.
Approach 2: Graph-Based Approach (Implicit Graph)
Conceptually, treat each pair of intervals as a directed edge if one interval is covering another. Such implicit graph construction helps identify covered intervals. You process over this graph to recognize unique intervals not covered by others. This approach may be non-trivial compared to the sorting technique, but it provides a different perspective.
This C implementation checks each interval against every other to see if it is covered (acting as a graph edge implies coverage). An array tracks covered intervals, and the count reduces with each uncovered detection.
Complexity
Time Complexity: O(n^2) for comparing each interval with every other one.
Space Complexity: O(n) for the boolean array tracking covered intervals.
Approach 3: Sorting
We can sort the intervals in ascending order by their left endpoints, and if the left endpoints are the same, sort them in descending order by their right endpoints.
After sorting, we can traverse the intervals. If the right endpoint of the current interval is greater than the previous right endpoint, it means the current interval is not covered, and we increment the answer by one.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the number of intervals.
Code
Python
Java
C++
Go
TypeScript
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sorting by Start and then by End Descending | Time Complexity: O(n log n) due to sorting. |
| Graph-Based Approach (Implicit Graph) | Time Complexity: O(n^2) for comparing each interval with every other one. |
| Sorting | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Graph-Based Comparison (Implicit Graph) | O(n²) | O(1) | Useful for understanding the coverage definition or when constraints are very small. |
| Sort by Start, End Descending | O(n log n) | O(1) | Optimal general solution. Preferred in interviews and large input sizes. |
Video Solution
Remove Covered Intervals - Leetcode 1288 - Python • NeetCode • 17,041 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Remove Covered Intervals easy or hard?
Remove Covered Intervals Python/Java solution
How to solve Remove Covered Intervals in O(n)?
What is the best approach for Remove Covered Intervals?
Is Remove Covered Intervals asked at Google/Amazon/Meta?
What data structure is used in Remove Covered Intervals?
What is the time complexity of Remove Covered Intervals?
Ready to solve this problem?
Practice Remove Covered Intervals with our built-in code editor and test cases.
Practice on FleetCode