Missing Ranges - Practice Coding Problems

Missing Ranges - Problem

Array Easy

You are given an inclusive range [lower, upper] and a sorted unique integer array nums, where all elements are within the inclusive range.

A number x is considered missing if x is in the range [lower, upper] and x is not in nums.

Return the shortest sorted list of ranges that exactly covers all the missing numbers. That is, no element of nums is included in any of the ranges, and each missing number is covered by one of the ranges.

Each range [a,b] in the list should be output as:

"a->b" if a != b
"a" if a == b

Input & Output

Example 1 — Basic Missing Ranges

$ Input: nums = [0,1,3,50,75], lower = 0, upper = 99

› Output: ["2","4->49","51->74","76->99"]

💡 Note: Missing ranges: 2 (single number), 4-49 (range), 51-74 (range), and 76-99 (range)

Example 2 — Single Missing Number

$ Input: nums = [1,3], lower = 1, upper = 3

› Output: ["2"]

💡 Note: Only number 2 is missing from range [1,3]

Example 3 — Empty Array

$ Input: nums = [], lower = 1, upper = 1

› Output: ["1"]

💡 Note: Array is empty, so entire range [1,1] is missing

Constraints

-10⁹ ≤ lower ≤ upper ≤ 10⁹
0 ≤ nums.length ≤ 100
lower ≤ nums[i] ≤ upper
All values in nums are unique

Visualization

Tap to expand

Understanding the Visualization

Input

Sorted array nums and range [lower, upper]

Process

Find gaps between consecutive elements

Output

Format missing ranges as strings

Key Takeaway

🎯 Key Insight: Instead of checking every number in the range, examine gaps between consecutive existing numbers for optimal O(n) solution

Asked in

G Google 45 f Facebook 32 a Amazon 28 M Microsoft 22

The key insight is to focus on gaps between consecutive numbers rather than checking every individual number. The optimal approach scans through the sorted array once, detecting gaps before, between, and after existing elements. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check Every Number	O(n + r)	O(n)	Check every number in [lower, upper] to see if it exists in nums
One Pass Gap Detection	O(n)	O(1)	Scan through nums array once, detecting gaps between consecutive elements

Brute Force - Check Every Number — Algorithm Steps

Convert nums to set for O(1) lookup
Iterate through every number from lower to upper
Check if each number exists in the set
Group consecutive missing numbers into ranges

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Set

Convert nums to set for fast lookup

Check Range

Check every number from lower to upper

Form Ranges

Group consecutive missing numbers

Code -

solution.c — C

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

char** solution(int* nums, int numsSize, int lower, int upper, int* returnSize) {
    bool* exists = (bool*)calloc(upper - lower + 1, sizeof(bool));
    
    // Mark existing numbers
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] >= lower && nums[i] <= upper) {
            exists[nums[i] - lower] = true;
        }
    }
    
    char** result = (char**)malloc(1000 * sizeof(char*));
    *returnSize = 0;
    int start = -1;
    
    for (int i = 0; i <= upper - lower; i++) {
        if (!exists[i]) {
            if (start == -1) {
                start = i + lower;
            }
        } else {
            if (start != -1) {
                result[*returnSize] = (char*)malloc(50 * sizeof(char));
                if (start == i + lower - 1) {
                    sprintf(result[*returnSize], "%d", start);
                } else {
                    sprintf(result[*returnSize], "%d->%d", start, i + lower - 1);
                }
                (*returnSize)++;
                start = -1;
            }
        }
    }
    
    // Handle case where range ends with missing numbers
    if (start != -1) {
        result[*returnSize] = (char*)malloc(50 * sizeof(char));
        if (start == upper) {
            sprintf(result[*returnSize], "%d", start);
        } else {
            sprintf(result[*returnSize], "%d->%d", start, upper);
        }
        (*returnSize)++;
    }
    
    free(exists);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    if (strcmp(line, "[]\n") != 0) {
        char* token = strtok(line, "[,]");
        while (token != NULL) {
            nums[numsSize++] = atoi(token);
            token = strtok(NULL, "[,]");
        }
    }
    
    int lower, upper;
    scanf("%d", &lower);
    scanf("%d", &upper);
    
    int returnSize;
    char** result = solution(nums, numsSize, lower, upper, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("\"%s\"", result[i]);
        if (i < returnSize - 1) printf(",");
        free(result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + r)

O(n) to build set from nums, O(r) to check each number in range [lower, upper] where r = upper - lower + 1

✓ Linear Growth

Space Complexity

O(n)

Set stores all n elements from nums array

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

842 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

Brute Force - Check Every Number — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler