#1744

Medium

LeetCode Problem Workspace

Can You Eat Your Favorite Candy on Your Favorite Day?

Determine if you can eat a candy of your favorite type on a specific day, given daily limits and candy availability.

Problem Statement

You are given an array candiesCount of positive integers, where each element represents the number of candies available for a particular type of candy. You are also provided a list of queries, where each query consists of three values: favoriteType, favoriteDay, and dailyCap. The goal is to determine whether you can eat a candy of type favoriteType on the given favoriteDay without exceeding dailyCap candies consumed on any day.

For each query, return true if it's possible to eat a candy of the favorite type on the favorite day following the rules, and false otherwise. Specifically, the number of candies eaten on any day must not exceed the dailyCap, and you can consume different types of candy on the same day as long as this condition is met.

Examples

Example 1

Input: candiesCount = [7,4,5,3,8], queries = [[0,2,2],[4,2,4],[2,13,1000000000]]

Output: [true,false,true]

1- If you eat 2 candies (type 0) on day 0 and 2 candies (type 0) on day 1, you will eat a candy of type 0 on day 2. 2- You can eat at most 4 candies each day. If you eat 4 candies every day, you will eat 4 candies (type 0) on day 0 and 4 candies (type 0 and type 1) on day 1. On day 2, you can only eat 4 candies (type 1 and type 2), so you cannot eat a candy of type 4 on day 2. 3- If you eat 1 candy each day, you will eat a candy of type 2 on day 13.

Example 2

Input: candiesCount = [5,2,6,4,1], queries = [[3,1,2],[4,10,3],[3,10,100],[4,100,30],[1,3,1]]

Output: [false,true,true,false,false]

Example details omitted.

Constraints

1 <= candiesCount.length <= 105
1 <= candiesCount[i] <= 105
1 <= queries.length <= 105
queries[i].length == 3
0 <= favoriteTypei < candiesCount.length
0 <= favoriteDayi <= 109
1 <= dailyCapi <= 109

Solution Approach

Prefix Sum Calculation

Start by calculating the cumulative number of candies available up to each type using a prefix sum array. This helps efficiently determine how many candies can be consumed by the favorite day.

Binary Search for Favorite Day

For each query, use binary search to quickly find if the favorite day falls within the possible days where the favorite candy type can be consumed based on the prefix sum of candies.

Range Checking with Daily Cap

For each query, check whether the total number of candies consumed before and on the favorite day respects the dailyCap constraint. If the number of candies exceeds the cap, return false; otherwise, return true.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the approach chosen: calculating the prefix sum takes linear time, and each query requires binary search, which takes logarithmic time. Thus, the overall time complexity is O(N + Q log N), where N is the length of candiesCount and Q is the number of queries. Space complexity is O(N) due to the prefix sum array.

What Interviewers Usually Probe

Ability to understand array manipulation and prefix sum optimization.
Knowledge of binary search and how to apply it in practical problems.
Strong understanding of time complexity and its application in large input sizes.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the role of the dailyCap constraint and not checking it properly for each query.
Forgetting to use prefix sum for efficient range calculations.
Not optimizing for large inputs, resulting in time limit exceeded errors due to inefficient approaches.

Follow-up variants

What if the candiesCount array had more types of candies? Consider how the solution scales.
How does the problem change if we introduce variable daily caps instead of a fixed one?
What if we need to handle queries with a wider range of favorite days or candy types?

FAQ

What is the key approach for solving "Can You Eat Your Favorite Candy on Your Favorite Day?"?

The key approach involves using a prefix sum array to efficiently calculate the total number of candies available up to each type, combined with binary search to find the favorite day within the valid range.

How does the dailyCap affect the solution?

The dailyCap limits the number of candies you can consume each day. For each query, you must check if the total number of candies consumed before and on the favorite day fits within this cap.

What happens if the favorite day exceeds the available number of days?

If the favorite day exceeds the available days, it will be impossible to eat the favorite candy type on that day, so the answer for that query will be false.

Can this problem be solved using brute force?

While brute force might work for small inputs, it will not scale for large inputs due to time complexity. A more efficient approach involves prefix sums and binary search.

What is the expected time complexity for this problem?

The expected time complexity is O(N + Q log N), where N is the length of candiesCount and Q is the number of queries, due to the prefix sum calculation and binary search for each query.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

class Solution:
    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:
        s = list(accumulate(candiesCount, initial=0))
        ans = []
        for t, day, mx in queries:
            least, most = day, (day + 1) * mx
            ans.append(least < s[t + 1] and most > s[t])
        return ans

Continue Practicing

#1738 find kth largest xor coordinate value #1732 find the highest altitude #1769 minimum number of operations to move all balls to each box