Reducing Dishes

Leetcode Daily Challenge (29th March, 2023)

29 March, 2023

Contributors

Lakshit Chiranjiv Sagar

@lakshit-cs

Problem Statement:-

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 dishes preparation.

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

Link: https://leetcode.com/problems/reducing-dishes/

Problem Explanation with examples:-

Example 1

Input: satisfaction = [-1,-8,0,5,-9]
Output: 14
Explanation: After Removing the second and last dish, the maximum total like-time coefficient will be equal to (-1*1 + 0*2 + 5*3 = 14).
Each dish is prepared in one unit of time.

Example 2

Input: satisfaction = [4,3,2]
Output: 20
Explanation: Dishes can be prepared in any order, (2*1 + 3*2 + 4*3 = 20)

Example 3

Input: satisfaction = [-1,-4,-5]
Output: 0
Explanation: People do not like the dishes. No dish is prepared.

Constraints

n == satisfaction.length
1 <= n <= 500
-1000 <= satisfaction[i] <= 1000

Intuition:-

We will sort the array in ascending order to have the time factor as high as possible for the higher satisfaction values.
We will use a recursive function to solve this problem picking and not picking the current value at each step and returning the max of the two.
We will use memoization to store the results of the subproblems to avoid recomputation.
Starting from the first index and time as 1, we will return the max of the two cases (pick and not pick).
We will return 0 if we reach the end of the array

Solution:-

Sort the array.
Define a recursive function with memoization using a cache decorator.
The recursive function will take the index and time as parameters.
If we reach the end of the array, we will return 0.
The pick case will be the recursive call with index+1 and time+1 added to the product of the current satisfaction value and time.
The not-pick case will be the recursive call with index+1 and time.
We will return the max of the two cases.
We will return the recursive call with index 0 and time 1.

Code:-

JAVA Solution

class Solution {
    public int maxSatisfaction(int[] satisfaction) {
        Arrays.sort(satisfaction);

        HashMap<String, Integer> memo = new HashMap<>();
        return solve(satisfaction, 0, 1, memo);
    }

    private int solve(int[] satisfaction, int i, int t, HashMap<String, Integer> memo) {
        if (i == satisfaction.length) {
            return 0;
        }

        String key = i + "," + t;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        int pick = solve(satisfaction, i+1, t+1, memo) + (t*satisfaction[i]);
        int not_pick = solve(satisfaction, i+1, t, memo);

        int result = Math.max(pick, not_pick);
        memo.put(key, result);

        return result;
    }
}

Python Solution

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:

        satisfaction.sort()

        @cache
        def solve(i,t):
            if i == len(satisfaction):
                return 0

            pick = solve(i+1,t+1) + (t*satisfaction[i])
            not_pick = solve(i+1,t)

            return max(pick,not_pick)

        return solve(0,1)

Complexity Analysis:-

TIME:-

The time complexity of the recursive algorithm with memoization is O(n^2), where n is the length of the input array. This is because the algorithm solves subproblems for every possible combination of i and t, and there are n * n possible combinations.

SPACE:-

The space complexity of the algorithm is also O(n^2), due to the memoization table. The table stores the results of subproblems for every possible combination of i and t, which are n * n entries.