Reorder the Level Score Changes
Context
During a game level, a player records score changes in one mutable list. Negative values are penalties, while zero and positive values are gains or neutral events. Reorganize the list in place so every penalty appears before every nonnegative change.
Problem
Write a function that rearranges the given score-change list in place. Every negative value must appear before every value that is zero or positive. The relative order inside either group does not matter, so any valid partition is accepted. Keep every original value with exactly the same multiplicity, including repeated values, and return the rearranged list. Use linear time and constant auxiliary space. An empty list is valid and should be returned unchanged.
Examples
score_changes = [5, -2, 0, -7, 3, -1][-2, -7, -1, 5, 3, 0]score_changes = [0, -4, -4, 2, 0, -1, 2][-4, -4, -1, 2, 0, 0, 2]score_changes = [-9, -3, -1, 4, 8][-9, -3, -1, 4, 8]Constraints
0 <= len(score_changes) <= 100000-1000000 <= score_changes[i] <= 1000000 for every i- Types:
score_changesis int[]; result is int[]
Function signature
def partition_score_changes(score_changes: list[int]) -> list[int]
score_changeslist[int]- The mutable list of integer score changes recorded during the level.
- returns list[int]
- The same list after in-place rearrangement, with all negative values before all nonnegative values.
Adapted from MBPP problem task_229 (CC BY 4.0). Rewritten, extended and verified by Iksha.
Notes
- The arrangement within the negative group and within the nonnegative group may be arbitrary.
- The input list must be modified in place and its values must not be added or removed.