Fruits Into Baskets II

Easy

Asked by:

0 views

Topics:

ArraysGreedy Algorithms

You are given two arrays of integers, fruits and baskets, each of length n, where fruits[i] represents the quantity of the i^th type of fruit, and baskets[j] represents the capacity of the j^th basket.

From left to right, place the fruits according to these rules:

Each fruit type must be placed in the leftmost available basket with a capacity greater than or equal to the quantity of that fruit type.
Each basket can hold only one type of fruit.
If a fruit type cannot be placed in any basket, it remains unplaced.

Return the number of fruit types that remain unplaced after all possible allocations are made.

Example 1:

Input: fruits = [4,2,5], baskets = [3,5,4]

Output: 1

Explanation:

fruits[0] = 4 is placed in baskets[1] = 5.
fruits[1] = 2 is placed in baskets[0] = 3.
fruits[2] = 5 cannot be placed in baskets[2] = 4.

Since one fruit type remains unplaced, we return 1.

Example 2:

Input: fruits = [3,6,1], baskets = [6,4,7]

Output: 0

Explanation:

fruits[0] = 3 is placed in baskets[0] = 6.
fruits[1] = 6 cannot be placed in baskets[1] = 4 (insufficient capacity) but can be placed in the next available basket, baskets[2] = 7.
fruits[2] = 1 is placed in baskets[1] = 4.

Since all fruits are successfully placed, we return 0.

Constraints:

n == fruits.length == baskets.length
1 <= n <= 100
1 <= fruits[i], baskets[i] <= 1000

Fruits Into Baskets II

Easy

Asked by:

0 views

Topics:

ArraysGreedy Algorithms

You are given two arrays of integers, fruits and baskets, each of length n, where fruits[i] represents the quantity of the i^th type of fruit, and baskets[j] represents the capacity of the j^th basket.

From left to right, place the fruits according to these rules:

Each fruit type must be placed in the leftmost available basket with a capacity greater than or equal to the quantity of that fruit type.
Each basket can hold only one type of fruit.
If a fruit type cannot be placed in any basket, it remains unplaced.

Return the number of fruit types that remain unplaced after all possible allocations are made.

Example 1:

Input: fruits = [4,2,5], baskets = [3,5,4]

Output: 1

Explanation:

fruits[0] = 4 is placed in baskets[1] = 5.
fruits[1] = 2 is placed in baskets[0] = 3.
fruits[2] = 5 cannot be placed in baskets[2] = 4.

Since one fruit type remains unplaced, we return 1.

Example 2:

Input: fruits = [3,6,1], baskets = [6,4,7]

Output: 0

Explanation:

fruits[0] = 3 is placed in baskets[0] = 6.
fruits[1] = 6 cannot be placed in baskets[1] = 4 (insufficient capacity) but can be placed in the next available basket, baskets[2] = 7.
fruits[2] = 1 is placed in baskets[1] = 4.

Since all fruits are successfully placed, we return 0.

Constraints:

n == fruits.length == baskets.length
1 <= n <= 100
1 <= fruits[i], baskets[i] <= 1000

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible values of the characters in the `fruits` array, and is the input array guaranteed to be non-empty?
If the input array contains only one type of fruit, what should the expected output be?
If no two fruits can be picked (e.g., the first three fruits are all different), what should be returned?
Does the starting position impact the maximal number of fruits picked, or can I choose any starting position?
Are there any memory constraints beyond the input array itself that I should be aware of?

Brute Force Solution

Approach

The brute force approach to the Fruits Into Baskets problem is like trying every single possible picking combination. We start by considering the smallest possible range of fruit and expand it until we find the longest valid picking sequence. We keep track of the best one found so far.

Here's how the algorithm would work step-by-step:

Start by considering the first fruit alone as the initial pick.
Next, consider the first two fruits, then the first three, and so on, each time extending the range of fruits you are picking.
For each range of fruits, check if it satisfies the basket constraint, which typically means having at most two types of fruits.
If the fruit range is valid, remember its length.
Keep doing this until you've considered every possible range of fruits, from the start to the end.
Compare all the valid lengths that you remembered.
Choose the longest valid length. That's the maximum number of fruits you can pick while following the basket constraint.

Code Implementation

def fruits_into_baskets_brute_force(fruits):
    maximum_fruits_picked = 0

    for starting_index in range(len(fruits)):
        fruits_in_baskets = {}
        fruits_picked_from_start = 0

        for current_index in range(starting_index, len(fruits)):
            fruit_type = fruits[current_index]

            # Check if adding this fruit exceeds basket limit
            if fruit_type not in fruits_in_baskets and len(fruits_in_baskets) == 2:
                break

            if fruit_type not in fruits_in_baskets:
                fruits_in_baskets[fruit_type] = 0

            fruits_in_baskets[fruit_type] += 1
            fruits_picked_from_start += 1

        # Update max fruits picked
        maximum_fruits_picked = max(maximum_fruits_picked, fruits_picked_from_start)

    return maximum_fruits_picked

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The outer loop iterates through each fruit in the array of n fruits, defining the starting point of a possible picking range. The inner loop expands the picking range from the starting point to the end of the array. For each range, a check is performed to validate the basket constraint. In the worst case, every possible sub-array is checked. Thus, the time complexity approximates to n * (n+1) / 2 operations, which simplifies to O(n²).

Space Complexity

O(1) – The brute force approach iterates through all possible subarrays. It appears the described algorithm primarily utilizes a few integer variables (like current range length and max length) and does not create any auxiliary data structures that scale with the input size N (number of fruits). No temporary lists, hash maps, or recursion are explicitly mentioned in the plain English description, suggesting constant extra space. Thus, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The best way to solve this is to use a 'sliding window' to keep track of the different types of fruit in our baskets. We efficiently expand the window to include more fruit, and shrink it when we have too many types, always aiming to maximize the fruit we pick.

Here's how the algorithm would work step-by-step:

Imagine a window moving across the row of fruit trees.
We'll keep track of how many of each type of fruit are currently within that window.
We keep expanding the window to the right, adding more fruit to our baskets.
If we end up with more than two types of fruit in our window, we need to shrink it from the left.
We remove fruit types from the left until we only have two types of fruit left in our window.
At each step, we calculate how much fruit we've collected inside the window, and keep track of the largest amount.
We repeat this process until the window has moved through all the trees, so we now know the maximum amount of fruit we can collect, while only holding two fruit types.

Code Implementation

def fruits_into_baskets_two(fruits):
    window_start = 0
    fruit_frequency = {}
    min_removed = float('inf')

    for window_end in range(len(fruits)):
        right_fruit = fruits[window_end]
        if right_fruit not in fruit_frequency:
            fruit_frequency[right_fruit] = 0
        fruit_frequency[right_fruit] += 1

        # Shrink the sliding window until we have at most two fruit types
        while len(fruit_frequency) > 2:
            left_fruit = fruits[window_start]
            fruit_frequency[left_fruit] -= 1
            if fruit_frequency[left_fruit] == 0:
                del fruit_frequency[left_fruit]
            window_start += 1

        # Calculate the number of fruits removed to keep 2 types
        current_length = window_end - window_start + 1

        # Update the minimum number of removed fruits
        min_removed = min(min_removed, len(fruits) - current_length)

    # If min_removed is still infinity, it means all fruits can be put in one basket
    if min_removed == float('inf'):
        return 0

    return min_removed

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm uses a sliding window approach that iterates through the input array of fruit trees once. The window expands to the right, and shrinks from the left when necessary, ensuring that each element is visited at most twice (once when the window expands and once when it shrinks). Since the number of operations is proportional to the number of fruit trees (n), the time complexity is O(n).

Space Complexity

O(1) – The provided solution uses a sliding window approach, primarily managing the fruit types within the window using a counter or similar mechanism. The number of distinct fruit types tracked is limited to two, implying a fixed-size data structure, such as a hash map or dictionary, with at most two entries. This data structure, along with a few integer variables for window boundaries and maximum count, constitutes the auxiliary space. Since the space used is independent of the input size (N, the number of trees), the space complexity is constant.

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 as no fruits can be picked.
Array with only one type of fruit	Return the length of the array since all fruits can be picked.
Array with two types of fruit	Return the length of the array since all fruits can be picked.
Array with all fruits of the same type	Return the length of the array.
Array with a long sequence of one fruit type followed by another single fruit	Sliding window needs to correctly adjust the start index after a new fruit type appears.
Input array containing only two distinct fruit types spread unevenly.	Sliding window algorithm needs to correctly identify the longest sequence.
Integer overflow if the fruit count is extremely large.	Use a data type that can handle large numbers, such as long or consider breaking if input fruit array is excessively large.
Starting from a sub optimal starting position.	Test all possible starting position to determine optimal starting point that produces maximum length.