Smallest Combined Token Scores
Context
A log analyzer compares token severity scores from two ordered archive batches. Each possible pairing produces a combined score. Return the first requested number of combined scores, from smallest to largest, while treating repeated scores from different pairings as separate results.
Problem
Given two lists of token scores already arranged from smallest to largest and a requested limit, produce the smallest available pairwise sums. A sum uses one score from the first list and one from the second list. Keep duplicate sums when they come from different index pairings, and return sums in nondecreasing order. If the limit is zero, either list is empty, or fewer pairings exist than requested, return only the sums that can be produced. Do not build the complete collection of pairings; maintain the smallest unseen candidate from each active row in a min-priority queue. After removing a candidate, replace it with the next candidate from that same row when available.
Examples
first_scores = [1, 4, 7]limit = 5second_scores = [2, 3, 8][3, 4, 6, 7, 9]first_scores = [1, 1, 3]limit = 6second_scores = [2, 2][3, 3, 3, 3, 5, 5]first_scores = [-5, 0, 4]limit = 4second_scores = [-2, 1, 1][-7, -4, -4, -2]Constraints
0 <= len(first_scores) <= 100-100000 <= first_scores[i] <= 100000 for every ifirst_scores: sorted non decreasing0 <= len(second_scores) <= 100-100000 <= second_scores[i] <= 100000 for every isecond_scores: sorted non decreasing0 <= limit <= 10000- Types:
first_scoresis int[],second_scoresis int[],limitis int; result is int[]
Function signature
def smallest_combined_scores(first_scores: list[int], second_scores: list[int], limit: int) -> list[int]
first_scoreslist[int]- Sorted token severity scores from the first archive batch.
second_scoreslist[int]- Sorted token severity scores from the second archive batch.
limitint- Maximum number of combined scores to return.
- returns list[int]
- The available pairwise sums in nondecreasing order, containing at most limit entries and preserving multiplicity.
Adapted from MBPP problem task_408 (CC BY 4.0). Rewritten, extended and verified by Iksha.
Notes
- The lists may contain negative values and repeated values.
- The requested limit can exceed the number of available pairings.