Skip to content

Handing Out Bonuses

Jump to bottom
Andrew Burke edited this page Aug 19, 2026 · 1 revision

TIP103 Unit 12 Session 1 (Click for link to problem statements)

Handing Out Bonuses

Employees stand in a line with performance ratings ratings. Every employee gets at least one bonus unit, and anyone rated higher than an immediate neighbor must receive more units than that neighbor.

Return the minimum total number of bonus units needed.

def candy(ratings):
    pass

Problem Highlights

  • 💡 Difficulty: Hard
  • ⏰ Time to complete: 30-40 mins
  • 🛠️ Topics: Arrays, Greedy Algorithms, Two-Pass Technique

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • Q: What are the two rules every bonus assignment must satisfy?
    • A: Every employee receives at least 1 bonus unit, and any employee rated strictly higher than an immediate neighbor must receive strictly more units than that neighbor.
  • Q: If two adjacent employees have equal ratings, do they need equal bonuses?
    • A: No. The constraint only applies when one rating is strictly higher than a neighbor's, so an employee with an equal rating can drop back down to 1 unit.
  • Q: Does an employee's bonus depend on anyone other than their immediate neighbors?
    • A: No. Only the immediate left and right neighbors matter, which is what makes one pass in each direction sufficient.
HAPPY CASE
Input: ratings = [1, 0, 2]
Output: 5
Explanation: Give the employees 2, 1, and 2 bonus units respectively. The middle employee has the lowest rating and gets the minimum of 1; both neighbors outrank them and must get more, so each gets 2. Total = 2 + 1 + 2 = 5.

Input: ratings = [1, 2, 2]
Output: 4
Explanation: Give the employees 1, 2, and 1 bonus units respectively. The second employee outranks the first and needs more than 1. The third employee's rating equals the second's, so 1 unit suffices. Total = 1 + 2 + 1 = 4.

EDGE CASE
Input: ratings = [4, 3, 2, 1]
Output: 10
Explanation: Ratings strictly decrease, so bonuses must be 4, 3, 2, 1. A single left-to-right pass would miss this — the increases have to propagate backward from the right end. Total = 4 + 3 + 2 + 1 = 10.

Input: ratings = [7]
Output: 1
Explanation: A single employee has no neighbors and simply receives the minimum of 1 unit.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Local Constraint Optimization Problems, we can consider the following approaches:

  • Greedy (Two-Pass Technique): Because each employee's bonus is only constrained by immediate neighbors, we can satisfy all left-neighbor constraints in one forward pass and all right-neighbor constraints in one backward pass, taking the max of the two requirements.
  • Brute Force / Repeated Sweeps: Repeatedly scan the line and bump anyone who violates a constraint until nothing changes — correct, but far slower than the two-pass greedy.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Start everyone at 1 bonus unit. Sweep left to right: whenever an employee outrates their left neighbor, give them one more unit than that neighbor. Then sweep right to left: whenever an employee outrates their right neighbor, they need more than that neighbor too — take the max of what they already have and the right neighbor's bonus plus one, so the left-pass result is never broken. The sum of the final array is the minimum total.

1) Initialize a `bonuses` array of the same length as `ratings`, filled with 1.
2) Left-to-right pass: for each i from 1 to n-1:
   a) If ratings[i] > ratings[i-1], set bonuses[i] = bonuses[i-1] + 1.
3) Right-to-left pass: for each i from n-2 down to 0:
   a) If ratings[i] > ratings[i+1], set bonuses[i] = max(bonuses[i], bonuses[i+1] + 1).
4) Return the sum of `bonuses`.

⚠️ Common Mistakes

  • Overwriting instead of taking the max in the right-to-left pass, which breaks constraints already satisfied by the left-to-right pass.
  • Attempting a single pass, which fails on strictly decreasing runs like [4, 3, 2, 1] where increases must propagate backward.
  • Increasing the bonus when adjacent ratings are equal — equal ratings carry no constraint, and adding units inflates the total above the minimum.
  • Initializing the array to 0 and forgetting that every employee needs at least 1 unit.

4: I-mplement

Implement the code to solve the algorithm.

def candy(ratings):
    n = len(ratings)
    bonuses = [1] * n  # Everyone starts with the minimum of 1 unit

    # Left-to-right pass: satisfy constraints against the left neighbor
    for i in range(1, n):
        if ratings[i] > ratings[i - 1]:
            bonuses[i] = bonuses[i - 1] + 1

    # Right-to-left pass: satisfy constraints against the right neighbor
    # without breaking the left-pass results (hence the max)
    for i in range(n - 2, -1, -1):
        if ratings[i] > ratings[i + 1]:
            bonuses[i] = max(bonuses[i], bonuses[i + 1] + 1)

    return sum(bonuses)

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Input: ratings = [1, 0, 2]

    • Initialize: bonuses = [1, 1, 1]
    • Left-to-right: index 1 (0 < 1, no change); index 2 (2 > 0, bonuses[2] = 2) → bonuses = [1, 1, 2]
    • Right-to-left: index 1 (0 < 2, no change); index 0 (1 > 0, bonuses[0] = max(1, 1 + 1) = 2) → bonuses = [2, 1, 2]
    • Output: 2 + 1 + 2 = 5

  • Input: ratings = [1, 2, 2]

    • Initialize: bonuses = [1, 1, 1]
    • Left-to-right: index 1 (2 > 1, bonuses[1] = 2); index 2 (2 == 2, no change) → bonuses = [1, 2, 1]
    • Right-to-left: no rating is strictly greater than its right neighbor, so no changes
    • Output: 1 + 2 + 1 = 4

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of employees in the line.

  • Time Complexity: O(N) because we make two linear passes over the ratings plus one pass to sum the bonuses.
  • Space Complexity: O(N) for the bonuses array that tracks each employee's units.

Clone this wiki locally