1e:I[344796,["/_next/static/chunks/0whdtqcc5h8md.js","/_next/static/chunks/1qo17jq3o72yb.js","/_next/static/chunks/00mfjk9z2ewie.js","/_next/static/chunks/3_0kqrj9zuodm.js","/_next/static/chunks/2q9x6spyz4qxv.js","/_next/static/chunks/2cxhk-z7t3ztw.js","/_next/static/chunks/35kg0tmkl08ow.js","/_next/static/chunks/09hukzrse-ioj.js","/_next/static/chunks/3-qfh2-yexhl7.js","/_next/static/chunks/0_-iwh06bu1or.js"],"default"] 1f:T486,#include #include using namespace std; class Solution { public: int candy(vector& ratings) { int n = ratings.size(); if (n == 0) return 0; int ret = 1; int up = 0; int down = 0; int peak = 0; for (int i = 1; i < n; ++i) { if (ratings[i] > ratings[i - 1]) { up++; peak = up + 1; down = 0; ret += peak; } else if (ratings[i] == ratings[i - 1]) { up = 0; down = 0; peak = 0; ret += 1; } else { down++; up = 0; ret += down; if (down >= peak) { ret += 1; } } } return ret; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; if (cin >> n) { vector ratings(n); for (int i = 0; i < n; ++i) { cin >> ratings[i]; } Solution sol; cout << sol.candy(ratings) << "\n"; } return 0; }20:T67e,import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String line = br.readLine(); if (line == null) return; StringTokenizer st = new StringTokenizer(line); if (!st.hasMoreTokens()) return; int n = Integer.parseInt(st.nextToken()); int[] ratings = new int[n]; for (int i = 0; i < n; i++) { while (!st.hasMoreTokens()) { line = br.readLine(); if (line == null) break; st = new StringTokenizer(line); } if (st.hasMoreTokens()) { ratings[i] = Integer.parseInt(st.nextToken()); } } if (n == 0) { System.out.println(0); return; } int ret = 1; int up = 0; int down = 0; int peak = 0; for (int i = 1; i < n; i++) { if (ratings[i] > ratings[i - 1]) { up++; peak = up + 1; down = 0; ret += peak; } else if (ratings[i] == ratings[i - 1]) { up = 0; down = 0; peak = 0; ret += 1; } else { down++; up = 0; ret += down; if (down >= peak) { ret += 1; } } } System.out.println(ret); } }21:T59d,# Candy ## Problem 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. ## Input - An integer `n` representing the number of children. - An integer array `ratings` of length `n` containing each child's rating. ## Output - Return the minimum number of candies needed. ## Examples #### Example 1 Input: `n = 3, ratings = [1, 0, 2]` Output: `5` Explanation: You can allocate 2, 1, 2 candies respectively. #### Example 2 Input: `n = 3, ratings = [1, 2, 2]` Output: `4` Explanation: You can allocate 1, 2, 1 candies respectively. The third child gets 1 candy because it is not required to give more than the neighbor with equal rating. #### Example 3 Input: `n = 1, ratings = [10]` Output: `1` #### Example 4 Input: `n = 5, ratings = [1, 3, 5, 7, 9]` Output: `15` #### Example 5 Input: `n = 5, ratings = [9, 7, 5, 3, 1]` Output: `15` ## Constraints - No explicit constraints were provided in the problem statement. Typical LeetCode constraints: `1 <= n <= 2 * 10^5`, `-10^4 <= ratings[i] <= 10^4`. ## Notes - The problem is known as LeetCode 135 – Candy.22:T3be3,# Candy Editorial ## Solution 1: Iterative Neighbor Adjustment ### Intuition The simplest way to satisfy the rules is to start by giving every child the minimum of one candy. We then look at every child and their neighbors to see if any rules are broken. If a child has a higher rating than a neighbor but does not have more candies, we increase their candy count to fix the mistake. Since fixing one child might break the rule for another neighbor, we repeat this process until the candy distribution stops changing. This approach eventually settles on the minimum valid distribution because we only increase candies when absolutely necessary. ### Approach - Create a list to store candies for each child and initialize every value to one. - Use a flag to track if any updates were made during a full pass of the array. - In each pass, loop through the array and compare each child with their left and right neighbors. - Update the current child's candy count if they have a higher rating but fewer or equal candies than a neighbor. - Repeat the passes until a full scan results in no further updates to the candy counts. - Sum all the values in the candy list to get the final result. ### Pseudocode ```pseudocode candy(ratings) { n = ratings.size candies = array of size n filled with 1 hasChanged = true while hasChanged == true { hasChanged = false for i = 0 to n - 1 { if i > 0 and ratings[i] > ratings[i-1] and candies[i] <= candies[i-1] { candies[i] = candies[i-1] + 1 hasChanged = true } if i < n - 1 and ratings[i] > ratings[i+1] and candies[i] <= candies[i+1] { candies[i] = candies[i+1] + 1 hasChanged = true } } } totalCandies = 0 for i = 0 to n - 1 { totalCandies = totalCandies + candies[i] } return totalCandies } ``` ### Code Implementation #### C++ ```cpp #include using namespace std; class solution { public: int candy(vector& ratings) { int n = ratings.size(); if (n == 0) return 0; vector candies(n, 1); bool hasChanged = true; while (hasChanged) { hasChanged = false; for (int i = 0; i < n; i++) { if (i > 0 && ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1]) { candies[i] = candies[i - 1] + 1; hasChanged = true; } if (i < n - 1 && ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) { candies[i] = candies[i + 1] + 1; hasChanged = true; } } } int totalCandies = 0; for (int c : candies) { totalCandies += c; } return totalCandies; } }; ``` #### Python ```python class solution: def candy(self, ratings: list[int]) -> int: n = len(ratings) if n == 0: return 0 candies = [1] * n has_changed = True while has_changed: has_changed = False for i in range(n): if i > 0 and ratings[i] > ratings[i-1] and candies[i] <= candies[i-1]: candies[i] = candies[i-1] + 1 has_changed = True if i < n - 1 and ratings[i] > ratings[i+1] and candies[i] <= candies[i+1]: candies[i] = candies[i+1] + 1 has_changed = True return sum(candies) ``` #### Java ```java import java.util.*; class Solution { public int candy(int[] ratings) { int n = ratings.length; if (n == 0) return 0; int[] candies = new int[n]; Arrays.fill(candies, 1); boolean hasChanged = true; while (hasChanged) { hasChanged = false; for (int i = 0; i < n; i++) { if (i > 0 && ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1]) { candies[i] = candies[i - 1] + 1; hasChanged = true; } if (i < n - 1 && ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) { candies[i] = candies[i + 1] + 1; hasChanged = true; } } } int totalCandies = 0; for (int c : candies) { totalCandies += c; } return totalCandies; } } ``` #### JavaScript ```javascript class Solution { static candy(ratings) { const n = ratings.length; if (n === 0) return 0; const candies = new Array(n).fill(1); let hasChanged = true; while (hasChanged) { hasChanged = false; for (let i = 0; i < n; i++) { if (i > 0 && ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1]) { candies[i] = candies[i - 1] + 1; hasChanged = true; } if (i < n - 1 && ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) { candies[i] = candies[i + 1] + 1; hasChanged = true; } } } return candies.reduce((a, b) => a + b, 0); } } ``` ### Complexity Analysis - **Time Complexity:** `O(n^2)` – Each pass takes `O(n)` and in the worst case (e.g., strictly decreasing sequence) we may need`O(n)` passes. - **Space Complexity:** `O(n)` – We use an auxiliary array of size `n`. ## Solution 2: Two-Pass Greedy Array ### Intuition The problem asks us to satisfy two conditions: a child must have more candies than their left neighbor if their rating is higher, and similarly for their right neighbor. We can handle these two conditions independently. First, scan from left to right to ensure every child has more candies than their left neighbor when appropriate. Then, scan from right to left to ensure the same for the right neighbor. By taking the maximum candy count required by either direction at each index, we satisfy both conditions while using the minimum number of candies. ### Approach - Initialize an array with 1 candy for each child. - Perform a left-to-right pass: if the current child has a higher rating than the one before it, set its candy count to the previous child's count plus one. - Perform a right-to-left pass: if the current child has a higher rating than the one after it, update its candy count to be the maximum of its current count and the next child's count plus one. - Sum up all the values in the candy array for the final answer. ### Pseudocode ```pseudocode candy(ratings) { n = ratings.size if n == 0 return 0 candies = array of size n filled with 1 for i = 1 to n - 1 { if ratings[i] > ratings[i-1] { candies[i] = candies[i-1] + 1 } } for i = n - 2 down to 0 { if ratings[i] > ratings[i+1] { candies[i] = max(candies[i], candies[i+1] + 1) } } total = 0 for val in candies { total = total + val } return total } ``` ### Code Implementation #### C++ ```cpp #include using namespace std; class solution { public: int candy(vector& ratings) { int n = ratings.size(); if (n <= 1) return n; vector candies(n, 1); for (int i = 1; i < n; i++) { if (ratings[i] > ratings[i - 1]) { candies[i] = candies[i - 1] + 1; } } for (int i = n - 2; i >= 0; i--) { if (ratings[i] > ratings[i + 1]) { candies[i] = max(candies[i], candies[i + 1] + 1); } } int total = 0; for (int c : candies) total += c; return total; } }; ``` #### Python ```python class solution: def candy(self, ratings: list[int]) -> int: n = len(ratings) if n <= 1: return n candies = [1] * n for i in range(1, n): if ratings[i] > ratings[i - 1]: candies[i] = candies[i - 1] + 1 for i in range(n - 2, -1, -1): if ratings[i] > ratings[i + 1]: candies[i] = max(candies[i], candies[i + 1] + 1) return sum(candies) ``` #### Java ```java import java.util.*; class Solution { public int candy(int[] ratings) { int n = ratings.length; if (n <= 1) return n; int[] candies = new int[n]; Arrays.fill(candies, 1); for (int i = 1; i < n; i++) { if (ratings[i] > ratings[i - 1]) { candies[i] = candies[i - 1] + 1; } } int total = 0; for (int i = n - 2; i >= 0; i--) { if (ratings[i] > ratings[i + 1]) { candies[i] = Math.max(candies[i], candies[i + 1] + 1); } } for (int c : candies) total += c; return total; } } ``` #### JavaScript ```javascript class Solution { static candy(ratings) { const n = ratings.length; if (n <= 1) return n; const candies = new Array(n).fill(1); for (let i = 1; i < n; i++) { if (ratings[i] > ratings[i - 1]) { candies[i] = candies[i - 1] + 1; } } for (let i = n - 2; i >= 0; i--) { if (ratings[i] > ratings[i + 1]) { candies[i] = Math.max(candies[i], candies[i + 1] + 1); } } return candies.reduce((a, b) => a + b, 0); } } ``` ### Complexity Analysis - **Time Complexity:** `O(n)` – Two linear passes and one sum. - **Space Complexity:** `O(n)` – Auxiliary array of size `n`. ## Solution 3: Single Pass Slope Tracking ### Intuition Instead of using extra space, we can observe that the candy distribution follows the "slopes" of the ratings. An increasing sequence of ratings (an "up" slope) means each child gets one more candy than the last. A decreasing sequence (a "down" slope) means each child in that sequence needs one more candy than the child following them. The "peak" of these slopes is special; it must be high enough to satisfy both the "up" sequence before it and the "down" sequence after it. By tracking the lengths of these slopes, we can calculate the total candies on the fly without storing individual counts. ### Approach - Initialize the total candy count to 1 (for the first child). - Maintain three counters: `up` (length of the current rising slope), `down` (length of the current falling slope), and `peak` (the height of the last rising slope). - Iterate through the ratings starting from the second child: - If the rating is increasing: Reset `down` to 0, increment `up`, update `peak` to `up + 1`, and add `peak` to the total candies. - If the rating is equal: Reset `up`, `down`, and `peak` to 0, and add 1 candy for the current child. - If the rating is decreasing: Reset `up` to 0, increment `down`, and add `down` candies. If the `down` slope length meets or exceeds the `peak` height, add an additional 1 candy to adjust the peak's height. - Return the final accumulated total. ### Pseudocode ```pseudocode candy(ratings) { n = ratings.size if n == 0 return 0 total = 1 up = 0 down = 0 peak = 0 for i = 1 to n - 1 { if ratings[i] > ratings[i-1] { up = up + 1 peak = up + 1 down = 0 total = total + peak } else if ratings[i] == ratings[i-1] { up = 0 down = 0 peak = 0 total = total + 1 } else { down = down + 1 up = 0 total = total + down if down >= peak { total = total + 1 } } } return total } ``` ### Code Implementation #### C++ ```cpp #include using namespace std; class solution { public: int candy(vector& ratings) { int n = ratings.size(); if (n == 0) return 0; int total = 1; int up = 0; int down = 0; int peak = 0; for (int i = 1; i < n; ++i) { if (ratings[i] > ratings[i - 1]) { up++; peak = up + 1; down = 0; total += peak; } else if (ratings[i] == ratings[i - 1]) { up = 0; down = 0; peak = 0; total += 1; } else { down++; up = 0; total += down; if (down >= peak) { total += 1; } } } return total; } }; ``` #### Python ```python class solution: def candy(self, ratings: list[int]) -> int: n = len(ratings) if n == 0: return 0 total = 1 up = 0 down = 0 peak = 0 for i in range(1, n): if ratings[i] > ratings[i-1]: up += 1 peak = up + 1 down = 0 total += peak elif ratings[i] == ratings[i-1]: up = 0 down = 0 peak = 0 total += 1 else: down += 1 up = 0 total += down if down >= peak: total += 1 return total ``` #### Java ```java import java.util.*; class Solution { public int candy(int[] ratings) { int n = ratings.length; if (n == 0) return 0; int total = 1; int up = 0; int down = 0; int peak = 0; for (int i = 1; i < n; i++) { if (ratings[i] > ratings[i - 1]) { up++; peak = up + 1; down = 0; total += peak; } else if (ratings[i] == ratings[i - 1]) { up = 0; down = 0; peak = 0; total += 1; } else { down++; up = 0; total += down; if (down >= peak) { total += 1; } } } return total; } } ``` #### JavaScript ```javascript class Solution { static candy(ratings) { const n = ratings.length; if (n === 0) return 0; let total = 1; let up = 0; let down = 0; let peak = 0; for (let i = 1; i < n; i++) { if (ratings[i] > ratings[i - 1]) { up++; peak = up + 1; down = 0; total += peak; } else if (ratings[i] === ratings[i - 1]) { up = 0; down = 0; peak = 0; total += 1; } else { down++; up = 0; total += down; if (down >= peak) { total += 1; } } } return total; } } ``` ### Complexity Analysis - **Time Complexity:** `O(n)` – Single pass through the array. - **Space Complexity:** `O(1)` – Only a few integer variables used.16:[["$","script",null,{"type":"application/ld+json","dangerouslySetInnerHTML":{"__html":"{\"@context\":\"https://schema.org\",\"@type\":\"LearningResource\",\"learningResourceType\":\"Coding Question\",\"name\":\"Candy\",\"description\":\"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.\",\"educationalLevel\":\"medium\",\"about\":{\"@type\":\"Organization\",\"name\":\"NextHopp_2ndaug\"},\"provider\":{\"@type\":\"Organization\",\"name\":\"OAHelper\",\"url\":\"https://www.oahelper.in\"},\"isPartOf\":{\"@type\":\"WebSite\",\"name\":\"OAHelper\",\"url\":\"https://www.oahelper.in\"},\"url\":\"https://www.oahelper.in/problems/MzYxNnww/candy\"}"}}],["$","script",null,{"type":"application/ld+json","dangerouslySetInnerHTML":{"__html":"{\"@context\":\"https://schema.org\",\"@type\":\"BreadcrumbList\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https://www.oahelper.in/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Problems\",\"item\":\"https://www.oahelper.in/problems\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"Candy\",\"item\":\"https://www.oahelper.in/problems/MzYxNnww/candy\"}]}"}}],["$","$L1e",null,{"fallback":["$","section",null,{"className":"mx-auto max-w-5xl px-6 py-24 text-white","children":[["$","h1",null,{"className":"mb-5 text-3xl font-bold","children":"Candy"}],["$","p",null,{"children":["Company: ","NextHopp_2ndaug"]}],["$","p",null,{"children":["Difficulty: ","medium"]}],false,["$","div",null,{"children":[["$","h2",null,{"children":"Problem Statement"}],["$","p",null,{"children":"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."}]]}],false,["$","nav",null,{"aria-label":"Related company pages","children":[["$","$L9",null,{"href":"/company-questions/nexthopp2ndaug","children":["More ","NextHopp_2ndaug"," OA questions"]}],["$","$L9",null,{"href":"/interview-experiences","children":"Interview experiences"}]]}]]}],"id":"MzYxNnww","initialQuestion":{"id":"MzYxNnww","title":"Candy","google_doc_link":null,"problem_statement":"

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_cpp":"$1f","solution_python":"import sys\n\ndef main():\n input_data = sys.stdin.read().split()\n if not input_data:\n return\n n = int(input_data[0])\n if n == 0:\n print(0)\n return\n ratings = [int(x) for x in input_data[1:n+1]]\n ret = 1\n up = 0\n down = 0\n peak = 0\n for i in range(1, n):\n if ratings[i] > ratings[i-1]:\n up += 1\n peak = up + 1\n down = 0\n ret += peak\n elif ratings[i] == ratings[i-1]:\n up = 0\n down = 0\n peak = 0\n ret += 1\n else:\n down += 1\n up = 0\n ret += down\n if down >= peak:\n ret += 1\n print(ret)\n\nif __name__ == '__main__':\n main()","solution_java":"$20","pregiven_code_cpp":"#include \n#include \n\nusing namespace std;\n\nclass Solution {\npublic:\n int candy(vector& ratings) {\n return 0;\n }\n};\n\nint main() {\n ios_base::sync_with_stdio(false);\n cin.tie(NULL);\n int n;\n if (cin >> n) {\n vector ratings(n);\n for (int i = 0; i < n; ++i) {\n cin >> ratings[i];\n }\n Solution sol;\n cout << sol.candy(ratings) << \"\\n\";\n }\n return 0;\n}","pregiven_code_python":"import sys\n\nclass Solution:\n def candy(self, ratings: list[int]) -> int:\n return 0\n\nif __name__ == \"__main__\":\n input_data = sys.stdin.read().split()\n if input_data:\n n = int(input_data[0])\n ratings = [int(x) for x in input_data[1:n+1]]\n sol = Solution()\n print(sol.candy(ratings))","pregiven_code_java":"import java.util.*;\n\nclass Solution {\n public int candy(int[] ratings) {\n return 0;\n }\n}\n\npublic class Main {\n public static void main(String[] args) {\n Scanner scanner = new Scanner(System.in);\n if (scanner.hasNextInt()) {\n int n = scanner.nextInt();\n int[] ratings = new int[n];\n for (int i = 0; i < n; i++) {\n if (scanner.hasNextInt()) {\n ratings[i] = scanner.nextInt();\n }\n }\n Solution sol = new Solution();\n System.out.println(sol.candy(ratings));\n }\n }\n}","difficulty":"medium","question_type":"coding","premium_required":0,"created_at":"2026-03-08T06:55:08.253334+00:00","updated_at":"2026-08-09T23:09:12.891003+00:00","solution_code":null,"solution":null,"pregiven_code":null,"input_test_case":"[\"3\\n1 0 2\", \"3\\n1 2 2\"]","output_test_case":"[\"5\", \"4\"]","lc_tags":"[\"Array\", \"Greedy\", \"Dynamic Programming\"]","visual_animation":null,"difficulty_score":70,"md_problem_statement":"$21","unique_company_name":"nexthopp","sql_solution":null,"bash_solution":null,"js_solution":null,"editorial":"$22","hidden_test_cases_blob_count":null,"youtube_tutorial":null,"prompt_solution":null,"campus_type":null,"college_name":null,"role":null,"hidden_test_cases_ref":null,"is_mock_oa":false,"publication_status":"published","has_image":true,"company_name":"NextHopp_2ndaug","is_first_in_company":true,"company_ref":"MTMwMHww","total_test_cases":15,"hidden_test_cases_count":13},"isQotdToday":false,"qotdReward":5}]]