Leetcode 1833. Maximum Ice Cream Bars

Photo by Tracy Adams on Unsplash

It is a sweltering summer day, and a boy wants to buy some ice cream bars.

At the store, there are n ice cream bars. You are given an array costs of length n, where costs[i] is the price of the ith ice cream bar in coins. The boy initially has coins coins to spend, and he wants to buy as many ice cream bars as possible.

Return the maximum number of ice cream bars the boy can buy with coins coins.

Note: The boy can buy the ice cream bars in any order.

Example 1:

Input: costs = [1,3,2,4,1], coins = 7
Output: 4
Explanation: The boy can buy ice cream bars at indices 0,1,2,4 for a total price of 1 + 3 + 2 + 1 = 7.

Example 2:

Input: costs = [10,6,8,7,7,8], coins = 5
Output: 0
Explanation: The boy cannot afford any of the ice cream bars.

Example 3:

Input: costs = [1,6,3,1,2,5], coins = 20
Output: 6
Explanation: The boy can buy all the ice cream bars for a total price of 1 + 6 + 3 + 1 + 2 + 5 = 18.

Constraints:

• costs.length == n
• 1 <= n <= 10^5
• 1 <= costs[i] <= 10^5
• 1 <= coins <= 10^8

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;
    }
}

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.