Count Ways to Group Overlapping Ranges
MedPrompt
You are given a 2D integer array ranges where ranges[i] = [starti, endi] denotes that all integers between starti and endi (both inclusive) are contained in the ith 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 because2and3occur 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 109 + 7.
Example 1:
Input: ranges = [[6,10],[5,15]]
Output: 2
Explanation:
The two ranges are overlapping, so they must be in the same group.
Thus, there are two possible ways:
- Put both the ranges together in group 1.
- Put both the ranges together in group 2.Example 2:
Input: ranges = [[1,3],[10,20],[2,5],[4,8]]
Output: 4
Explanation:
Ranges [1,3], and [2,5] are overlapping. So, they must be in the same group.
Again, ranges [2,5] and [4,8] are also overlapping. So, they must also be in the same group.
Thus, there are four possible ways to group them:
- All the ranges in group 1.
- All the ranges in group 2.
- Ranges [1,3], [2,5], and [4,8] in group 1 and [10,20] in group 2.
- Ranges [1,3], [2,5], and [4,8] in group 2 and [10,20] in group 1.
Constraints:
1 <= ranges.length <= 105ranges[i].length == 20 <= starti <= endi <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
This approach models the problem as a graph problem. Each range is a node, and an edge connects two nodes if their corresponding ranges overlap. The problem then reduces to finding the number of connected components in this graph. If there are k connected components, each component can be independently assigned to one of two groups, leading to 2^k total ways.
Algorithm
- Initialize an adjacency list for
Nranges. - Iterate through all unique pairs of ranges
(i, j). - If
ranges[i]andranges[j]overlap, add an edge between nodesiandj. - Initialize a
visitedarray and acomponentscounter to 0. - Iterate from
i = 0toN-1. If nodeiis not visited, incrementcomponentsand start a DFS/BFS fromito mark all nodes in the component as visited. - Calculate
2^componentsmodulo10^9 + 7and return the result.
Walkthrough
The core idea is that all overlapping ranges must be in the same group. This transitive relationship defines equivalence classes, which correspond to the connected components of a graph. The algorithm proceeds as follows:
- Graph Construction: We create an adjacency list representation of a graph with
Nvertices, whereNis the number of ranges. We iterate through every pair of ranges. For each pair, we check if they overlap. An overlap between range[s1, e1]and[s2, e2]occurs ifs1 <= e2ands2 <= e1. If they overlap, we add an undirected edge between the corresponding vertices in our graph. - Count Connected Components: After building the graph, we traverse it to count the number of connected components. We can use Depth First Search (DFS) or Breadth First Search (BFS). We maintain a
visitedarray to keep track of visited vertices. We iterate through all vertices from0toN-1. If a vertexihas not been visited, we start a traversal (DFS or BFS) fromi, increment our component counter, and mark all reachable vertices as visited. - Calculate Result: Once we have the total number of components,
k, the final answer is2^k. Since the answer can be large, we compute this value modulo10^9 + 7using modular exponentiation.
import java.util.ArrayList;import java.util.List; class Solution { public int countWays(int[][] ranges) { int n = ranges.length; List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) { adj.add(new ArrayList<>()); } // Step 1: Build the graph by checking all pairs for overlap for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (ranges[i][0] <= ranges[j][1] && ranges[j][0] <= ranges[i][1]) { adj.get(i).add(j); adj.get(j).add(i); } } } // Step 2: Count connected components using DFS boolean[] visited = new boolean[n]; int components = 0; for (int i = 0; i < n; i++) { if (!visited[i]) { components++; dfs(i, adj, visited); } } // Step 3: Calculate 2^components mod 10^9 + 7 return (int) power(2, components); } private void dfs(int u, List<List<Integer>> adj, boolean[] visited) { visited[u] = true; for (int v : adj.get(u)) { if (!visited[v]) { dfs(v, adj, visited); } } } private long power(long base, long exp) { long res = 1; long mod = 1_000_000_007; base %= mod; while (exp > 0) { if (exp % 2 == 1) res = (res * base) % mod; base = (base * base) % mod; exp /= 2; } return res; }}Complexity
Time
O(N^2), where N is the number of ranges. Building the graph requires checking O(N^2) pairs. Counting components is O(N + E), where E can be up to O(N^2). Thus, the overall complexity is dominated by graph construction.
Space
O(N^2) in the worst case. The adjacency list can store up to O(N^2) edges if the graph is dense. The `visited` array and recursion stack for DFS take O(N) space.
Trade-offs
Pros
The approach is a direct translation of the problem's constraints into a standard graph problem, making it easy to understand.
It correctly solves the problem for small inputs.
Cons
The O(N^2) time complexity is too slow for the given constraints (N up to 10^5), leading to a Time Limit Exceeded (TLE) error.
The O(N^2) space complexity can be very high, potentially causing a Memory Limit Exceeded error for large N.
Solutions
Solution
class Solution {public int countWays(int[][] ranges) { Arrays.sort(ranges, (a, b)->a[0] - b[0]); int cnt = 0, mx = -1; for (int[] e : ranges) { if (e[0] > mx) { ++cnt; } mx = Math.max(mx, e[1]); } return qpow(2, cnt, (int)1 e9 + 7); }private int qpow(long a, int n, int mod) { long ans = 1; for (; n > 0; n >>= 1) { if ((n & 1) == 1) { ans = ans * a % mod; } a = a * a % mod; } return (int)ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.