How Many Apples Can You Put into the Basket

class Solution {
    public int maximumApples(int[] weights) {
        int maxWeight = -1;
        for (int weight : weights) {
            maxWeight = Math.max(maxWeight, weight);
        }
        int[] frequency = new int[maxWeight + 1];
        for (int weight : weights) {
            frequency[weight]++;
        }

        int totalApples = 0, currentWeight = 0;
        for (int i = 0; i <= maxWeight; i++) {
            if (frequency[i] > 0) {
                int possibleToTake = Math.min(frequency[i], (5000 - currentWeight) / i);
                if (possibleToTake == 0) {
                    break;
                }
                currentWeight += possibleToTake * i;
                totalApples += possibleToTake;
            }
        }
        return totalApples;
    }
}

In the Java-based solution provided, the goal is to determine the maximum number of apples you can carry in a basket without exceeding a weight limit of 5000 units. The approach uses a greedy algorithm and the following steps outline the implementation:

1. Initialize maxWeight to -1 to find the heaviest apple by iterating over the input apple weights array and updating maxWeight using the built-in Math.max() function.

2. Create a frequency array to count occurrences of each weight. The size of the array is maxWeight + 1 (to account for all weights from 0 to maxWeight), and the array is populated by iterating through the weights again.

3. Set totalApples initially to 0, representing the count of apples in the basket, and currentWeight to 0, representing the current total weight of the basket. Proceed through each unique apple weight from lightest to heaviest.

4. For each weight in the frequency array:

   • Calculate possibleToTake, the maximum number of apples of that weight that can still fit in the basket without exceeding the 5000 unit limit. This is determined by taking the minimum between how many apples of that weight are available (frequency[i]) and how many apples of that weight can fit given the remaining capacity of the basket.
   • If no apples of that weight can be added (i.e., possibleToTake is zero), exit the loop as adding heavier apples would also exceed the limit.
   • Add the product of possibleToTake and the apple weight to currentWeight and add possibleToTake to totalApples.

5. Return totalApples, which now contains the maximum number of apples that fit within the weight limit.

This algorithm effectively compiles the maximum number of apples that can be placed in the basket without surpassing the total weight allowance, ensuring that as many apples are included as possible until the weight limit is hit or all weight categories are evaluated.

class Solution:
    def maximumApples(self, weights: List[int]) -> int:
        max_size = max(weights) + 1
        fruit_counts = [0] * max_size
        for weight in weights:
            fruit_counts[weight] += 1

        total_apples = total_weight = 0
        for idx in range(max_size):
            if fruit_counts[idx] > 0:
                available_to_take = min(fruit_counts[idx], (5000 - total_weight) // idx)
                if available_to_take == 0:
                    break

                total_apples += available_to_take
                total_weight += available_to_take * idx
        return total_apples

The Python code provided calculates the maximum number of apples that can be placed into a basket, given the constraints on total weight. They key idea in the solution is to use a greedy algorithm that leverages sorting and counting each apple's weight. Here’s a breakdown of the steps taken:

1. First, determine the maximum weight among all the apples for creating a list long enough to track all possible weights.
2. Create a list fruit_counts to count how many apples exist for each weight.
3. Iterate through the apple weights updating the fruit_counts list to reflect the number of apples for each specific weight.
4. Initialize total_apples and total_weight to zero, which will keep track of the total apples in the basket and their cumulative weight.
5. Iterate through the weights. For each weight, calculate the maximum number of apples that can be added without exceeding the total allowed weight of 5000.
6. If adding apples of a particular weight would exceed the weight limit, skip to the next lighter apple (if any), otherwise add as many apples as possible up to either their available count or the maximum that the basket can still handle.
7. Return the total number of apples (total_apples) that can be put into the basket without exceeding the weight limit of 5000.

The solution is optimal and efficiently handles the problem by considering apples based on their weight, ensuring that the basket carries the maximum number of apples possible within the given weight constraint.