Solution Explanation: 1833. Maximum Ice Cream Bars

This problem asks to find the maximum number of ice cream bars a boy can buy with a given amount of coins, given an array of ice cream bar costs. The key insight is that to maximize the number of bars, we should buy the cheapest ones first. This leads to a greedy approach.

Approach: Greedy Algorithm with Sorting

1. Sort the costs: We sort the costs array in ascending order. This ensures we consider the cheapest ice cream bars first.

2. Iterate and buy: We iterate through the sorted costs array. For each ice cream bar:

   • We check if we have enough coins to buy it (coins >= costs[i]).
   • If we do, we buy it by subtracting its cost from our coins (coins -= costs[i]).
   • If we don't, it means we can't afford any more ice cream bars, so we return the number of ice cream bars we've already bought (i).

3. All bars affordable: If the loop completes without running out of coins, it means we could afford all the ice cream bars, so we return the total number of ice cream bars (len(costs) or costs.length).

Time and Space Complexity Analysis

• Time Complexity: The dominant operation is sorting the costs array. Most sorting algorithms (like merge sort or quicksort used in Python's sort() and Java's Arrays.sort()) have a time complexity of O(n log n), where n is the number of ice cream bars. The subsequent iteration through the sorted array takes O(n) time. Therefore, the overall time complexity is O(n log n), dominated by the sorting step.

• Space Complexity: The space complexity depends on the sorting algorithm used. In-place sorting algorithms like quicksort have O(log n) space complexity in the average case due to the recursive call stack. Merge sort generally uses O(n) space. Python's list.sort() uses Timsort (a hybrid sorting algorithm), which is generally O(n) in the worst case but can be closer to O(log n) in practice. Java's Arrays.sort() uses a hybrid merge sort/insertion sort approach, also roughly O(n) in the worst case and closer to O(log n) on average. Thus, the space complexity is typically considered O(n) in the worst case, or potentially O(log n) on average, depending on the specific sorting implementation. If we consider only the extra space used besides the input array, we can consider it to be O(1) (for the counter in the iterative approach).

Code Examples (Multiple Languages)

The code examples below demonstrate the greedy approach in several programming languages. They all follow the same basic algorithm: sort, iterate, and buy.

Python3

def maxIceCream(costs: list[int], coins: int) -> int:
    costs.sort()  # Sort in ascending order
    bars_bought = 0
    for cost in costs:
        if coins >= cost:
            coins -= cost
            bars_bought += 1
        else:
            break  # Cannot afford anymore
    return bars_bought
 

Java

import java.util.Arrays;
 
class Solution {
    public int maxIceCream(int[] costs, int coins) {
        Arrays.sort(costs); // Sort in ascending order
        int barsBought = 0;
        for (int cost : costs) {
            if (coins >= cost) {
                coins -= cost;
                barsBought++;
            } else {
                break; // Cannot afford anymore
            }
        }
        return barsBought;
    }
}

C++

#include <algorithm>
#include <vector>
 
class Solution {
public:
    int maxIceCream(std::vector<int>& costs, int coins) {
        std::sort(costs.begin(), costs.end()); // Sort in ascending order
        int barsBought = 0;
        for (int cost : costs) {
            if (coins >= cost) {
                coins -= cost;
                barsBought++;
            } else {
                break; // Cannot afford anymore
            }
        }
        return barsBought;
    }
};

JavaScript

/**
 * @param {number[]} costs
 * @param {number} coins
 * @return {number}
 */
var maxIceCream = function(costs, coins) {
    costs.sort((a, b) => a - b); // Sort in ascending order
    let barsBought = 0;
    for (let cost of costs) {
        if (coins >= cost) {
            coins -= cost;
            barsBought++;
        } else {
            break; // Cannot afford anymore
        }
    }
    return barsBought;
};

These code examples all achieve the same result efficiently using a greedy strategy and sorting. The choice of language depends on your preference and the context of the problem's usage.