Count Ways to Group Overlapping Ranges

Medium
1044.

Count Ways to Group Overlapping Ranges

Count Ways to Group Overlapping Ranges is a medium coding problem on arrays, math and sorting, asked in Amazon, Google and Salesforce interviews.

ranges[i] = [start, end] is an inclusive range of integers. Split all the ranges into two groups so that any two ranges sharing at least one integer end up in the same group. Either group may be empty.

Return the number of ways to do this, modulo 10⁹ + 7. Two ways differ if some range lands in a different group.

Example 1

Input
ranges = [[6,10],[5,15]]
Output
2
Explanation
They overlap, so both go together — into group 1 or group 2.

Example 2

Input
ranges = [[1,3],[10,20],[2,5],[4,8]]
Output
4
Explanation
`[1,3]`, `[2,5]` and `[4,8]` merge into one block; `[10,20]` is its own. 2² = 4.

Example 3

Input
ranges = [[1,2]]
Output
2

Constraints

  • 1 <= ranges.length <= 10^5
  • ranges[i].length == 2
  • 0 <= starti <= endi <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} ranges
 * @return {number}
 */
var countWays = function(ranges) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Ways to Group Overlapping Ranges — Problem & Solution

Count Ways to Group Overlapping Ranges solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count Ways to Group Overlapping Ranges is a medium coding problem on arrays, math and sorting, asked in Amazon, Google and Salesforce interviews.

  • Difficulty: Medium
  • Topics: Arrays, Math, Sorting
  • Asked at: Amazon, Google, Salesforce
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

ranges[i] = [start, end] is an inclusive range of integers. Split all the ranges into two groups so that any two ranges sharing at least one integer end up in the same group. Either group may be empty.

Return the number of ways to do this, modulo 10⁹ + 7. Two ways differ if some range lands in a different group.

Example 1

Input: ranges = [[6,10],[5,15]]
Output: 2
Explanation: They overlap, so both go together — into group 1 or group 2.

Example 2

Input: ranges = [[1,3],[10,20],[2,5],[4,8]]
Output: 4
Explanation: `[1,3]`, `[2,5]` and `[4,8]` merge into one block; `[10,20]` is its own. 2² = 4.

Example 3

Input: ranges = [[1,2]]
Output: 2

Constraints

  • 1 <= ranges.length <= 10^5
  • ranges[i].length == 2
  • 0 <= starti <= endi <= 10^9

Hints for Count Ways to Group Overlapping Ranges

  1. Hint 1

    Ranges that overlap — even transitively through a chain — are forced into the same group.

  2. Hint 2

    So merge the overlapping ranges first and count how many independent blocks remain.

  3. Hint 3

    Each block chooses one of two groups freely: the answer is 2^blocks.

How to solve Count Ways to Group Overlapping Ranges

Sort by start and sweep, merging ranges into maximal blocks: a range starts a new block only when its start is beyond the furthest end reached so far. Each block is then independent, so the answer is 2^blocks.

Approach

  1. Sort the ranges by start.
  2. Track reach, the furthest end covered. A range with start > reach opens a new block.
  3. Extend reach to the range's end when it goes further.
  4. Return 2^blocks modulo 10⁹ + 7.

Why it works

"Share an integer" is transitive once the ranges are merged — a chain of pairwise overlaps forms a single connected block, which is why a union-find solution and this sweep give the same count. Sorting by start is what lets one reach variable stand in for the whole block: any later range that starts at or before reach must touch something already inside it.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • Touching endpoints count as overlapping: [1,3] and [3,5] share the integer 3.
  • reach must be the maximum end so far, not the previous range's end — a nested range would otherwise close the block early.
  • The exponent is the number of blocks, not the number of ranges.

Reference solution

Python

from typing import List

def countWays(ranges: List[List[int]]) -> int:
    MOD = 10**9 + 7
    groups = 0
    reach = -1
    for start, end in sorted(ranges):
        if start > reach:
            groups += 1
        reach = max(reach, end)
    return pow(2, groups, MOD)

Java

public static int countWays(int[][] ranges) {
    final long MOD = 1000000007L;
    int[][] sorted = ranges.clone();
    Arrays.sort(sorted, (a, b) -> Integer.compare(a[0], b[0]));
    int groups = 0;
    int reach = -1;
    for (int[] r : sorted) {
        if (r[0] > reach) groups++;
        reach = Math.max(reach, r[1]);
    }
    long answer = 1;
    for (int i = 0; i < groups; i++) answer = answer * 2 % MOD;
    return (int) answer;
}

C++

int countWays(vector<vector<int>>& ranges) {
    const long long MOD = 1000000007LL;
    vector<vector<int>> sorted = ranges;
    sort(sorted.begin(), sorted.end());
    int groups = 0, reach = -1;
    for (auto& r : sorted) {
        if (r[0] > reach) groups++;
        reach = max(reach, r[1]);
    }
    long long answer = 1;
    for (int i = 0; i < groups; i++) answer = answer * 2 % MOD;
    return (int) answer;
}

JavaScript

var countWays = function(ranges) {
    var MOD = 1000000007;
    var sorted = ranges.slice();
    sorted.sort(function(a, b) { return a[0] - b[0]; });
    var groups = 0, reach = -1;
    for (var i = 0; i < sorted.length; i++) {
        if (sorted[i][0] > reach) groups++;
        if (sorted[i][1] > reach) reach = sorted[i][1];
    }
    var answer = 1;
    for (var g = 0; g < groups; g++) answer = (answer * 2) % MOD;
    return answer;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms