Find Maximal Uncovered Ranges - Practice Coding Problems

Find Maximal Uncovered Ranges - Problem

Array Sorting Medium

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

Input & Output

Example 1 — Basic Case

$ Input: n = 8, ranges = [[0,2],[5,7]]

› Output: [[3,4]]

💡 Note: Positions 0-2 are covered by [0,2], positions 5-7 are covered by [5,7]. Positions 3-4 are uncovered, forming one maximal range [3,4].

Example 2 — Multiple Gaps

$ Input: n = 10, ranges = [[2,3],[7,8]]

› Output: [[0,1],[4,6],[9,9]]

💡 Note: Three uncovered ranges: [0,1] before first range, [4,6] between ranges, and [9,9] after last range.

Example 3 — Overlapping Ranges

$ Input: n = 6, ranges = [[1,3],[2,5]]

› Output: [[0,0]]

💡 Note: Ranges [1,3] and [2,5] overlap and merge to [1,5]. Only position 0 is uncovered.

Constraints

1 ≤ n ≤ 50
0 ≤ ranges.length ≤ 50
ranges[i].length == 2
0 ≤ ranges[i][0] ≤ ranges[i][1] < n

Visualization

Tap to expand

Understanding the Visualization

Input

Array length n=8, ranges [[0,2],[5,7]]

Process

Merge overlapping ranges and find gaps

Output

Uncovered range [[3,4]]

Key Takeaway

🎯 Key Insight: Merge overlapping ranges first, then scan for gaps between merged ranges

Asked in

G Google 25 a Amazon 20 M Microsoft 15

The key insight is to merge overlapping ranges first, then find gaps between merged ranges. The optimal approach sorts ranges by start position O(m log m), merges overlapping ones, then scans for gaps. Time: O(m log m), Space: O(m)

Common Approaches

Approach	Time	Space	Notes
✓ Sort and Merge Ranges	O(m log m)	O(m)	Sort ranges by start position, merge overlapping ones, then find gaps
Brute Force Check Each Position	O(n × m)	O(1)	Check each position individually to see if it's covered by any range

Sort and Merge Ranges — Algorithm Steps

Step 1: Sort ranges by start position
Step 2: Merge overlapping ranges
Step 3: Find gaps between merged ranges

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Ranges

Sort by start position

Merge Overlaps

Combine adjacent/overlapping ranges

Find Gaps

Identify spaces between merged ranges

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    int* rangeA = *(int**)a;
    int* rangeB = *(int**)b;
    return rangeA[0] - rangeB[0];
}

int** solution(int n, int** ranges, int rangesSize, int* returnSize, int** returnColumnSizes) {
    int** result = malloc(n * sizeof(int*));
    *returnColumnSizes = malloc(n * sizeof(int));
    *returnSize = 0;
    
    if (rangesSize == 0) {
        if (n > 0) {
            result[0] = malloc(2 * sizeof(int));
            result[0][0] = 0;
            result[0][1] = n - 1;
            (*returnColumnSizes)[0] = 2;
            *returnSize = 1;
        }
        return result;
    }
    
    // Sort ranges by start position
    qsort(ranges, rangesSize, sizeof(int*), compare);
    
    // Merge overlapping ranges
    int** merged = malloc(rangesSize * sizeof(int*));
    int mergedSize = 0;
    
    merged[mergedSize] = malloc(2 * sizeof(int));
    merged[mergedSize][0] = ranges[0][0];
    merged[mergedSize][1] = ranges[0][1];
    mergedSize++;
    
    for (int i = 1; i < rangesSize; i++) {
        if (ranges[i][0] <= merged[mergedSize-1][1] + 1) {
            if (ranges[i][1] > merged[mergedSize-1][1]) {
                merged[mergedSize-1][1] = ranges[i][1];
            }
        } else {
            merged[mergedSize] = malloc(2 * sizeof(int));
            merged[mergedSize][0] = ranges[i][0];
            merged[mergedSize][1] = ranges[i][1];
            mergedSize++;
        }
    }
    
    // Find uncovered ranges
    // Check gap before first range
    if (merged[0][0] > 0) {
        result[*returnSize] = malloc(2 * sizeof(int));
        result[*returnSize][0] = 0;
        result[*returnSize][1] = merged[0][0] - 1;
        (*returnColumnSizes)[*returnSize] = 2;
        (*returnSize)++;
    }
    
    // Check gaps between ranges
    for (int i = 0; i < mergedSize - 1; i++) {
        if (merged[i][1] + 1 < merged[i + 1][0]) {
            result[*returnSize] = malloc(2 * sizeof(int));
            result[*returnSize][0] = merged[i][1] + 1;
            result[*returnSize][1] = merged[i + 1][0] - 1;
            (*returnColumnSizes)[*returnSize] = 2;
            (*returnSize)++;
        }
    }
    
    // Check gap after last range
    if (merged[mergedSize-1][1] < n - 1) {
        result[*returnSize] = malloc(2 * sizeof(int));
        result[*returnSize][0] = merged[mergedSize-1][1] + 1;
        result[*returnSize][1] = n - 1;
        (*returnColumnSizes)[*returnSize] = 2;
        (*returnSize)++;
    }
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    // Simple parsing for the example
    int rangesSize = 2;
    int** ranges = malloc(rangesSize * sizeof(int*));
    for (int i = 0; i < rangesSize; i++) {
        ranges[i] = malloc(2 * sizeof(int));
    }
    
    // Hardcoded for demo - in real implementation, parse JSON
    ranges[0][0] = 0; ranges[0][1] = 2;
    ranges[1][0] = 5; ranges[1][1] = 7;
    
    int returnSize;
    int* returnColumnSizes;
    int** result = solution(n, ranges, rangesSize, &returnSize, &returnColumnSizes);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("[%d,%d]", result[i][0], result[i][1]);
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m log m)

Sorting m ranges dominates, merging and gap finding are O(m)

⚡ Linearithmic

Space Complexity

O(m)

Space for merged ranges list

✓ Linear Space

12.0K Views

Medium Frequency

~15 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort and Merge Ranges — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler