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.
A more efficient approach avoids the O(N^2) pairwise comparison by first sorting the ranges based on their start points. After sorting, we can find the connected components (groups of overlapping ranges) in a single linear scan. This is similar to the classic 'Merge Intervals' problem.
Algorithm
- Sort the
rangesarray based on the start points. - Initialize
components = 1andmaxEnd = ranges[0][1]. - Iterate through the sorted ranges from the second range (
i = 1toN-1). - For the current range
[start, end], ifstart <= maxEnd, updatemaxEnd = max(maxEnd, end). - If
start > maxEnd, it's a new component. Incrementcomponentsand updatemaxEnd = end. - After the loop, calculate
2^componentsmodulo10^9 + 7and return it.
Walkthrough
The key insight is that if we process ranges in increasing order of their start times, we only need to check for an overlap with the most recently formed component. The algorithm is as follows:
- Sort: Sort the
rangesarray in ascending order based on the start point of each range. - Merge and Count: We iterate through the sorted ranges to merge them and count the number of resulting disjoint components.
- We initialize a
componentscounter to 1 (for the first range) and amaxEndvariable to the end point of the first range. - We then iterate from the second range. For each range
[currentStart, currentEnd]:- If
currentStartis less than or equal tomaxEnd, it means the current range overlaps with the ongoing component. We merge it by updatingmaxEndto be the maximum of its current value andcurrentEnd. - If
currentStartis greater thanmaxEnd, the current range does not overlap with the previous component. This signifies the start of a new component. We increment thecomponentscounter and updatemaxEndtocurrentEnd.
- If
- We initialize a
- Calculate Result: After iterating through all ranges,
componentswill hold the number of disjoint groups,k. The total number of ways to assign thesekgroups to two sets is2^k. We compute this value modulo10^9 + 7.
import java.util.Arrays;import java.util.Comparator; class Solution { public int countWays(int[][] ranges) { int n = ranges.length; // Step 1: Sort ranges by their start points Arrays.sort(ranges, Comparator.comparingInt(a -> a[0])); int components = 1; int maxEnd = ranges[0][1]; // Step 2: Merge overlapping intervals and count components for (int i = 1; i < n; i++) { int currentStart = ranges[i][0]; int currentEnd = ranges[i][1]; if (currentStart <= maxEnd) { // Overlap: merge with the current component maxEnd = Math.max(maxEnd, currentEnd); } else { // No overlap: start a new component components++; maxEnd = currentEnd; } } // Step 3: Calculate 2^components mod 10^9 + 7 return (int) power(2, components); } 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 log N), where N is the number of ranges. The sorting step dominates the time complexity. The subsequent linear scan takes O(N) time.
Space
O(log N) or O(N), depending on the space complexity of the sorting algorithm used. In Java, `Arrays.sort` for objects uses Timsort, which requires O(N) space in the worst case. If we ignore the space used by the sorting algorithm, the extra space is O(1).
Trade-offs
Pros
Highly efficient and passes the given constraints.
Optimal time complexity for this problem.
Low auxiliary space complexity.
Cons
The solution is less direct than the graph approach and relies on the insight of sorting.
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; }}class Solution {public: int countWays(vector<vector<int>> &ranges) { sort(ranges.begin(), ranges.end()); int cnt = 0, mx = -1; for (auto &e : ranges) { cnt += e[0] > mx; mx = max(mx, e[1]); } using ll = long long; auto qpow = [&](ll a, int n, int mod) { ll ans = 1; for (; n; n >>= 1) { if (n & 1) { ans = ans * a % mod; } a = a * a % mod; } return ans; }; return qpow(2, cnt, 1e9 + 7); }};class Solution: def countWays(self, ranges: List[List[int]]) -> int: ranges . sort() cnt, mx = 0, - 1 for start, end in ranges: if start > mx: cnt += 1 mx = max(mx, end) mod = 10 ** 9 + 7 return pow(2, cnt, mod)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.