PracticeArrays

Arena Score Median

Easy/MediumArraystraversalstate trackingcomparison Time not estimated Not started

Context

Two rival players have completed the same number of runs in a score-based game. Each player's scores are already sorted from lowest to highest. The arena wants one typical score for the combined results, using the median of all scores while avoiding unnecessary storage for a merged sequence.

Problem

Given two equally sized sorted score sequences, determine the median of all scores when the sequences are considered together as one multiset. Repeated scores must remain repeated. Traverse the two sequences from left to right by repeatedly selecting the smaller available score. Keep only the previously selected score and the latest selected score, and stop once the central positions have been reached. If the combined count is odd, return the central score. If it is even, return the arithmetic mean of the two central scores.

Examples

Example 1
Input: first_scores = [1, 4, 7]second_scores = [2, 5, 8]
Output: 4.5
Explanation: For the first example, the executed result is 4.5.
Example 2
Input: first_scores = [-3, 0, 4, 10]second_scores = [-1, 2, 4, 9]
Output: 3
Explanation: For the second example, the executed result is 3.0.
Example 3
Input: first_scores = [2, 2, 6, 12, 12]second_scores = [1, 2, 8, 12, 15]
Output: 7
Explanation: For the third example, the executed result is 7.0.

Constraints

  • 1 <= len(first_scores) <= 100000
  • -1000000 <= first_scores[i] <= 1000000 for every i
  • first_scores: non empty
  • first_scores: sorted non decreasing
  • len(first_scores) <= len(second_scores) <= len(first_scores)
  • -1000000 <= second_scores[i] <= 1000000 for every i
  • second_scores: non empty
  • second_scores: sorted non decreasing
  • Types: first_scores is int[], second_scores is int[]; result is float

Function signature

def arena_score_median(first_scores: list[int], second_scores: list[int]) -> float
first_scores list[int]
The first player's scores in non-decreasing order.
second_scores list[int]
The second player's scores in non-decreasing order, with the same length as first_scores.
returns float
The median score of the combined multiset, returned as a number; it may be fractional when the combined count is even.

Adapted from MBPP problem task_622 (CC BY 4.0). Rewritten, extended and verified by Iksha.

Notes

  • Both sequences have equal length, including the smallest valid case of one score each.
  • Duplicate, negative, and zero scores are valid values.
Approved · cb039r1-abs_22_v214 execution-verified tests
Code
Saved
Checking environment…Python SandboxLn 1, Col 1