BackmediumArrays arrays medium

Minimum Node Activation Set Solution

Problem Statement

You are given an integer `N`, representing the total count of unique nodes labeled from `0` to `N-1`. You are also provided with `messages`, a list of lists of integers. Each inner list `messages[i]` represents a specific message and contains the distinct node labels that message `i` activates. Your task is to find the minimum number of messages you need to select from `messages` such that all `N` nodes (from `0` to `N-1`) are activated. If it's impossible to activate all `N` nodes using the given messages, return -1.

Example 1
Input
N = 4, messages = [[0, 1], [1, 2], [2, 3], [0, 3]]
Output
2

Explanation: Selecting messages `[0, 1]` and `[2, 3]` activates nodes {0, 1, 2, 3}. Another valid combination is `[0, 3]` and `[1, 2]`. This is the minimum possible.

Constraints

  • 1 <= N <= 16
  • 1 <= messages.length <= 100
  • 0 <= messages[i].length <= N
  • 0 <= node_label < N for all nodes in `messages[i]`
  • Each `messages[i]` contains unique node labels.

More Arrays Problems

Move Zeros to EndeasyCumulative Array SumeasyFind Balance IndexeasySorted Squareseasy
View all problems →
Live Compiler
Loading...
Test Cases & Output
🔒 Sign up to run your code

🚀 Practice this problem

Run code, get AI hints & track streak

Sign Up Free