Merging Segments of Student Performance — Problem Statement & Solution Guide
Problem Description
You are provided with an integer n representing the total number of recorded performance entries, followed by n pairs of integers (segmentId, score). Each pair corresponds to a specific academic segment identified by segmentId and the numerical score achieved in that segment. Multiple entries may share the same segmentId, indicating repeated assessments or contributions to the same segment.
Your task is to aggregate the scores for each distinct segmentId. For every unique identifier found in the input, compute the cumulative sum of all associated scores. The final result should be a list of pairs [segmentId, totalScore], where totalScore is the sum of all scores corresponding to that segmentId.
The output list must be sorted in ascending order based on segmentId. The solution must achieve a time complexity of O(n log n) or better and utilize O(n) auxiliary space.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Merging Segments of Student Performance"
WHY DOES IT MATTER?
Aggregating by key is a foundational pattern for summarizing logs, metrics, and transactional data; mastering it enables efficient data reduction before further analysis.
OPTIMIZATION CHALLENGE
Recognizing that a hash map provides O(1) amortized inserts and lookups eliminates the need for nested loops, and the only remaining cost is sorting the distinct keys, which is optimal for unordered identifiers.
REAL-WORLD CONNECTION
Think of a distributed log‑aggregation service where each server tags log lines with a service ID; the central collector must sum error counts per service, analogous to summing scores per student segment.
Reserve the hash map size to n before insertion to avoid rehashing, and use stable_sort only if you need to preserve original order for equal ids; otherwise, a simple sort on the key vector is fastest.
COMPLEXITY AT A GLANCE
O(n log n)O(n)Core Theory — Why This Approach?
The problem is a classic aggregation task where we need to collapse multiple records sharing the same identifier into a single summary. A naïve solution would scan the list for each distinct id, summing matching scores, which leads to O(n²) time on worst‑case inputs because each element could be revisited many times. The optimal paradigm leverages a hash‑based map (e.g., unordered_map) to accumulate scores in a single linear pass, guaranteeing O(n) expected time for the aggregation phase. After all totals are computed, we must present the results ordered by id; sorting the distinct keys costs O(k log k) where k ≤ n, yielding an overall O(n log n) bound that meets the requirement while using only O(k) extra space for the map and the output list.
Interview Questions on This Problem
Q1How would you modify the solution if the ids are guaranteed to be in the range [1, 10⁶] and you need O(n) total time without a comparison sort?
Use a counting array (or vector) of size 10⁶+1 to accumulate scores directly; this gives O(n) time and O(10⁶) space, which is linear relative to the bounded id range.
Q2A fintech platform receives millions of transaction records per second. Which part of this algorithm becomes a bottleneck and how would you scale it?
The aggregation map can become a contention point; sharding the input stream by id hash and maintaining per‑shard hash maps reduces lock contention, and a final reduce‑by‑key step merges the partial results.
Q3In a high‑growth startup, you are asked to return the top‑k ids by totalScore instead of the full sorted list. What change would you make?
Maintain a min‑heap of size k while iterating over the map entries; each entry is pushed onto the heap and the smallest is popped when the heap exceeds k, resulting in O(n log k) time and O(k) extra space.
Examples
Input
n = 5 pairs = [[1, 10], [2, 20], [1, 5], [3, 15], [2, 5]]
Output
[[1, 15], [2, 25], [3, 15]]
Explanation: Segment 1 has scores 10 and 5, summing to 15. Segment 2 has scores 20 and 5, summing to 25. Segment 3 has score 15, summing to 15. Sorting by ID yields [[1, 15], [2, 25], [3, 15]].
Input
n = 3 pairs = [[10, 100], [10, 200], [5, 50]]
Output
[[5, 50], [10, 300]]
Explanation: Segment 10 has scores 100 and 200, summing to 300. Segment 5 has score 50, summing to 50. Sorting by ID yields [[5, 50], [10, 300]].
Input
n = 4 pairs = [[1, 1], [2, 2], [3, 3], [4, 4]]
Output
[[1, 1], [2, 2], [3, 3], [4, 4]]
Explanation: Each segment ID is unique. The sums are identical to the individual scores. Sorting by ID yields [[1, 1], [2, 2], [3, 3], [4, 4]].
Constraints
- 1 <= n <= 10^5
- 1 <= segmentId <= 10^9
- -10^9 <= score <= 10^9
- The sum of scores for any segmentId fits within a 64-bit integer.
Optimal Approach & Strategy
Use a hash map to accumulate sums in linear time, then sort the unique ids to produce the ordered output.
Brute Force Approach
Iterate over every pair, and for each distinct id scan the entire list again to sum matching scores, resulting in quadratic time.
Verified Code Solutions
/**
* @param {number} n - The number of performance entries.
* @param {number[][]} pairs - An array of pairs [segmentId, score].
* @return {number[][]} - An array of merged segments [[segmentId, totalScore], ...] sorted by segmentId.
*/
function mergeSegments(n, pairs) {
const segmentScores = new Map();
for (const [segmentId, score] of pairs) {
segmentScores.set(segmentId, (segmentScores.get(segmentId) || 0) + score);
}
const result = [];
for (const [segmentId, totalScore] of segmentScores.entries()) {
result.push([segmentId, totalScore]);
}
result.sort((a, b) => a[0] - b[0]);
return result;
}
// Driver code for local testing
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
rl.question('Enter n: ', (nStr) => {
const n = parseInt(nStr);
let pairs = [];
let count = 0;
const readPair = () => {
if (count === n) {
const result = mergeSegments(n, pairs);
console.log(JSON.stringify(result));
rl.close();
return;
}
rl.question(`Enter pair ${count + 1} (id score): `, (line) => {
const [id, score] = line.split(' ').map(Number);
pairs.push([id, score]);
count++;
readPair();
});
};
readPair();
});#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
vector<pair<int, int>> mergeSegments(int n, vector<pair<int, int>>& pairs) {
map<int, int> segmentScores;
for (const auto& p : pairs) {
int segmentId = p.first;
int score = p.second;
segmentScores[segmentId] += score;
}
vector<pair<int, int>> result;
for (const auto& entry : segmentScores) {
result.push_back({entry.first, entry.second});
}
return result;
}
int main() {
int n;
cin >> n;
vector<pair<int, int>> pairs(n);
for (int i = 0; i < n; i++) {
cin >> pairs[i].first >> pairs[i].second;
}
vector<pair<int, int>> result = mergeSegments(n, pairs);
for (const auto& p : result) {
cout << p.first << " " << p.second << endl;
}
return 0;
}import java.util.*;
public class Main {
/**
* Merges segments of student performance.
*
* @param n The number of performance entries.
* @param pairs A 2D array of pairs {segmentId, score}.
* @return A 2D array of merged segments {{segmentId, totalScore}, ...} sorted by segmentId.
*/
public static int[][] mergeSegments(int n, int[][] pairs) {
Map<Integer, Integer> segmentScores = new TreeMap<>();
for (int[] pair : pairs) {
int segmentId = pair[0];
int score = pair[1];
segmentScores.put(segmentId, segmentScores.getOrDefault(segmentId, 0) + score);
}
int[][] result = new int[segmentScores.size()][2];
int index = 0;
for (Map.Entry<Integer, Integer> entry : segmentScores.entrySet()) {
result[index][0] = entry.getKey();
result[index][1] = entry.getValue();
index++;
}
return result;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[][] pairs = new int[n][2];
for (int i = 0; i < n; i++) {
pairs[i][0] = scanner.nextInt();
pairs[i][1] = scanner.nextInt();
}
int[][] result = mergeSegments(n, pairs);
for (int[] pair : result) {
System.out.println(pair[0] + " " + pair[1]);
}
scanner.close();
}
}def merge_segments(n, pairs):
"""
Merges segments of student performance.
Args:
n (int): The number of performance entries.
pairs (list of list of int): A list of pairs [segmentId, score].
Returns:
list of list of int: A list of merged segments [[segmentId, totalScore], ...] sorted by segmentId.
"""
segment_scores = {}
for segment_id, score in pairs:
if segment_id in segment_scores:
segment_scores[segment_id] += score
else:
segment_scores[segment_id] = score
result = []
for segment_id in sorted(segment_scores.keys()):
result.append([segment_id, segment_scores[segment_id]])
return result
if __name__ == "__main__":
import sys
input = sys.stdin.read
data = input().split()
if not data:
sys.exit(0)
n = int(data[0])
pairs = []
index = 1
for _ in range(n):
segment_id = int(data[index])
score = int(data[index + 1])
pairs.append([segment_id, score])
index += 2
result = merge_segments(n, pairs)
for seg in result:
print(f"{seg[0]} {seg[1]}")/**
* @param {number} n - The number of performance entries.
* @param {number[][]} pairs - An array of pairs [segmentId, score].
* @return {number[][]} - An array of merged segments [[segmentId, totalScore], ...] sorted by segmentId.
*/
function mergeSegments(n, pairs) {
const segmentScores = new Map();
for (const [segmentId, score] of pairs) {
segmentScores.set(segmentId, (segmentScores.get(segmentId) || 0) + score);
}
const result = [];
for (const [segmentId, totalScore] of segmentScores.entries()) {
result.push([segmentId, totalScore]);
}
result.sort((a, b) => a[0] - b[0]);
return result;
}
// Driver code for local testing
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
rl.question('Enter n: ', (nStr) => {
const n = parseInt(nStr);
let pairs = [];
let count = 0;
const readPair = () => {
if (count === n) {
const result = mergeSegments(n, pairs);
console.log(JSON.stringify(result));
rl.close();
return;
}
rl.question(`Enter pair ${count + 1} (id score): `, (line) => {
const [id, score] = line.split(' ').map(Number);
pairs.push([id, score]);
count++;
readPair();
});
};
readPair();
});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.