# Count Ways to Group Overlapping Ranges **Difficulty:** MEDIUM [External](https://leetcode.com/problems/count-ways-to-group-overlapping-ranges) Canonical: https://scaleengineer.com/dsa/problems/count-ways-to-group-overlapping-ranges **Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting) **Data structures:** Array **Companies:** [IBM](https://scaleengineer.com/companies/ibm) --- ## Problem 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 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** `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 <= 105` * `ranges[i].length == 2` * `0 <= starti <= endi <= 109` # Approaches ## Brute Force using Graph and DFS/BFS 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. **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. **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. ### Explanation 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: 1. **Graph Construction**: We create an adjacency list representation of a graph with `N` vertices, where `N` is 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 if `s1 <= e2` and `s2 <= e1`. If they overlap, we add an undirected edge between the corresponding vertices in our graph. 2. **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 `visited` array to keep track of visited vertices. We iterate through all vertices from `0` to `N-1`. If a vertex `i` has not been visited, we start a traversal (DFS or BFS) from `i`, increment our component counter, and mark all reachable vertices as visited. 3. **Calculate Result**: Once we have the total number of components, `k`, the final answer is `2^k`. Since the answer can be large, we compute this value modulo `10^9 + 7` using modular exponentiation. ```java import java.util.ArrayList; import java.util.List; class Solution { public int countWays(int[][] ranges) { int n = ranges.length; List> 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> 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; } } ``` ### Algorithm - Initialize an adjacency list for `N` ranges. - Iterate through all unique pairs of ranges `(i, j)`. - If `ranges[i]` and `ranges[j]` overlap, add an edge between nodes `i` and `j`. - Initialize a `visited` array and a `components` counter to 0. - Iterate from `i = 0` to `N-1`. If node `i` is not visited, increment `components` and start a DFS/BFS from `i` to mark all nodes in the component as visited. - Calculate `2^components` modulo `10^9 + 7` and return the result. ## Efficient Approach using Sorting and Merging 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. **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). **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. ### Explanation 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: 1. **Sort**: Sort the `ranges` array in ascending order based on the start point of each range. 2. **Merge and Count**: We iterate through the sorted ranges to merge them and count the number of resulting disjoint components. - We initialize a `components` counter to 1 (for the first range) and a `maxEnd` variable to the end point of the first range. - We then iterate from the second range. For each range `[currentStart, currentEnd]`: - If `currentStart` is less than or equal to `maxEnd`, it means the current range overlaps with the ongoing component. We merge it by updating `maxEnd` to be the maximum of its current value and `currentEnd`. - If `currentStart` is greater than `maxEnd`, the current range does not overlap with the previous component. This signifies the start of a new component. We increment the `components` counter and update `maxEnd` to `currentEnd`. 3. **Calculate Result**: After iterating through all ranges, `components` will hold the number of disjoint groups, `k`. The total number of ways to assign these `k` groups to two sets is `2^k`. We compute this value modulo `10^9 + 7`. ```java 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; } } ``` ### Algorithm - Sort the `ranges` array based on the start points. - Initialize `components = 1` and `maxEnd = ranges[0][1]`. - Iterate through the sorted ranges from the second range (`i = 1` to `N-1`). - For the current range `[start, end]`, if `start <= maxEnd`, update `maxEnd = max(maxEnd, end)`. - If `start > maxEnd`, it's a new component. Increment `components` and update `maxEnd = end`. - After the loop, calculate `2^components` modulo `10^9 + 7` and return it. # Solutions ### Java ```java 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; } } ``` ### CPP ```cpp class Solution { public: int countWays(vector> &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); } }; ``` ### Python ```python 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) ```