Reducing Dishes - Practice Coding Problems

Reducing Dishes - Problem

A chef has collected data on the satisfaction level of his n dishes. Chef can cook any dish in 1 unit of time.

Like-time coefficient of a dish is defined as the time taken to cook that dish including previous dishes multiplied by its satisfaction level i.e. time[i] * satisfaction[i].

Return the maximum sum of like-time coefficient that the chef can obtain after preparing some amount of dishes.

Dishes can be prepared in any order and the chef can discard some dishes to get this maximum value.

Input & Output

Example 1 — Mixed Values

$ Input: satisfaction = [-1,0,3,1,2]

› Output: 25

💡 Note: After sorting: [-1,0,1,2,3]. Optimal selection is dishes with satisfaction [1,2,3] cooked in this order. Like-time coefficient: 1×1 + 2×2 + 3×3 = 14. But we can include all dishes: 1×(-1) + 2×0 + 3×1 + 4×2 + 5×3 = 20. Actually, using greedy: 25.

Example 2 — All Negative

$ Input: satisfaction = [-2,-3,-1]

› Output: 0

💡 Note: All satisfaction values are negative. Best strategy is to cook no dishes, resulting in sum = 0.

Example 3 — All Positive

$ Input: satisfaction = [4,3,2]

› Output: 20

💡 Note: All positive values. Sort to [2,3,4]. Cook in this order: 1×2 + 2×3 + 3×4 = 2 + 6 + 12 = 20.

Constraints

1 ≤ satisfaction.length ≤ 500
-1000 ≤ satisfaction[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Array of satisfaction values for n dishes

Process

Select dishes and order them to maximize sum of time×satisfaction

Output

Maximum possible like-time coefficient sum

Key Takeaway

🎯 Key Insight: Sort dishes and use greedy strategy - add dishes while their contribution (suffix sum) remains positive

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is to sort the satisfaction array and use a greedy approach: add dishes from highest satisfaction while the suffix sum remains positive. Each dish contributes its suffix sum to the total score. Best approach is greedy optimization. Time: O(n log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Sort and Try Starting Points	O(n²)	O(1)	Sort satisfaction values, then try different starting positions
Greedy Optimization	O(n log n)	O(1)	Sort and add dishes while the total contribution remains positive
Brute Force - All Subsets	O(n! × 2ⁿ)	O(n)	Generate all possible subsets and try all orderings

Sort and Try Starting Points — Algorithm Steps

Sort satisfaction array in ascending order
Try each position as potential starting point
For each start, include all remaining dishes
Return maximum sum found

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Array

Sort satisfaction values in ascending order

Try Starts

Test each position as potential starting point

Find Max

Return the maximum sum found

Code -

solution.c — C

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

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int max(int a, int b) {
    return a > b ? a : b;
}

int solution(int* satisfaction, int n) {
    qsort(satisfaction, n, sizeof(int), compare);
    int maxSum = 0;
    
    // Try each position as starting point
    for (int start = 0; start < n; start++) {
        int currentSum = 0;
        int time = 1;
        
        // Include all dishes from start position onwards
        for (int i = start; i < n; i++) {
            currentSum += time * satisfaction[i];
            time++;
        }
        
        maxSum = max(maxSum, currentSum);
    }
    
    return maxSum;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array manually
    int satisfaction[500];
    int n = 0;
    
    char* ptr = strchr(line, '[');
    if (ptr != NULL) {
        ptr++;
        char* token = strtok(ptr, ",]");
        while (token != NULL && n < 500) {
            satisfaction[n++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    int result = solution(satisfaction, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Sorting takes O(n log n), then O(n) starting points each with O(n) calculation

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

28.0K Views

Medium Frequency

~15 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

Sort and Try Starting Points — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler