Minimum salary hike for employees based on ratings
Filed under Amazon
Free read 3 of 3Confirm that adjacent employees with equal ratings do not need the same or different hikes, only strictly higher-rated ones do.
The question
There are n employees standing in a line. Each employee is assigned a rating value. You are asked to give hikes to these employees following the rules: each employee must have at least one hike, and employees with a higher rating get a higher hike than their immediate neighbors. Return the minimum total hikes needed.
Constraints
- n == ratings.length
- 1 <= n <= 2 * 10^4
- 0 <= ratings[i] <= 2 * 10^4
Examples
- Input
- ratings = [1,0,2]
- Output
- 5
- Why
- You can allocate [2,1,2] hikes. The third employee has a higher rating than the second and gets more hikes.
Approach
Confirm that adjacent employees with equal ratings do not need the same or different hikes, only strictly higher-rated ones do.
Repeatedly adjust hikes until no violations occur, which can take O(N^2) time.
Use two passes: first pass from left to right to ensure right neighbor satisfies condition if rating is higher; second pass from right to left to ensure left neighbor condition, taking the maximum of both.
Single employee array or arrays with all identical ratings.
Solution
O(N) time, O(N) space
def candy(ratings: list[int]) -> int:
n = len(ratings)
hikes = [1] * n
for i in range(1, n):
if ratings[i] > ratings[i-1]:
hikes[i] = hikes[i-1] + 1
for i in range(n-2, -1, -1):
if ratings[i] > ratings[i+1]:
hikes[i] = max(hikes[i], hikes[i+1] + 1)
return sum(hikes)
Tips
- What they are testing: Test with strictly increasing, strictly decreasing, flat ratings, and alternating valleys/peaks.
- Common mistake: Iterating only in a single direction, which fails to account for constraints from both left and right neighbors simultaneously.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.