#3477

Easy

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Fruits Into Baskets II

Determine the number of fruit types that remain unplaced after all allocations in the "Fruits Into Baskets II" problem.

array binary search segment tree simulation ordered set

Problem Statement

You are given two arrays, fruits and baskets, both of length n. The i-th element in fruits represents the quantity of the ith type of fruit, and the i-th element in baskets represents the capacity of the ith basket. The task is to simulate placing fruits into baskets following specific rules.

The goal is to determine how many fruit types remain unplaced after attempting to allocate them to the baskets. The function should return the number of unallocated fruit types after all possible placements have been made.

Examples

Example 1

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

Output: 1

Since one fruit type remains unplaced, we return 1.

Example 2

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

Output: 0

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 Approach

Binary Search over Valid Answer Space

Use binary search to explore the valid space for the maximum number of fruit types that can be placed in baskets. This reduces the problem's time complexity by narrowing down the possibilities efficiently.

Simulating Fruit Placement

Simulate placing fruits into baskets by iterating through the baskets and checking if each fruit can fit within the available capacity. Track the unplaced fruit types as you go.

Optimization with Early Stopping

Optimize the solution by stopping the search early if you determine that no more fruits can be placed in baskets. This helps avoid unnecessary iterations and speeds up the solution.

Complexity Analysis

Metric	Value
Time	O(n^2)
Space	O(1)

The time complexity is O(n^2) because of the nested loops for simulating fruit placements across baskets. The space complexity is O(1) as no extra space is used beyond a few variables for simulation.

What Interviewers Usually Probe

Can the candidate explain how binary search helps in narrowing down the valid answer space?
Does the candidate simulate the allocation process clearly and efficiently?
Is the candidate aware of optimizations like early stopping to avoid unnecessary checks?

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the problem statement and returning the wrong number of unplaced fruits.
Overcomplicating the binary search logic without focusing on the correct range.
Failing to optimize the simulation step, leading to excessive computation time.

Follow-up variants

What if the number of baskets exceeds the number of fruit types? How does the solution scale?
Can this problem be adapted to handle varying basket types or additional constraints?
How would the solution change if we needed to track which fruits were unplaced, instead of just counting them?

FAQ

How does binary search apply to the "Fruits Into Baskets II" problem?

Binary search is used to narrow down the range of fruit types that can be placed into baskets, optimizing the process.

What is the optimal way to simulate fruit placement in this problem?

The optimal way is to iterate through the baskets, placing fruits while tracking how many types remain unplaced.

What happens if no fruit types can be placed in baskets?

If no fruits can be placed, the solution will return the total number of fruit types as unplaced.

How does GhostInterview help with the binary search optimization?

GhostInterview assists by providing hints and structured feedback on how to approach the binary search effectively for this problem.

Can the "Fruits Into Baskets II" problem be solved with a greedy approach?

A greedy approach is not ideal for this problem, as it requires a more refined search method to efficiently place fruits into baskets.

terminal

Solution

Solution 1: Simulation

We use a boolean array $\textit{vis}$ of length $n$ to record the baskets that have already been used, and a variable $\textit{ans}$ to record the number of fruits that have not been placed, initially $\textit{ans} = n$.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
        n = len(fruits)
        vis = [False] * n
        ans = n
        for x in fruits:
            for i, y in enumerate(baskets):
                if y >= x and not vis[i]:
                    vis[i] = True
                    ans -= 1
                    break
        return ans

Continue Practicing

#3479 fruits into baskets iii #2659 make array empty #3454 separate squares ii