What is the time complexity of Candy?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Candy?

This problem uses Array, Greedy. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Candy?

Insight 1: The problem can be solved by making two passes through the ratings array: one from left to right and another from right to left. This ensures that both neighbors are considered when distributing candies. Insight 2: Each child's candy count depends on its immediate neighbors. We can initialize each child with one candy and then adjust the counts based on their neighbors' ratings during each pass.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Candy - LeetCode 135 Solution

Q: Which companies ask LeetCode 135. Candy in interviews?

This problem is frequently asked at Accenture, ConsultAdd, Flipkart, Goldman Sachs, Komprise and 7 more companies.

Candy - Complete Solution Guide

Candy is LeetCode problem 135, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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 . Example 1: Input: ratings = [1,0,2] Output: 5 Explanation: You can allocate to the first, seco

Detailed Explanation

The "Candy" problem requires us to distribute candies to a line of children, where each child has a rating. The distribution must satisfy two conditions: every child receives at least one candy, and children with higher ratings than their neighbors receive more candies than their neighbors. The goal is to minimize the total number of candies required.

Solution Approach

The solution uses a greedy approach, making local optimal choices to arrive at the global minimum. It involves initializing a `candies` array where each child initially receives one candy. Then, it performs two passes: one from left to right to satisfy the increasing rating condition with the left neighbor, and another from right to left to satisfy the increasing rating condition with the right neighbor. During the second pass, we use `max()` to ensure the left-to-right candy count is preserved when applicable, to handle scenarios where the initial count based on the left neighbor is better for the overall min candy distribution.

Step-by-Step Algorithm

Step 1: Initialize an array `candies` of the same size as the `ratings` array, with each element set to 1. This ensures each child initially receives at least one candy.
Step 2: Iterate through the `ratings` array from left to right (from index 1 to n-1). If a child's rating is higher than the rating of the child to its left, update the child's candy count to be one more than the candy count of the child to its left: `candies[i] = candies[i-1] + 1`.
Step 3: Iterate through the `ratings` array from right to left (from index n-2 to 0). If a child's rating is higher than the rating of the child to its right, update the child's candy count to be the maximum of its current candy count and one more than the candy count of the child to its right: `candies[i] = max(candies[i], candies[i+1] + 1)`.
Step 4: Calculate the sum of all the elements in the `candies` array. This sum represents the minimum number of candies required to satisfy the given conditions.
Step 5: Return the calculated sum.

Key Insights

Insight 1: The problem can be solved by making two passes through the ratings array: one from left to right and another from right to left. This ensures that both neighbors are considered when distributing candies.
Insight 2: Each child's candy count depends on its immediate neighbors. We can initialize each child with one candy and then adjust the counts based on their neighbors' ratings during each pass.
Insight 3: The second pass needs to consider the candy counts already assigned in the first pass. If a child has a higher rating than its right neighbor but already has fewer or the same candies, its candy count needs to be updated.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Array, Greedy.

Companies

Asked at: Accenture, ConsultAdd, Flipkart, Goldman Sachs, Komprise, Mastercard, PhonePe, Tencent, Teradata, Uber, Urban Company, Yandex.

Candy | LeetCode 135

Hard

Array Greedy

Time: O(n)Space: O(n)

Solution Code

Available in:

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];
        for (int i = 0; i < n; i++) {
            candies[i] = 1;
        }

        // First pass: from left to right
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        // Second pass: from right to left
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
        }

        int sum = 0;
        for (int candy : candies) {
            sum += candy;
        }

        return sum;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 135: Candy - Detailed explanation and solution approaches.

Topics

Array Greedy

Companies

AccentureConsultAddFlipkartGoldman SachsKompriseMastercardPhonePeTencent

Stats

Difficulty:Hard

Languages:4

Companies:12

Problem #:135

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

5 steps

1
Step 1: Initialize an array `candies` of the same size as the `ratings` array, with each element set to 1. This ensures each child initially receives at least one candy.
2
Step 2: Iterate through the `ratings` array from left to right (from index 1 to n-1). If a child's rating is higher than the rating of the child to its left, update the child's candy count to be one more than the candy count of the child to its left: `candies[i] = candies[i-1] + 1`.
3
Step 3: Iterate through the `ratings` array from right to left (from index n-2 to 0). If a child's rating is higher than the rating of the child to its right, update the child's candy count to be the maximum of its current candy count and one more than the candy count of the child to its right: `candies[i] = max(candies[i], candies[i+1] + 1)`.
4
Step 4: Calculate the sum of all the elements in the `candies` array. This sum represents the minimum number of candies required to satisfy the given conditions.
5
Step 5: Return the calculated sum.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is linear as the solution iterates through the input array a fixed number of times (specifically, three times). The space complexity is also linear because the size of the auxiliary `candies` array scales linearly with the input size.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Sorting Based Approach

Sort the indices based on ratings, then iterate through the sorted indices. This approach requires sorting the ratings which takes O(n log n) time. Using a hashmap to store the rating and index pair can make implementation easier. However, this is not a good approach since there's a O(n) solution available.

Time: O(n log n)Space: O(n)

Trade-offs: This approach is less efficient than the two-pass greedy approach due to the sorting step. It might be useful if you needed to perform other operations on the sorted ratings.

✨

Key Insights

1Insight 1: The problem can be solved by making two passes through the ratings array: one from left to right and another from right to left. This ensures that both neighbors are considered when distributing candies.
2Insight 2: Each child's candy count depends on its immediate neighbors. We can initialize each child with one candy and then adjust the counts based on their neighbors' ratings during each pass.
3Insight 3: The second pass needs to consider the candy counts already assigned in the first pass. If a child has a higher rating than its right neighbor but already has fewer or the same candies, its candy count needs to be updated.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Greedy Algorithm

Making the best choice at each step without looking ahead.

Edge Cases

Edge case 1: Empty input array. The code implicitly handles this correctly because loops won't execute and 0 will be returned.
Edge case 2: All children have the same rating. The solution assigns one candy to each child in this case, which is the minimum required.
Edge case 3: Ratings are in strictly decreasing order. The algorithm correctly handles this, ensuring the first child receives n candies, the second n-1, and so on.
Edge case 4: Ratings are in strictly increasing order. The algorithm correctly handles this, ensuring the first child receives 1 candy, the second 2, and so on.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Only performing one pass (e.g., only left to right). This will not correctly handle scenarios where a child's candy count needs to be increased based on their right neighbor's rating.

✗Common mistake 2: Failing to use `max()` during the right-to-left pass. Without `max()`, the candy counts assigned during the left-to-right pass might be overwritten, potentially leading to a suboptimal solution.

✗Common mistake 3: Incorrectly comparing ratings with `>` instead of `>=`, or vice-versa when the problem's constraints need to be met. In this case we want strictly greater.

✗Common mistake 4: Using `if` instead of `while` loops. `if` statements only apply the logic once, whereas sometimes more adjustment is needed. In this case, the two-pass solution covers the cases correctly.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Resource allocation. Imagine allocating computing resources to different tasks based on their priority. Each task must get a minimum amount of resources, and tasks with higher priority get more resources than their immediate neighbors.

🏦Real-world scenario 2: Employee compensation. Consider adjusting employee bonuses based on their performance rating, ensuring that everyone receives a minimum bonus and that higher-performing employees receive more than their neighbors. This makes the company appear fair overall.

🎮Real-world scenario 3: Load balancing. Distributing workload among servers, ensuring each has a base load and servers with higher capacity handle more load than their peers.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Hard problems often combine multiple techniques. Break the problem into sub-problems.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

👨‍💻 From Experience

I encountered a variation of this problem in a system design interview. The key was recognizing the underlying pattern.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 14, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 13

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 6

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

What are common greedy problem patterns?

Activity selection (sort by end time), interval scheduling (sort by start/end), Huffman coding (always combine smallest), fractional knapsack (sort by value/weight ratio), and minimum spanning tree. Look for problems where local decisions don't affect future options.

Is it okay to not fully solve hard problems in interviews?

Yes! Interviewers care more about your problem-solving process than the final answer. Demonstrate: clear communication, systematic approach, ability to recognize when to pivot strategies, and graceful handling of hints. Partial progress with good reasoning is valued.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Candy"?

For this hard-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether greedy techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?