Skip to main content
Talentd

Find Maximal Uncovered Ranges - Solution & Explanation

MediumPremiumFree on FleetCodeArraySorting10 min readAsked at: Meta
Practice this problem

Problem Statement

You are given an integer n which is the length of a 0-indexed array nums, and a 0-indexed 2D-array ranges, which is a list of sub-ranges of nums (sub-ranges may overlap).

Each row ranges[i] has exactly 2 cells:

  • ranges[i][0], which shows the start of the ith range (inclusive)
  • ranges[i][1], which shows the end of the ith range (inclusive)

These ranges cover some cells of nums and leave some cells uncovered. Your task is to find all of the uncovered ranges with maximal length.

Return a 2D-array answer of the uncovered ranges, sorted by the starting point in ascending order.

By all of the uncovered ranges with maximal length, we mean satisfying two conditions:

  • Each uncovered cell should belong to exactly one sub-range
  • There should not exist two ranges (l1, r1) and (l2, r2) such that r1 + 1 = l2

 

Example 1:

Input: n = 10, ranges = [[3,5],[7,8]]
Output: [[0,2],[6,6],[9,9]]
Explanation: The ranges (3, 5) and (7, 8) are covered, so if we simplify the array nums to a binary array where 0 shows an uncovered cell and 1 shows a covered cell, the array becomes [0,0,0,1,1,1,0,1,1,0] in which we can observe that the ranges (0, 2), (6, 6) and (9, 9) aren't covered.

Example 2:

Input: n = 3, ranges = [[0,2]]
Output: []
Explanation: In this example, the whole of the array nums is covered and there are no uncovered cells so the output is an empty array.

Example 3:

Input: n = 7, ranges = [[2,4],[0,3]]
Output: [[5,6]]
Explanation: The ranges (0, 3) and (2, 4) are covered, so if we simplify the array nums to a binary array where 0 shows an uncovered cell and 1 shows a covered cell, the array becomes [1,1,1,1,1,0,0] in which we can observe that the range (5, 6) is uncovered.

 

Constraints:

  • 1 <= n <= 109
  • 0 <= ranges.length <= 106
  • ranges[i].length = 2
  • 0 <= ranges[i][j] <= n - 1
  • ranges[i][0] <= ranges[i][1]

Approach Overview

Problem Overview: You get an integer n representing the range [0, n-1] and a list of covered intervals. The task is to return all maximal contiguous ranges that are not covered by any interval.

Approach 1: Brute Force Marking (O(n + m * k) time, O(n) space)

Create a boolean array of size n where each index represents whether that position is covered. Iterate through every interval and mark the corresponding indices as covered. After marking, scan the array to collect maximal contiguous segments where coverage is false. This approach is straightforward but inefficient when n is large because every element inside each interval may be visited.

Approach 2: Sorting and Gap Detection (O(m log m) time, O(1) extra space)

Sort the intervals by their starting point using a standard sorting technique. Track the end of the last covered position while iterating through the sorted intervals. Whenever the next interval starts after the current covered boundary, the gap between them forms an uncovered range. Update the current boundary with max(currentEnd, intervalEnd) to handle overlaps and merged coverage. This approach works well because sorted intervals allow you to detect gaps with a single linear scan.

After processing all intervals, check if the last covered boundary is less than n - 1. If so, the remaining segment forms the final uncovered range. The logic resembles interval merging problems commonly seen with array processing and sorting patterns.

Recommended for interviews: The sorting + gap detection approach. Interviewers expect you to recognize this as an interval problem: sort the intervals, track the current merged coverage, and output gaps. Brute force demonstrates the basic idea of coverage, but the sorted scan shows you understand interval merging and optimal time complexity.

Solution

We sort all intervals by their left endpoints in ascending order, then traverse all intervals from left to right, maintaining a variable last to represent the rightmost endpoint that has been covered so far, initially last=-1.

If the left endpoint of the current interval is greater than last+1, it means [last+1, l-1] is an uncovered interval, and we add it to the answer array. Then we update last to the right endpoint of the current interval and continue traversing the next interval. After traversing all intervals, if last+1 < n, it means [last+1, n-1] is an uncovered interval, and we add it to the answer array.

Finally, we return the answer array.

The time complexity is O(n times log n), and the space complexity is O(log n), where n is the length of the array ranges.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force MarkingO(n + m * k)O(n)Small n where marking coverage directly is simple and acceptable
Sorting + Gap DetectionO(m log m)O(1)General case with many intervals; standard optimal interview approach

Video Solution

Kth Largest Element in an Array - Quick Select - Leetcode 215 - Python • NeetCode • 331,616 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find Maximal Uncovered Ranges easy or hard?
Find Maximal Uncovered Ranges is considered a Medium-level problem. The challenge is recognizing it as an interval merging and gap detection problem, which requires sorting and careful boundary updates.
Find Maximal Uncovered Ranges Python/Java solution
Most implementations sort the intervals, track the current covered boundary, and append gaps to a result list. The same logic translates cleanly to Python, Java, C++, Go, TypeScript, and Rust because it relies only on sorting and a linear pass.
How to solve Find Maximal Uncovered Ranges in O(n)?
True O(n) is possible only if the range size n is small and you use a coverage array. Mark each interval as covered in a boolean array and scan for uncovered segments. This uses O(n) space and O(n + total interval length) time, which is practical only when n is manageable.
What is the best approach for Find Maximal Uncovered Ranges?
The most efficient approach sorts the intervals by start position and scans them to detect gaps. While iterating, maintain the farthest covered endpoint and output any gap before the next interval begins. This sorting-based interval scan runs in O(m log m) time and O(1) extra space.
Is Find Maximal Uncovered Ranges asked at Google/Amazon/Meta?
Interval and gap-detection problems frequently appear in interviews at companies like Google, Amazon, and Meta. While the exact problem ID may vary, the pattern of sorting intervals and finding uncovered gaps is a common interview topic.
What data structure is used in Find Maximal Uncovered Ranges?
The solution primarily uses arrays to store intervals and relies on sorting. During the scan, only a few variables track the current merged boundary and detected gaps, so no advanced data structures are required.
What is the time complexity of Find Maximal Uncovered Ranges?
The optimal solution runs in O(m log m) time due to sorting the intervals, followed by a linear scan. The scan itself is O(m). Space complexity is O(1) if the intervals are processed in-place, excluding the output list.

Ready to solve this problem?

Practice Find Maximal Uncovered Ranges with our built-in code editor and test cases.

Practice on FleetCode
Previous

Check if All the Integers in a Range Are Covered

Next

Missing Ranges