Matrix Vessel Detector 21 — Problem Statement & Solution Guide
Problem Description
You are provided with an array of positive integers, where each element represents the processing throughput of a specific sensor node in a distributed matrix detection system. A global threshold T defines the minimum aggregate throughput required to validate a detection event. Your objective is to identify the minimum number of sensor nodes that must be activated such that their combined throughput meets or exceeds T. If the sum of all available sensor throughputs is strictly less than T, the system cannot achieve the required threshold, and you must return -1.
To minimize the number of activated nodes, you must select the nodes with the highest individual throughputs first. This greedy strategy ensures that the cumulative sum reaches the target T with the fewest additions possible. The problem reduces to sorting the array in descending order and iterating through the elements, accumulating their values until the sum is at least T.
Input: An array of positive integers representing sensor throughputs and an integer T representing the target threshold.
Output: An integer representing the minimum count of sensors needed, or -1 if the target is unreachable.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Matrix Vessel Detector 21"
WHY DOES IT MATTER?
Greedy selection solves many resource‑allocation problems with minimal overhead.
OPTIMIZATION CHALLENGE
The key is reducing exponential subset search to a single sort and linear pass.
REAL-WORLD CONNECTION
It mirrors load‑balancing where you activate the most powerful servers first to meet demand.
Always verify the greedy choice property; a quick counter‑example test can save hours of debugging.
COMPLEXITY AT A GLANCE
O(N log N)O(1)Core Theory — Why This Approach?
The problem reduces to selecting the smallest subset of sensor throughputs whose sum meets or exceeds a global threshold T. A greedy strategy—sorting the throughputs in descending order and picking the largest values first—guarantees optimality because each chosen element contributes the maximum possible remaining throughput, minimizing the count needed. Naïve approaches such as exhaustive subset enumeration or DP over the sum dimension explode to O(2^N) or O(N·T) time, which is infeasible for N up to 10^5 and T up to 10^12. The optimal paradigm leverages the matroid property of the “minimum‑size covering” problem, allowing a simple sort plus linear scan to achieve O(N log N) time and O(1) extra space.
Interview Questions on This Problem
Q1Why does picking the largest throughputs first always yield the minimum number of nodes?
Because each selection maximally reduces the remaining deficit, and any solution that replaces a larger chosen value with a smaller one cannot use fewer elements.
Q2What is the time complexity of the greedy solution and which step dominates it?
The overall complexity is O(N log N), dominated by the sorting step; the subsequent linear scan is O(N).
Q3How would you modify the algorithm if the threshold T could be negative?
If T ≤ 0, zero nodes already satisfy the condition, so the answer is 0 without any processing.
Examples
Input
throughputs = [5, 1, 3, 4, 2], T = 10
Output
3
Explanation: Sort the throughputs in descending order: [5, 4, 3, 2, 1]. 1. Select 5. Sum = 5. Count = 1. (5 < 10) 2. Select 4. Sum = 9. Count = 2. (9 < 10) 3. Select 3. Sum = 12. Count = 3. (12 >= 10) Target reached. Return 3.
Input
throughputs = [10, 10, 10], T = 25
Output
3
Explanation: Sort the throughputs in descending order: [10, 10, 10]. 1. Select 10. Sum = 10. Count = 1. (10 < 25) 2. Select 10. Sum = 20. Count = 2. (20 < 25) 3. Select 10. Sum = 30. Count = 3. (30 >= 25) Target reached. Return 3.
Input
throughputs = [1, 2, 3], T = 100
Output
-1
Explanation: Sort the throughputs in descending order: [3, 2, 1]. 1. Select 3. Sum = 3. Count = 1. 2. Select 2. Sum = 5. Count = 2. 3. Select 1. Sum = 6. Count = 3. All elements processed. Total sum 6 is less than T (100). Return -1.
Input
throughputs = [7, 7, 7, 7], T = 14
Output
2
Explanation: Sort the throughputs in descending order: [7, 7, 7, 7]. 1. Select 7. Sum = 7. Count = 1. (7 < 14) 2. Select 7. Sum = 14. Count = 2. (14 >= 14) Target reached. Return 2.
Constraints
- 1 <= throughputs.length <= 10^5
- 1 <= throughputs[i] <= 10^9
- 1 <= T <= 10^14
Optimal Approach & Strategy
Sort the array in descending order and greedily accumulate until the sum reaches T (O(N log N)).
Brute Force Approach
Enumerate all subsets, compute their sums, and track the smallest subset meeting T (O(2^N)).
Verified Code Solutions
/**
* @param {number[]} throughputs
* @param {number} T
* @return {number}
*/
var minNodes = function(throughputs, T) {
throughputs.sort((a, b) => b - a);
let sum = 0;
for (let i = 0; i < throughputs.length; i++) {
sum += throughputs[i];
if (sum >= T) {
return i + 1;
}
}
return -1;
};class Solution {
public:
int minNodes(vector<int>& throughputs, int T) {
sort(throughputs.rbegin(), throughputs.rend());
int sum = 0;
for (int i = 0; i < throughputs.size(); ++i) {
sum += throughputs[i];
if (sum >= T) {
return i + 1;
}
}
return -1;
}
};class Solution {
public int minNodes(int[] throughputs, int T) {
Arrays.sort(throughputs);
int sum = 0;
for (int i = throughputs.length - 1; i >= 0; i--) {
sum += throughputs[i];
if (sum >= T) {
return throughputs.length - i;
}
}
return -1;
}
}class Solution:
def minNodes(self, throughputs: List[int], T: int) -> int:
throughputs.sort(reverse=True)
total = 0
for i, val in enumerate(throughputs):
total += val
if total >= T:
return i + 1
return -1/**
* @param {number[]} throughputs
* @param {number} T
* @return {number}
*/
var minNodes = function(throughputs, T) {
throughputs.sort((a, b) => b - a);
let sum = 0;
for (let i = 0; i < throughputs.length; i++) {
sum += throughputs[i];
if (sum >= T) {
return i + 1;
}
}
return -1;
};Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.