Candy

Array Greedy

48.0% acceptance

Jan 12, 2026

9277

843

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings. You are giving candies to these children subjected to the following requirements: Each child must have at least one candy. Children with a higher rating get more candies than their neighbors. Return the minimum number of candies you need to have to distribute the candies to the children.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn candy(ratings: Vec<i32>) -> i32 {
    let n = ratings.len();
    if n == 0 {
      return 0;
    }
    
    let mut candies = vec![1; n];
    
    // Left to right pass
    for i in 1..n {
      if ratings[i] > ratings[i - 1] {
        candies[i] = candies[i - 1] + 1;
      }
    }
    
    // Right to left pass
    for i in (0..n - 1).rev() {
      if ratings[i] > ratings[i + 1] {
        candies[i] = candies[i].max(candies[i + 1] + 1);
      }
    }
    
    candies.iter().sum()
  }
}