Skip to main content
Talentd

Minimum Runes to Add to Cast Spell - Solution & Explanation

HardPremiumFree on FleetCodeArrayDepth-First SearchBreadth-First SearchUnion Find7 min readAsked at: De Shaw
Practice this problem

Problem Statement

Alice has just graduated from wizard school, and wishes to cast a magic spell to celebrate. The magic spell contains certain focus points where magic needs to be concentrated, and some of these focus points contain magic crystals which serve as the spell's energy source. Focus points can be linked through directed runes, which channel magic flow from one focus point to another.

You are given a integer n denoting the number of focus points and an array of integers crystals where crystals[i] indicates a focus point which holds a magic crystal. You are also given two integer arrays flowFrom and flowTo, which represent the existing directed runes. The ith rune allows magic to freely flow from focus point flowFrom[i] to focus point flowTo[i].

You need to find the number of directed runes Alice must add to her spell, such that each focus point either:

  • Contains a magic crystal.
  • Receives magic flow from another focus point.

Return the minimum number of directed runes that she should add.

 

Example 1:

Input: n = 6, crystals = [0], flowFrom = [0,1,2,3], flowTo = [1,2,3,0]

Output: 2

Explanation: 

Add two directed runes:

  • From focus point 0 to focus point 4.
  • From focus point 0 to focus point 5.

Example 2:

Input: n = 7, crystals = [3,5], flowFrom = [0,1,2,3,5], flowTo = [1,2,0,4,6]

Output: 1

Explanation: 

Add a directed rune from focus point 4 to focus point 2.

 

Constraints:

  • 2 <= n <= 105
  • 1 <= crystals.length <= n
  • 0 <= crystals[i] <= n - 1
  • 1 <= flowFrom.length == flowTo.length <= min(2 * 105, (n * (n - 1)) / 2)
  • 0 <= flowFrom[i], flowTo[i] <= n - 1
  • flowFrom[i] != flowTo[i]
  • All pre-existing directed runes are distinct.

Approach Overview

Problem Overview: You are given runes connected by dependency rules where one rune may require another before it can be used. Some runes are already available. The goal is to determine the minimum number of additional runes you must add so every rune in the system can eventually be activated through the dependency graph.

Approach 1: Direct Reachability Simulation (BFS/DFS from Each Missing Rune) (Time: O(n*(n+m)), Space: O(n+m))

Start by building the directed graph of rune dependencies using adjacency lists. Run BFS or DFS from all initially available runes to mark reachable nodes. For every rune that remains unreachable, simulate adding that rune and run another traversal to see how many additional nodes become reachable. This brute-force style approach helps verify correctness but repeatedly explores the graph, making it inefficient for large inputs. It is useful for understanding how reachability propagates through a dependency graph.

Approach 2: Topological Dependency Tracking (Time: O(n+m), Space: O(n+m))

Treat the runes as nodes in a directed graph and compute indegrees for each node. Perform a traversal similar to topological sort starting from runes that are already available. Each time a rune becomes reachable, decrease the indegree of its neighbors. Nodes that never reach indegree zero remain blocked because none of their prerequisite chains start from an available rune. Counting these independent blocked chains provides a better estimate of how many additional starting runes are needed.

Approach 3: Strongly Connected Components + Condensed Graph (Optimal) (Time: O(n+m), Space: O(n+m))

Cycles in the dependency graph mean several runes must be activated together. Compress the graph into strongly connected components using Kosaraju or Tarjan from Depth-First Search. Each SCC becomes a single node in a condensed DAG. Next, mark all SCCs reachable from the initially available runes using a traversal. In the condensed graph, count SCCs that are not reachable and have zero incoming edges from other unreachable components. Each such component requires adding one rune to start the chain. This works because activating one rune in that component unlocks the entire cycle.

Recommended for interviews: The SCC condensation approach. Interviewers expect candidates to recognize that cycles must be collapsed before analyzing dependency flow. Using graph traversal and topological sort ideas reduces the problem to counting source components in a DAG. Brute-force reachability demonstrates understanding, but the SCC-based solution shows strong graph modeling skills.

Solution

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Repeated BFS/DFS ReachabilityO(n*(n+m))O(n+m)Conceptual understanding or very small graphs
Topological Dependency TrackingO(n+m)O(n+m)When the dependency graph behaves like a DAG
SCC + Condensed DAG (Optimal)O(n+m)O(n+m)General case with cycles in dependency graph

Frequently Asked Questions

Is Minimum Runes to Add to Cast Spell easy or hard?
Minimum Runes to Add to Cast Spell is classified as Hard because it combines multiple graph concepts: reachability, strongly connected components, and reasoning on a condensed DAG. Candidates must recognize cycles and transform the graph before counting the minimal starting components.
Minimum Runes to Add to Cast Spell Python/Java solution
The implementation builds an adjacency list, runs a DFS-based SCC algorithm such as Tarjan or Kosaraju, constructs a condensed DAG, and counts zero‑indegree unreachable components. The same logic translates cleanly across Python, Java, C++, Go, and TypeScript because it relies on standard graph traversal patterns.
How to solve Minimum Runes to Add to Cast Spell in O(n+m)?
Build the dependency graph and compute strongly connected components using DFS. Compress each component into a single node to form a DAG. Mark components reachable from the initially available runes. Among the remaining components, count those with zero incoming edges in the condensed graph. Each such component requires adding one rune.
What is the best approach for Minimum Runes to Add to Cast Spell?
The most reliable approach uses Strongly Connected Components (SCC) with graph condensation. First collapse cycles using Tarjan or Kosaraju DFS, then build a condensed DAG. Count the SCCs that are not reachable from existing runes and have zero incoming edges from other unreachable components. This runs in O(n+m) time and handles cyclic dependencies correctly.
Is Minimum Runes to Add to Cast Spell asked at Google/Amazon/Meta?
Problems combining SCC, graph reachability, and dependency resolution are common in interviews at companies like Google, Amazon, and Meta. Variants appear in system dependency resolution, build systems, and package management style questions. Interviewers typically expect a graph modeling approach with SCC or topological reasoning.
What data structure is used in Minimum Runes to Add to Cast Spell?
The core structure is a directed graph stored with adjacency lists. DFS stacks or recursion are used for SCC detection, and arrays track visited nodes, component IDs, and indegrees in the condensed graph. These structures allow efficient O(n+m) traversal and dependency analysis.
What is the time complexity of Minimum Runes to Add to Cast Spell?
The optimal algorithm runs in O(n+m) time where n is the number of runes and m is the number of dependency edges. SCC detection takes O(n+m), and the reachability traversal on the condensed graph also takes O(n+m). Space complexity is O(n+m) for adjacency lists and component storage.

Ready to solve this problem?

Practice Minimum Runes to Add to Cast Spell with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Edge Weight Equilibrium Queries in a Tree

Next

Minimum Number of Days to Disconnect Island