🔗 submission url

🧩 Problem: Fruits Into Baskets II

LeetCode link

Description

You are given two arrays of integers,fruitsandbaskets, each of lengthn, wherefruits[i]represents thequantityof theithtype of fruit, andbaskets[j]represents thecapacityof thejthbasket.From left to right, place the fruits according to these rules:Each fruit type must be placed in theleftmost available basketwith a capacitygreater than or equalto the quantity of that fruit type.Each basket can holdonly onetype of fruit.If a fruit typecannot be placedin any basket, it remainsunplaced.Return the number of fruit types that remain unplaced after all possible allocations are made.

Examples

Example 1:

Input: fruits = [4,2,5], baskets = [3,5,4]
Output: 1
Explanation: fruits[0] = 4is placed inbaskets[1] = 5.fruits[1] = 2is placed inbaskets[0] = 3.fruits[2] = 5cannot be placed inbaskets[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] = 3is placed inbaskets[0] = 6.fruits[1] = 6cannot be placed inbaskets[1] = 4(insufficient capacity) but can be placed in the next available basket,baskets[2] = 7.fruits[2] = 1is placed inbaskets[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

My Solution

⏱ Runtime: 9 ms
🧠 Memory: 18 MB

Code

class Solution:
    def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
        for fruit in fruits:
            for basket in baskets:
                if fruit <= basket:
                    baskets.remove(basket)
                    break
        
        return len(baskets)
        

Approach

Wanted to use 'Segment Tree' but didn't know how.
So search right basket from the fornt and Change baskets[i] directly to not use check

Python Grammar

# changing list element
for i, basket in enumerate(baskets):
	basket = 0  # don't change baskets
	baskets[i] = 0  # change baskets
	
# count number of list element
n = baskets.count(value)

🔁 Feedback

Better Solution

class Solution:
    def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
        for fruit in fruits:
            for basket in baskets:
                if fruit <= basket:
                    baskets.remove(basket)
                    break
        return len(baskets)

Explanation

My second trial.
If a basket once used, don't need to consider it.
So, I just removed and I even didn't need to count 0s.

💬 Review & Thoghts

• How can I use Segment Tree BTW?
• n <= 100 made O(N^2) ok.
• define class if it's needed