We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Runes to Add to Cast Spell

Number: 3718

Difficulty: Hard

Paid? Yes

Companies: N/A

Problem Description

We are given n focus points. Some focus points hold magic crystals and there exist pre‐established directed runes (edges) that channel magic from one focus point to another. To successfully cast the spell, every focus point must either contain a crystal or be able to receive magic from another focus point (via one or more directed rune flows). The task is to return the minimum number of additional directed runes that must be added so that every focus point satisfies this property.

Key Insights

  • The directed rune network can be viewed as a graph where nodes (focus points) are “powered” if they initially contain a crystal.
  • Magic can propagate: if a powered node has a directed edge to another node, that node becomes powered.
  • Compute, by BFS/DFS, the set of nodes reachable (and therefore powered) starting from all nodes that have crystals.
  • Not powered nodes possibly form separate connected “components” (through their directed connectivity) that can be powered by adding a single rune into each component.
  • The answer is the number of such disjoint groups (of unpowered nodes) that cannot be reached by any propagation starting from an initial crystal.

Space and Time Complexity

Time Complexity: O(n + m), where m is the number of existing runes.
Space Complexity: O(n + m) for storing the graph and auxiliary data structures.

Solution

We first build a graph with an adjacency list to represent existing directed runes. Then, we start from every focus point that initially contains a magic crystal and perform a BFS (or DFS) to mark every focus point that becomes powered through propagation. After this, any focus point that remains unpowered must be addressed by adding a new directed rune. However, note that adding a rune to any one focus point in a connected group of unpowered nodes will power the entire group (because magic will then cascade through their outgoing connections). Thus, we perform another BFS/DFS over the unpowered nodes grouped by connectivity (using the same directed edges) and count one additional rune per group.

The key mental leap is to recognize that powering one node in each “component” of unreachable nodes is enough to make the entire component powered, hence we only add as many runes as there are unpowered connected groups.

Code Solutions

# Python solution using BFS
from collections import deque, defaultdict

def minimumRunesToAdd(n, crystals, flowFrom, flowTo):
    # Build the graph as an adjacency list
    graph = defaultdict(list)
    m = len(flowFrom)
    for i in range(m):
        # rune from u (flowFrom) to v (flowTo)
        u, v = flowFrom[i], flowTo[i]
        graph[u].append(v)
    
    # Initialize powered status for each node.
    powered = [False] * n
    queue = deque()
    
    # Start BFS from each focus point that contains a crystal.
    for node in crystals:
        if not powered[node]:
            powered[node] = True
            queue.append(node)
    
    # Propagate magic flow to mark powered nodes.
    while queue:
        current = queue.popleft()
        for neighbor in graph[current]:
            if not powered[neighbor]:
                powered[neighbor] = True
                queue.append(neighbor)
    
    additional_runes = 0
    # For each still unpowered node, perform BFS to mark its connected component.
    for i in range(n):
        if not powered[i]:
            additional_runes += 1  # we add one rune to power this component
            queue.append(i)
            powered[i] = True  # mark as powered after adding a rune
            
            while queue:
                current = queue.popleft()
                for neighbor in graph[current]:
                    if not powered[neighbor]:
                        powered[neighbor] = True
                        queue.append(neighbor)
    
    return additional_runes

# Example usage:
print(minimumRunesToAdd(6, [0], [0,1,2,3], [1,2,3,0]))  # Output: 2
print(minimumRunesToAdd(7, [3,5], [0,1,2,3,5], [1,2,0,4,6]))  # Output: 1
← Back to All Questions