Protocol Pipeline Analyzer 7 — Problem Statement & Solution Guide
Problem Description
You are tasked with processing a stream of integer values representing telemetry data from a distributed system. The goal is to compute the cumulative sum of the first k distinct values encountered in the sequence. If the sequence contains fewer than k distinct values, return the sum of all distinct values present. The order of appearance determines which values are considered 'first'.
Given an array of integers nums and an integer k, return the sum of the first k unique elements in the order they appear. If k is greater than the total number of unique elements, return the sum of all unique elements.
For example, if nums = [1, 2, 2, 3, 4] and k = 3, the unique elements in order are [1, 2, 3], and the sum is 1 + 2 + 3 = 6.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Protocol Pipeline Analyzer 7"
WHY DOES IT MATTER?
The two‑pointer / sliding‑window pattern is fundamental for any scenario where you need to process a contiguous segment of data with constraints on uniqueness, length, or sum. Mastering this pattern enables engineers to write linear‑time solutions for streaming analytics, rate‑limiting, and windowed aggregations.
OPTIMIZATION CHALLENGE
The key insight is that once a value is marked as ‘seen’, it never needs to be revisited. By coupling a hash set with a single forward scan, we eliminate the need for nested loops or repeated searches, collapsing the time complexity from quadratic to linear.
REAL-WORLD CONNECTION
In distributed telemetry pipelines, services often need to compute metrics over the first k unique event types (e.g., error codes) to trigger alerts. The algorithm mirrors how a monitoring agent would keep a small hash set of seen error codes and update a cumulative severity score on the fly.
During an interview, write the hash‑set insertion and sum update in one line, and immediately guard the k‑limit with a simple if‑statement. This keeps the code concise, avoids off‑by‑one errors, and demonstrates that you understand early termination.
COMPLEXITY AT A GLANCE
O(n)O(k)Core Theory — Why This Approach?
The problem asks for the sum of the first k distinct integers in a stream, preserving the order of first appearance. A naive solution would scan the entire array for each element, checking whether it has already been seen, which leads to O(n·k) or O(n²) time in the worst case. The optimal approach leverages the two‑pointer (or sliding‑window) paradigm combined with a hash set to record distinct values on‑the‑fly, allowing us to traverse the stream exactly once while maintaining a running sum of unique elements. This linear‑time strategy works because the order of distinctness is dictated solely by the first occurrence, so once a value is added to the set it never needs to be reconsidered, and the pointer never moves backward.
Two‑pointer techniques excel when we need to process contiguous subsequences or maintain a dynamic window over a sequence. Here, the ‘left’ pointer is implicit (the start of the stream) and the ‘right’ pointer advances through each telemetry value. As each new value arrives, we check the hash set: if it is unseen and we have not yet collected k distinct numbers, we add it to the sum and the set; otherwise we simply skip it. This yields O(n) time and O(k) auxiliary space, which scales gracefully even for massive telemetry logs that cannot fit entirely in memory.
Interview Questions on This Problem
Q1How would you modify the solution if the stream is infinite and you must output the sum after every new distinct element until k distinct values are seen?
Maintain the same hash set and running sum; after each insertion of a new distinct value, emit the current sum. Once the set size reaches k, you can stop emitting or continue emitting the same sum for subsequent elements, depending on the requirement.
Q2What changes are needed if the problem asks for the sum of the last k distinct values instead of the first k distinct values?
Use a doubly‑linked list (or deque) together with a hash map that stores node references. When a new distinct value arrives, append it to the tail; if the map already contains the value, remove its previous node before re‑adding. Keep the list size at k by popping from the head when it exceeds k, updating the sum accordingly.
Q3Can you solve the problem in O(1) additional space while still running in O(n) time? Why or why not?
No, because we must remember which values have already been counted to avoid duplicates. Without at least O(k) extra storage (e.g., a hash set), we cannot guarantee that we correctly identify distinct elements, especially when the value range is large or unbounded.
Examples
Input
nums = [5, 3, 5, 8, 3, 2], k = 3
Output
16
Explanation: The unique elements in order of appearance are [5, 3, 8, 2]. The first 3 unique elements are 5, 3, and 8. Their sum is 5 + 3 + 8 = 16.
Input
nums = [1, 1, 1, 1], k = 2
Output
1
Explanation: The only unique element is [1]. Since k=2 is greater than the number of unique elements (1), we sum all unique elements: 1.
Input
nums = [10, 20, 30, 40, 50], k = 5
Output
150
Explanation: All elements are unique. The first 5 unique elements are [10, 20, 30, 40, 50]. Their sum is 10 + 20 + 30 + 40 + 50 = 150.
Input
nums = [7, 7, 8, 8, 9, 9, 10], k = 4
Output
34
Explanation: The unique elements in order are [7, 8, 9, 10]. The first 4 unique elements are 7, 8, 9, and 10. Their sum is 7 + 8 + 9 + 10 = 34.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- 1 <= k <= 10^5
Optimal Approach & Strategy
Traverse the array once, using a hash set to record distinct values and a running sum; stop when the set size reaches k or the array ends.
Brute Force Approach
Iterate over each element and, for each, scan all previous elements to check if it is a new distinct value, accumulating the sum until k distinct numbers are found.
Verified Code Solutions
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var sumFirstKDistinct = function(nums, k) {
const seen = new Set();
let sum = 0;
let count = 0;
for (let num of nums) {
if (!seen.has(num)) {
seen.add(num);
sum += num;
count++;
if (count === k) break;
}
}
return sum;
};class Solution {
public:
int sumFirstKDistinct(vector<int>& nums, int k) {
unordered_set<int> seen;
long long sum = 0;
int count = 0;
for (int num : nums) {
if (seen.find(num) == seen.end()) {
seen.insert(num);
sum += num;
count++;
if (count == k) break;
}
}
return (int)sum;
}
};class Solution {
public int sumFirstKDistinct(int[] nums, int k) {
Set<Integer> seen = new HashSet<>();
int sum = 0;
int count = 0;
for (int num : nums) {
if (!seen.contains(num)) {
seen.add(num);
sum += num;
count++;
if (count == k) break;
}
}
return sum;
}
}class Solution:
def sumFirstKDistinct(self, nums: List[int], k: int) -> int:
seen = set()
total = 0
count = 0
for num in nums:
if num not in seen:
seen.add(num)
total += num
count += 1
if count == k:
break
return total/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var sumFirstKDistinct = function(nums, k) {
const seen = new Set();
let sum = 0;
let count = 0;
for (let num of nums) {
if (!seen.has(num)) {
seen.add(num);
sum += num;
count++;
if (count === k) break;
}
}
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.