You are given an array scores, where scores[i] is the score of the i-th robot.
Robots repeatedly compete using the following rules:
-
Select the two robots with the highest current scores,
x
and
y
, where
x >= y
.
-
These two robots compete.
-
If
x == y
, both robots are removed.
-
If
x > y
, the robot with score
y
is removed, and the robot with score
x
remains with a new score of
x - y
.
-
Repeat until at most one robot remains.
Return the score of the final remaining robot. If no robots remain, return 0.
Design and implement an efficient algorithm. Analyze its time and space complexity.
Example:
Input: scores = [2, 7, 4, 1, 8, 1]
Output: 1
Explanation:
8 and 7 compete -> remaining score 1, scores become [2, 4, 1, 1, 1]
4 and 2 compete -> remaining score 2, scores become [2, 1, 1, 1]
2 and 1 compete -> remaining score 1, scores become [1, 1, 1]
1 and 1 compete -> both removed, scores become [1]
Final score is 1