Min Rewards

Tags

Min Rewards

Category

Arrays

Difficulty

Hard

Problem Statement

Imagine a row of students standing in a line, each with a unique score. You need to give rewards (positive integers) to each student such that:

  1. Every student receives at least 1 reward.
  2. Any student with a higher score than an adjacent student must receive more rewards than that neighbor.

Return the minimum total number of rewards you must give.

Intuition

The constraints are local: each student only needs to compare with immediate neighbors. If we process the array in two passes — one left-to-right and one right-to-left — we can satisfy both neighbor constraints independently and then take the maximum at each position. The left-to-right pass ensures that each student with a higher score than their left neighbor gets more rewards. The right-to-left pass ensures the same for the right neighbor. Taking the max of both passes satisfies both constraints simultaneously.

Approach

  1. Initialize a rewards array of length n, all set to 1.
  2. Left-to-right pass: For i from 1 to n-1, if scores[i] > scores[i-1], set rewards[i] = rewards[i-1] + 1.
  3. Right-to-left pass: For i from n-2 down to 0, if scores[i] > scores[i+1], set rewards[i] = max(rewards[i], rewards[i+1] + 1).
  4. Return the sum of the rewards array.

Pseudocode

function minRewards(scores):
    rewards = array of length(scores) filled with 1

    // Left to right pass
    for i from 1 to length(scores) - 1:
        if scores[i] > scores[i - 1]:
            rewards[i] = rewards[i - 1] + 1

    // Right to left pass
    for i from length(scores) - 2 down to 0:
        if scores[i] > scores[i + 1]:
            rewards[i] = max(rewards[i], rewards[i + 1] + 1)

    return sum(rewards)

Time & Space Complexity

  • Time: O(n) — Two linear passes through the array plus a final summation.
  • Space: O(n) — For the rewards array.

Key Insights

  • The two-pass technique is a common pattern for problems with bidirectional local constraints (also seen in "candy distribution" problems).
  • Using max in the second pass is essential: we must not reduce a reward that was already set higher by the first pass.
  • An alternative approach uses local minima (valleys) and expands outward from each valley, but the two-pass method is simpler to implement.

Edge Cases

  • Single student: the answer is 1.
  • Strictly increasing scores: rewards are [1, 2, 3, ..., n], totaling n*(n+1)/2.
  • Strictly decreasing scores: same total as strictly increasing.
  • All same scores: not applicable since the problem states scores are unique.
  • V-shaped scores (decreasing then increasing): the valley gets 1 reward, and both sides increase outward.

Linked mentions