Can You Eat Your Favorite Candy on Your Favorite Day?

Can You Eat Your Favorite Candy on Your Favorite Day? - Problem

You are given a 0-indexed array of positive integers candiesCount where candiesCount[i] represents the number of candies of the i-th type you have. You are also given a 2D array queries where queries[i] = [favoriteType_i, favoriteDay_i, dailyCap_i].

You play a game with the following rules:

You start eating candies on day 0.
You cannot eat any candy of type i unless you have eaten all candies of type i - 1.
You must eat at least one candy per day until you have eaten all the candies.

For each query, determine if you can eat a candy of type favoriteType_i on day favoriteDay_i without eating more than dailyCap_i candies on any day.

Return a boolean array answer where answer[i] is true if you can eat your favorite candy on your favorite day for query i, and false otherwise.

Input & Output

Example 1 — Multiple Query Types

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

› Output: [true,false,true]

💡 Note: Query 1: Type 0 candy available days 0-6, day 2 ∈ [0,6] ✓. Query 2: Type 4 needs 11 days minimum, but day 2 < 11 ✗. Query 3: Type 2 available days 1-15, day 13 ∈ [1,15] ✓

Example 2 — Single Type Query

$ Input: candiesCount = [5,2,6,4,1], queries = [[3,1,6],[4,10,3],[3,0,1]]

› Output: [false,true,false]

💡 Note: Query 1: Need 7 days minimum for type 3, day 1 too early. Query 2: Type 4 available days 3-17, day 10 ∈ [3,17] ✓. Query 3: Type 3 earliest day 7, day 0 too early

Example 3 — Edge Case Small Array

$ Input: candiesCount = [1], queries = [[0,0,1],[0,1,1]]

› Output: [true,false]

💡 Note: Only 1 candy of type 0. Available only on day 0. First query matches exactly, second query too late

Constraints

1 ≤ candiesCount.length ≤ 10⁵
1 ≤ candiesCount[i] ≤ 10⁵
1 ≤ queries.length ≤ 10⁵
queries[i].length == 3
0 ≤ favoriteType_i < candiesCount.length
0 ≤ favoriteDay_i ≤ 10⁹
1 ≤ dailyCap_i ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Candy counts array and queries with type, day, and daily limit

Process

Calculate valid day ranges for each candy type using constraints

Output

Boolean array indicating if each query is possible

Key Takeaway

🎯 Key Insight: Use prefix sums to find the earliest and latest day each candy type is available

Asked in

G Google 15 a Amazon 8 f Facebook 6

The key insight is to use prefix sums to quickly calculate the earliest and latest days when each candy type is available. For each query, check if the favorite day falls within this valid range. Best approach is Prefix Sum with Time: O(n + q), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum Optimization	O(n + q)	O(n)	Use prefix sums to quickly calculate candy availability ranges
Brute Force Simulation	O(q × d × c)	O(1)	Simulate all possible eating patterns for each query

Prefix Sum Optimization — Algorithm Steps

Calculate prefix sums of candy counts
For each query, find earliest day to reach favorite type
Find latest day when favorite type is still available
Check if favorite day is in valid range

Visualization

Tap to expand

Step-by-Step Walkthrough

Prefix Sums

Precompute cumulative candy counts for instant lookups

Range Check

Calculate earliest and latest day for each candy type

Quick Answer

O(1) check if favorite day falls in valid range

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool* solution(int* candiesCount, int candiesSize, int** queries, int queriesSize, int* returnSize) {
    // Build prefix sums
    long long* prefixSum = (long long*)malloc((candiesSize + 1) * sizeof(long long));
    prefixSum[0] = 0;
    for (int i = 0; i < candiesSize; i++) {
        prefixSum[i + 1] = prefixSum[i] + candiesCount[i];
    }
    
    bool* result = (bool*)malloc(queriesSize * sizeof(bool));
    *returnSize = queriesSize;
    
    for (int i = 0; i < queriesSize; i++) {
        int favoriteType = queries[i][0];
        long long favoriteDay = queries[i][1];
        long long dailyCap = queries[i][2];
        
        // Candies needed before favorite type
        long long candiesBeforeFavorite = prefixSum[favoriteType];
        
        // Earliest day to start eating favorite type
        long long earliestDay = candiesBeforeFavorite == 0 ? 0 : (candiesBeforeFavorite + dailyCap - 1) / dailyCap;
        
        // Latest day to still be eating favorite type
        long long candiesUpToFavorite = prefixSum[favoriteType + 1];
        long long latestDay = candiesUpToFavorite - 1;
        
        // Check if favorite day is within valid range
        bool possible = earliestDay <= favoriteDay && favoriteDay <= latestDay;
        result[i] = possible;
    }
    
    free(prefixSum);
    return result;
}

int main() {
    // Simple implementation for basic cases
    int candiesCount[] = {7,4,5,3,8};
    int candiesSize = 5;
    
    int q1[] = {0, 2, 2};
    int q2[] = {4, 2, 4};
    int q3[] = {2, 13, 1000000000};
    int* queries[] = {q1, q2, q3};
    int queriesSize = 3;
    
    int returnSize;
    bool* result = solution(candiesCount, candiesSize, queries, queriesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf(result[i] ? "true" : "false");
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + q)

O(n) to build prefix sums, O(1) per query

✓ Linear Growth

Space Complexity

O(n)

Array to store prefix sums of candy counts

⚡ Linearithmic Space

38.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Prefix Sum Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler