LeetCode 1916: Count Ways to Build Rooms in an Ant Colony Solution

Master LeetCode problem 1916 (Count Ways to Build Rooms in an Ant Colony), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1916. Count Ways to Build Rooms in an Ant Colony

Hard

Math Dynamic Programming Tree Graph Topological Sort Combinatorics

Problem Explanation

Explanation:

To solve this problem, we can use dynamic programming with a topological ordering approach. We can first construct a directed graph where each node represents a room, and the edges represent the dependency relationship between rooms. Then, we can perform a topological sort to determine the order in which rooms should be built. After that, we can iterate over the sorted order and calculate the number of ways to build the rooms based on the dependencies.

Algorithm:
1. Construct a directed graph based on the dependencies provided in prevRoom.
2. Perform a topological sort to determine the order in which rooms should be built.
3. Initialize a dp array to track the number of ways to build each room based on the dependencies.
4. Iterate over the sorted order and update the dp array accordingly.
5. Return the total number of ways to build all rooms modulo 10^9 + 7.
Time Complexity: O(N), where N is the number of rooms.
Space Complexity: O(N) for storing the graph and dp array.

Solution Code

class Solution {
    public int waysToBuildRooms(int[] prevRoom) {
        int n = prevRoom.length;
        List<Integer>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 1; i < n; i++) {
            graph[prevRoom[i]].add(i);
        }

        int[] factorial = new int[n + 1];
        factorial[0] = 1;
        for (int i = 1; i <= n; i++) {
            factorial[i] = (int)((long)factorial[i - 1] * i % 1000000007);
        }

        int[] size = new int[n];
        int[] ways = new int[n];
        dfs(graph, 0, size, ways, factorial);

        return ways[0];
    }

    private void dfs(List<Integer>[] graph, int node, int[] size, int[] ways, int[] factorial) {
        size[node] = 1;
        ways[node] = 1;

        for (int child : graph[node]) {
            dfs(graph, child, size, ways, factorial);
            size[node] += size[child];
            ways[node] = (int)((long)ways[node] * factorial[size[child]] % 1000000007 * ways[child] % 1000000007);
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1916 (Count Ways to Build Rooms in an Ant Colony)?

This page provides optimized solutions for LeetCode problem 1916 (Count Ways to Build Rooms in an Ant Colony) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1916 (Count Ways to Build Rooms in an Ant Colony)?

The time complexity for LeetCode 1916 (Count Ways to Build Rooms in an Ant Colony) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1916 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1916 in Java, C++, or Python.

Back to LeetCode Solutions