Minimum Runes to Add to Cast Spell - Practice Coding Problems

Minimum Runes to Add to Cast Spell - Problem

Array Depth-First Search Breadth-First Search Union Find Graph Topological Sort Hard

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 an 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 i-th 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, OR
Receives magic flow from another focus point

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

Input & Output

Example 1 — Basic Magic Spell

$ Input: n = 4, crystals = [0], flowFrom = [1], flowTo = [2]

› Output: 2

💡 Note: Focus point 0 has a crystal (satisfied). Focus point 2 receives flow from point 1 (satisfied). Focus points 1 and 3 need additional runes to be satisfied, so answer is 2.

Example 2 — Multiple Crystals

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

› Output: 1

💡 Note: Focus points 0 and 2 have crystals (satisfied). Focus point 1 has no crystal and receives no flow, so needs 1 additional rune.

Example 3 — All Satisfied

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

› Output: 0

💡 Note: Focus point 0 has a crystal and focus point 1 receives flow from point 0. All points are satisfied, so no additional runes needed.

Constraints

1 ≤ n ≤ 10⁵
0 ≤ crystals.length ≤ n
0 ≤ crystals[i] < n
0 ≤ flowFrom.length = flowTo.length ≤ 10⁵
0 ≤ flowFrom[i], flowTo[i] < n

Visualization

Tap to expand

Understanding the Visualization

Focus Points

4 focus points numbered 0-3

Crystals & Flow

Point 0 has crystal, flow goes 1→2

Missing Connections

Points 1 and 3 need additional runes

Key Takeaway

🎯 Key Insight: Count nodes that neither have crystals nor receive flow

Asked in

G Google 15 a Amazon 12 f Facebook 8

The key insight is that each focus point must either contain a crystal OR receive magic flow from another point. The optimal solution uses set theory: create a set of all satisfied nodes (those with crystals + those receiving flow), then subtract from total nodes. Time: O(n + m), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Optimal Set Theory Solution	O(n + m)	O(n)	Count nodes that neither have crystals nor receive flow - this is the minimum runes needed
Brute Force Check	O(n + m)	O(n)	Check each focus point individually to see if it needs additional runes
DFS Reachability Analysis	O(n + m)	O(n + m)	Use DFS to find all nodes reachable from crystal nodes, then count unreachable nodes

Optimal Set Theory Solution — Algorithm Steps

Step 1: Create set of nodes with crystals
Step 2: Create set of nodes receiving flow
Step 3: Count nodes in neither set

Visualization

Tap to expand

Step-by-Step Walkthrough

Crystal Set

Identify all nodes with crystals

Flow Target Set

Identify all nodes receiving flow

Union & Count

Count nodes not in either set

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int solution(int n, int* crystals, int crystalsSize, int* flowFrom, int flowFromSize, int* flowTo, int flowToSize) {
    // Create boolean array for satisfied nodes
    bool* satisfied = (bool*)calloc(n, sizeof(bool));
    
    // Mark crystal nodes as satisfied
    for (int i = 0; i < crystalsSize; i++) {
        satisfied[crystals[i]] = true;
    }
    
    // Mark nodes receiving flow as satisfied
    for (int i = 0; i < flowToSize; i++) {
        satisfied[flowTo[i]] = true;
    }
    
    // Count satisfied nodes
    int satisfiedCount = 0;
    for (int i = 0; i < n; i++) {
        if (satisfied[i]) {
            satisfiedCount++;
        }
    }
    
    free(satisfied);
    return n - satisfiedCount;
}

int main() {
    int n;
    scanf("%d", &n);
    
    // Simple parsing for demonstration
    int crystals[1000], flowFrom[1000], flowTo[1000];
    int crystalsSize = 1, flowFromSize = 1, flowToSize = 1;
    
    crystals[0] = 0;
    flowFrom[0] = 1;
    flowTo[0] = 2;
    
    int result = solution(n, crystals, crystalsSize, flowFrom, flowFromSize, flowTo, flowToSize);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + m)

Single pass through crystals array and flowTo array

✓ Linear Growth

Space Complexity

O(n)

Set to track satisfied nodes

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimal Set Theory Solution — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler