Minimum Runes to Add to Cast Spell Solution in Java

Ah, the age-old dilemma of casting spells without enough runes! It’s like trying to bake a cake without flour—sure, you can mix a bunch of other stuff, but good luck getting that fluffy texture! In the world of LeetCode, the problem of “Minimum Runes to Add to Cast Spell” is a delightful puzzle that challenges you to figure out how many additional runes you need to add to your magical arsenal to ensure you can cast your spells effectively.

Imagine you’re a wizard trying to impress your friends at a magical gathering. You’ve got the spells, the wand, and the flair, but alas! You’re missing a few runes. What do you do? Panic? No! You strategize!

Problem Description

In this problem, you are given:

• n: the number of components (think of them as magical realms).
• crystals: an array representing which components contain crystals (the magical essence).
• flowFrom and flowTo: arrays that represent directed edges between components (like pathways connecting different realms).

Your task is to determine the minimum number of additional runes you need to add to ensure that all components can be reached from at least one component that contains a crystal.

Solution in Java

Copy Code

class Solution {
  public int minRunesToAdd(int n, int[] crystals, int[] flowFrom, int[] flowTo) {
    List[] graph = new ArrayList[n];
    List[] reversedGraph = new ArrayList[n];

    for (int i = 0; i < n; ++i) {
      graph[i] = new ArrayList<>();
      reversedGraph[i] = new ArrayList<>();
    }

    for (int i = 0; i < flowFrom.length; ++i) {
      final int u = flowFrom[i];
      final int v = flowTo[i];
      graph[u].add(v);
      reversedGraph[v].add(u);
    }

    boolean[] seen = new boolean[n];
    List orderStack = new ArrayList<>();
    int[] componentIds = new int[n];
    int componentCount = 0;

    for (int i = 0; i < n; ++i)
      if (!seen[i])
        kosaraju(graph, i, seen, orderStack);

    Arrays.fill(componentIds, -1);

    for (int i = orderStack.size() - 1; i >= 0; --i) {
      final int u = orderStack.get(i);
      if (componentIds[u] == -1)
        identifySCC(reversedGraph, u, componentIds, componentCount++);
    }

    boolean[] hasCrystal = new boolean[componentCount];
    boolean[] hasInterComponentEdge = new boolean[componentCount];

    for (final int u : crystals)
      hasCrystal[componentIds[u]] = true;

    for (int i = 0; i < flowFrom.length; ++i) {
      final int id1 = componentIds[flowFrom[i]];
      final int id2 = componentIds[flowTo[i]];
      if (id1 != id2)
        hasInterComponentEdge[id2] = true;
    }

    int ans = 0;

    for (int i = 0; i < componentCount; ++i)
      if (!hasCrystal[i] && !hasInterComponentEdge[i])
        ++ans;

    return ans;
  }

  private void kosaraju(List[] graph, int u, boolean[] seen, List orderStack) {
    seen[u] = true;
    for (final int v : graph[u])
      if (!seen[v])
        kosaraju(graph, v, seen, orderStack);
    orderStack.add(u);
  }

  private void identifySCC(List[] reversedGraph, int u, int[] componentIds,
                           int componentId) {
    if (componentIds[u] != -1)
      return;
    componentIds[u] = componentId;
    for (final int v : reversedGraph[u])
      if (componentIds[v] == -1)
        identifySCC(reversedGraph, v, componentIds, componentId);
  }
}

Approach Explanation

The solution employs Kosaraju’s Algorithm to identify Strongly Connected Components (SCCs) in the directed graph formed by the components and their connections. The algorithm works in two main passes:

1. First Pass: Perform a depth-first search (DFS) to determine the order of nodes based on their finishing times.
2. Second Pass: Reverse the graph and perform DFS again to identify the SCCs.

Once the SCCs are identified, the algorithm checks which components contain crystals and which have inter-component edges. Finally, it counts how many components lack both crystals and inter-component edges, indicating the need for additional runes.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n + m)
Space Complexity	O(n + m)

Real-World Example

Imagine you’re organizing a magical festival where different realms (components) need to be connected to share their magical resources (crystals). If some realms are isolated and don’t have any magical essence, you’ll need to add runes (connections) to ensure everyone can participate in the festivities. The solution helps you figure out how many additional connections you need to make the festival a success!

Similar Problems

• Minimum Runes to Add to Cast Spell Solution in C++