Candy
Intermediate Greedy Techniques DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Binary Search: How does it work and what are its main implementation approaches?, Greedy Algorithm, Arrays, Loops, Time Complexity, Space Complexity, iterative algorithms, space complexity, array, divide and conquer, binary search, recursion, time complexity analysis.
Candy Problem Statement There are n children standing in a line. Each child has a rating value. You are giving candies to these children subjected to the following requirements: 1. Each child must have at least one candy. 2. Children with a higher rating get more candies than their immediate neighbors. Return the minimum number of candies you need to have to distribute. Input Specification The first line contains an integer n (1 <= n <= 2 10^4), representing the number of children. The second line contains n integers ratings 1, ratings 2, ..., ratings n (0 <= ratings i <= 2 10^4), where ratings i is the rating of the i th child. Output Specification Print a single integer, the minimum total number of candies required. Constraints 1 <= n <= 2 10^4 0 <= ratings[i] <= 2 10^4 Sample Test Cases Sample Input 1: Sample Output 1: Explanation 1: You can allocate candies [2, 1, 2]. Child 0 (rating 1) gets 2 candies. Child 1 (rating 0) gets 1 candy (less than neighbor 0). Child 2 (rating 2) gets 2 candies (more than neighbor 1). Total = 2 + 1 + 2 = 5. Sample Input 2: Sample Output 2: Explanation 2: You can allocate candies [1, 2, 2, 1, 2]. Child 0 (rating 1) gets 1 candy. Child 1 (rating 2) gets 2 candies (more than neighbor 0, and not less than neighbor 2). Child 2 (rating 2) gets 2 candies (more than neighbor 3, and not less than neighbor 1). Child 3 (rating 1) gets 1 candy (less than neighbor 2, and less than neighbor 4). Child 4 (rating 3) gets 2 candies (more than neighbor 3). Total = 1 + 2 + 2 + 1 + 2 = 8. Difficulty Level: Medium