Sensor Packet Tracker 13 — Problem Statement & Solution Guide
Problem Description
A distributed sensor network transmits a sequence of integer packet identifiers. To optimize bandwidth allocation for the next cycle, the system administrator must identify the top K highest priority packets. Given an array packets representing the identifiers and an integer K, compute the sum of the K largest values in the array.
The solution must efficiently handle large datasets where sorting the entire array is suboptimal. You are required to implement a method that returns the aggregate sum of the top K elements. If K is greater than the number of elements, return the sum of all elements.
Input: An array of integers packets and an integer K.
Output: A single integer representing the sum of the K largest values.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Sensor Packet Tracker 13"
WHY DOES IT MATTER?
Selecting top‑K values is a core building block for ranking, recommendation, and resource allocation systems.
OPTIMIZATION CHALLENGE
The key is to avoid sorting the entire dataset, reducing work from O(N log N) to O(N log K).
REAL-WORLD CONNECTION
Think of a network router keeping the K highest‑priority packets to prioritize bandwidth.
Initialize the heap with the first K items, then stream through the rest, swapping only when a larger value arrives.
COMPLEXITY AT A GLANCE
O(N log K)O(K)Core Theory — Why This Approach?
The naive method—sorting the entire array or scanning it K times—requires O(N log N) or O(K·N) time, which becomes prohibitive when N reaches millions and K is large. A more optimal paradigm leverages a min‑heap of size K to maintain the current K largest elements, ensuring each insertion or replacement costs O(log K) and the overall traversal stays linear.
By keeping only K elements in the heap, we reduce both time and auxiliary space compared to full sorting, while still guaranteeing that the smallest element in the heap is the K‑th largest overall. This approach exemplifies the “selection” problem, where we seek a subset of extreme values without ordering the entire dataset, a common pattern in streaming and real‑time analytics.
Interview Questions on This Problem
Q1What data structure allows you to keep track of the K largest elements efficiently?
A min‑heap (priority queue) of size K does. It lets you replace the smallest of the K when a larger element appears.
Q2How does the time complexity of the heap‑based solution compare to sorting the whole array?
Heap‑based runs in O(N log K) versus O(N log N) for full sort. When K ≪ N, the gain is substantial.
Q3Can you solve the problem in O(N) average time, and what trade‑off does that involve?
Yes, using Quickselect to partition around the K‑th largest element. It sacrifices worst‑case guarantees and is harder to implement correctly.
Examples
Input
packets = [12, 45, 7, 90, 33, 5], K = 3
Output
168
Explanation: The three largest values in the array are 90, 45, and 33. Summing these values: 90 + 45 + 33 = 168.
Input
packets = [100, 100, 100, 100], K = 2
Output
200
Explanation: The two largest values are both 100. Summing them: 100 + 100 = 200.
Input
packets = [-5, -1, -10, -2], K = 2
Output
-3
Explanation: The two largest values (closest to positive infinity) are -1 and -2. Summing them: -1 + (-2) = -3.
Input
packets = [42], K = 5
Output
42
Explanation: Since K (5) is greater than the array length (1), we sum all available elements. The only element is 42, so the sum is 42.
Constraints
- 1 <= packets.length <= 10^5
- -10^9 <= packets[i] <= 10^9
- 1 <= K <= 10^5
Optimal Approach & Strategy
Use a min‑heap of size K to keep only the top K values during a single O(N) pass, achieving O(N log K) time and O(K) space.
Brute Force Approach
Sort the entire array and sum the last K elements, which costs O(N log N) time and O(1) extra space.
Verified Code Solutions
function solution(nums, k) {
if (k > nums.length) {
k = nums.length;
}
nums.sort((a, b) => b - a);
let sum = 0;
for (let i = 0; i < k; i++) {
sum += nums[i];
}
return sum;
}class Solution {
public:
int solution(vector<int>& nums, int k) {
if (k > nums.size()) {
k = nums.size();
}
sort(nums.begin(), nums.end(), greater<int>());
int sum = 0;
for (int i = 0; i < k; i++) {
sum += nums[i];
}
return sum;
}
};class Solution {
public int solution(int[] nums, int k) {
if (k > nums.length) {
k = nums.length;
}
Arrays.sort(nums);
int sum = 0;
for (int i = 0; i < k; i++) {
sum += nums[i];
}
return sum;
}
}def solution(nums, k):
if k > len(nums):
k = len(nums)
nums.sort(reverse=True)
sum = 0
for i in range(k):
sum += nums[i]
return sumfunction solution(nums, k) {
if (k > nums.length) {
k = nums.length;
}
nums.sort((a, b) => b - a);
let sum = 0;
for (let i = 0; i < k; i++) {
sum += nums[i];
}
return sum;
}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.