Hand Out Prizes So Higher Scorers Beat Their Neighbours
Solve this ProblemA line of players each has a score. Prizes are handed out under two rules: everyone gets at least one prize, and a player who scores strictly higher than a neighbour standing directly next to them must get strictly more prizes than that neighbour. Find the fewest prizes that can be handed out.
Repeatedly repairing violations until none remain works but can ripple along a long descending run one step at a time. Splitting the rule into a left-neighbour half and a right-neighbour half, and satisfying each half in its own pass, gets the answer in two sweeps.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ scores.length ≤ 15 and 0 ≤ scores[i] ≤ 9; the players stand in a line in the given order - ◆
Every player must receive at least 1 prize - ◆
If a player has a strictly higher score than a player standing directly next to them (left or right), they must receive strictly more prizes than that neighbour. Neighbours with equal scores have no such requirement - ◆
Return the smallest total number of prizes that satisfies every rule
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Keep Fixing Rule Violations Until Nothing Changes
BruteStart by giving everyone 1 prize. Then sweep the line repeatedly: whenever a player has a higher score than a neighbour but does not have more prizes than that neighbour, raise their prize count to one more than the neighbour's. Fixing one player can break the rule for someone next to them, so keep sweeping until a full sweep changes nothing. The result satisfies every rule and every increase was forced, so it is the minimum. A long descending run needs a full sweep for each step of the correction, which is what makes this quadratic.
O(n²)O(n)1class Solution {
2 public int minPrizes(int[] scores) {
3 int n = scores.length;
4 int[] prizes = new int[n];
5 Arrays.fill(prizes, 1);
6 boolean changed = true;
7 while (changed) {
8 changed = false;
9 for (int i = 0; i < n; i++) {
10 if (i > 0 && scores[i] > scores[i - 1] && prizes[i] <= prizes[i - 1]) {
11 prizes[i] = prizes[i - 1] + 1;
12 changed = true;
13 }
14 if (i < n - 1 && scores[i] > scores[i + 1] && prizes[i] <= prizes[i + 1]) {
15 prizes[i] = prizes[i + 1] + 1;
16 changed = true;
17 }
18 }
19 }
20 int total = 0;
21 for (int prize : prizes) total += prize;
22 return total;
23 }
24}Optimal — Two Passes: Satisfy the Left Rule, Then the Right
OptimalSplit the rule into its two halves and satisfy each in one pass. Left to right: if a player scores higher than the player on their left, they get one more prize than that neighbour (this handles every rising stretch). Right to left: if a player scores higher than the player on their right, they must have at least one more prize than that neighbour — so take the larger of what they already have and that value, which keeps the left-pass result intact. Adding up the prizes during the second pass gives the total. Each pass moves in the one direction that lets it build on values already final.
O(n)O(n)1class Solution {
2 public int minPrizes(int[] scores) {
3 int n = scores.length;
4 int[] prizes = new int[n];
5 Arrays.fill(prizes, 1);
6 for (int i = 1; i < n; i++) {
7 if (scores[i] > scores[i - 1]) prizes[i] = prizes[i - 1] + 1;
8 }
9 int total = prizes[n - 1];
10 for (int i = n - 2; i >= 0; i--) {
11 if (scores[i] > scores[i + 1]) prizes[i] = Math.max(prizes[i], prizes[i + 1] + 1);
12 total += prizes[i];
13 }
14 return total;
15 }
16}