We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Maximal Uncovered Ranges

Number: 2815

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given a 0-indexed array of length n and a list of possibly overlapping ranges that indicate covered portions of the array, the objective is to find all the maximal uncovered ranges. An uncovered range must satisfy:

  • Every uncovered cell belongs to exactly one sub-range.
  • There are no two sub-ranges that are adjacent (i.e. no two ranges where the end of one plus one equals the start of the next).

In short, you need to return a sorted list of intervals (by starting index ascending) that represent contiguous uncovered segments in the array.

Key Insights

  • Instead of processing the entire array (n can be up to 10^9), merge the given covered ranges.
  • Merge overlapping or contiguous covered intervals to compute disjoint intervals of coverage.
  • The uncovered intervals are the gaps between these merged covered intervals as well as possible gaps at the beginning and end of the array.
  • Sorting the ranges first (by start index) allows efficient merging.

Space and Time Complexity

Time Complexity: O(m log m) where m is the number of ranges (up to 10^6) due to sorting. Space Complexity: O(m) for storing the merged coverage intervals.

Solution

The solution consists of the following steps:

  1. If the ranges list is empty, the whole array [0, n-1] is uncovered.
  2. Sort the ranges based on the starting index.
  3. Merge overlapping or contiguous ranges to form a list of disjoint covered intervals.
  4. Find the gaps (uncovered ranges) between these merged intervals.
  5. Return the uncovered ranges ensuring each uncovered cell belongs to one maximal contiguous sub-range (thus no two uncovered intervals will have r1+1 = l2).

Code Solutions

# Python solution for finding maximal uncovered ranges

def findMaximalUncoveredRanges(n, ranges):
    # If there are no covered ranges, the entire array is uncovered.
    if not ranges:
        return [[0, n - 1]]
    
    # Sort ranges by their starting index
    ranges.sort(key=lambda x: x[0])
    
    # Merge overlapping or contiguous intervals
    merged = []
    for start, end in ranges:
        # If merged list is empty or current range does not overlap with last merged range, append it.
        if not merged or merged[-1][1] + 1 < start:
            merged.append([start, end])
        else:
            # Otherwise, extend the last merged range if needed.
            merged[-1][1] = max(merged[-1][1], end)
    
    result = []
    # Check for uncovered interval before first merged interval
    if merged[0][0] > 0:
        result.append([0, merged[0][0] - 1])
    
    # Check for gaps between merged intervals
    for i in range(1, len(merged)):
        prev_end = merged[i - 1][1]
        curr_start = merged[i][0]
        if prev_end + 1 < curr_start:
            result.append([prev_end + 1, curr_start - 1])
    
    # Check for uncovered interval after the last merged interval
    if merged[-1][1] < n - 1:
        result.append([merged[-1][1] + 1, n - 1])
    
    return result

# Example usage:
print(findMaximalUncoveredRanges(10, [[3, 5], [7, 8]]))  # Expected output: [[0, 2], [6, 6], [9, 9]]
← Back to All Questions