DEV Community

Cover image for Leetcode 1833 : Maximum Ice Cream Bars
Rohith V
Rohith V

Posted on

Leetcode 1833 : Maximum Ice Cream Bars

Intuition

The question is to find the maximum number of chocolates the boy can have within the limit coins. So to have maximum chocolates, it is always optimal to buy the chocolate bars at a small cost. So we can sort the costs array and just keep on checking whether it's okay to buy the current chocolate with the money in hand.

Approach

  1. Sort the array.
  2. Traverse through the array keeping a running sum.
  3. Increment the running sum with the cost and check whether the running sum is less than or equal to the cost limit. If yes, then we can buy that chocolate bar, or else we will stop.
  4. Once gets out of the array, return the count of chocolate bars.

Complexity

  • Time complexity:
    We are sorting the array and also traversing through the array once.
    So time complexity will be O(nlogn) + O(n) where n = length of the array.

  • Space complexity:
    The sorting can take up some amount of space. But other than that, we are not making use of any extra space. So space complexity will be O(1).

Code

class Solution {
    public int maxIceCream(int[] costs, int coins) {
        int length = costs.length;
        // eventhough the constraint starts from 1, 
        // just adding as part of practice
        if (length == 0 || costs == null) {
            return 0;
        }
        if (coins <= 0) {
            return 0;
        }
        Arrays.sort(costs);
        int runningSum = 0;
        int chocolateBar = 0;
        for (int num : costs) {
            runningSum += num;
            if (runningSum <= coins) {
                chocolateBar++;
            }
            else {
                break;
            }
        }
        return chocolateBar;
    }
}
Enter fullscreen mode Exit fullscreen mode

Please feel free to suggest a better approach or a different approach for the same problem. Also, correct me if I have any mistakes.
Thanks.

Top comments (0)