Count Ways to Group Overlapping Ranges - Practice Coding Problems

Count Ways to Group Overlapping Ranges - Problem

Array Sorting Medium

You are given a 2D integer array ranges where ranges[i] = [start_i, end_i] denotes that all integers between start_i and end_i (both inclusive) are contained in the i^th range.

You are to split ranges into two (possibly empty) groups such that:

Each range belongs to exactly one group.
Any two overlapping ranges must belong to the same group.

Two ranges are said to be overlapping if there exists at least one integer that is present in both ranges.

For example, [1, 3] and [2, 5] are overlapping because 2 and 3 occur in both ranges.

Return the total number of ways to split ranges into two groups. Since the answer may be very large, return it modulo 10⁹ + 7.

Input & Output

Example 1 — Basic Overlapping Ranges

$ Input: ranges = [[6,10],[5,15]]

› Output: 2

💡 Note: The two ranges [6,10] and [5,15] overlap (they share integers 6,7,8,9,10), so they must be in the same group. We can put both in group 1 or both in group 2, giving us 2 ways total.

Example 2 — Non-overlapping Ranges

$ Input: ranges = [[1,3],[10,20],[2,5],[4,8]]

› Output: 4

💡 Note: After sorting: [1,3],[2,5],[4,8],[10,20]. Ranges [1,3],[2,5],[4,8] all overlap and form one component. Range [10,20] is separate. So we have 2 components, giving us 2² = 4 ways.

Example 3 — All Separate

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

› Output: 8

💡 Note: All three ranges are non-overlapping, so we have 3 independent components. Each can go to either group: 2³ = 8 ways total.

Constraints

1 ≤ ranges.length ≤ 10⁴
ranges[i].length == 2
0 ≤ start_i ≤ end_i ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array of ranges where each range [start, end] represents integers from start to end

Process

Group overlapping ranges together, count independent components

Output

Number of ways to split into two groups = 2^(components)

Key Takeaway

🎯 Key Insight: Merge overlapping ranges into components, then each component independently chooses a group

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is that overlapping ranges must be in the same group, forming connected components. After sorting and merging overlapping ranges, each independent component can choose either group. Best approach is Sort and Merge with Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Sort and Merge Overlapping Ranges	O(n log n)	O(1)	Sort ranges by start time, merge overlapping ones, then count independent components
Brute Force - Try All Groupings	O(n × 2ⁿ)	O(n)	Generate all possible ways to assign ranges to two groups and count valid ones

Sort and Merge Overlapping Ranges — Algorithm Steps

Sort ranges by start position
Merge overlapping ranges into components
Return 2^(number of components) mod (10^9 + 7)

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort

Sort ranges by start position

Merge

Merge overlapping ranges into components

Calculate

Result = 2^(components)

Code -

solution.c — C

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

#define MOD 1000000007

int ranges[100000][2];
int n;

int max(int a, int b) { return a > b ? a : b; }

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

int solution() {
    if (n == 0) return 1;
    
    // Sort ranges by start position
    qsort(ranges, n, sizeof(int[2]), compare);
    
    // Merge overlapping ranges to count connected components
    int components = 1;
    int currentEnd = ranges[0][1];
    
    for (int i = 1; i < n; i++) {
        int start = ranges[i][0];
        int end = ranges[i][1];
        if (start <= currentEnd) {  // Overlapping
            currentEnd = max(currentEnd, end);
        } else {  // New component
            components++;
            currentEnd = end;
        }
    }
    
    // Each component can be in group 1 or group 2
    long long result = 1;
    for (int i = 0; i < components; i++) {
        result = (result * 2) % MOD;
    }
    return result;
}

int main() {
    char line[100000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [[a,b],[c,d],...]
    if (strcmp(line, "[]\n") == 0) {
        printf("1\n");
        return 0;
    }
    
    char* ptr = line + 1; // Skip first [
    n = 0;
    while (*ptr && *ptr != ']' || *(ptr+1) != '\0') {
        if (*ptr == '[') {
            ptr++;
            ranges[n][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            ranges[n][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            n++;
        }
        ptr++;
    }
    
    printf("%d\n", solution());
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting takes O(n log n), merging takes O(n), exponentiation takes O(log n)

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra space for variables, sorting is in-place

✓ Linear Space

12.0K Views

Medium Frequency

~25 min Avg. Time

245 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 Overlapping Ranges — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler