Skip to content

3791. Fruits Into Baskets III

Array Binary Search Segment Tree Ordered Set

Problem - Fruits Into Baskets III

Medium

You are given two arrays of integers, fruits and baskets, each of length n, where fruits[i] represents the quantity of the ith type of fruit, and baskets[j] represents the capacity of the jth 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 <= 105
  • 1 <= fruits[i], baskets[i] <= 109

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
    def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
        n = len(baskets)
        self.segment = [0] * (4 * n)
        self.n = n
        self.build(baskets, 0, n -1, 1)
        num_unplaced = 0
        for fruit in fruits:
            if self.find_and_use(fruit, 0, n - 1, 1) == -1:
                num_unplaced += 1
        return num_unplaced


    def build(self, baskets: List[int], low: int, high: int, index: int):
        if low == high:
            self.segment[index] = baskets[high]
        else:
            mid = (high + low)//2
            self.build(baskets, low, mid, index * 2)
            self.build(baskets, mid + 1, high, index * 2 + 1)
            self.segment[index] = max(self.segment[index * 2], self.segment[index * 2 + 1])

    def find_and_use(self, fruit: int, low: int, high: int, index: int) -> int:
        # seg can't fir the fruit
        if self.segment[index] < fruit:
            return -1
        # at the leaf use this basket
        if low == high:
            self.segment[index] = -1
            return 1

        mid = (high + low)//2
        if self.segment[index * 2] >= fruit:
            result = self.find_and_use(fruit, low, mid, index * 2)
        else:
            result = self.find_and_use(fruit, mid + 1, high, index * 2 + 1)
        self.segment[index] = max(self.segment[index * 2], self.segment[index * 2 + 1])
        return result

Submission Stats:

  • Runtime: 1700 ms (79.83%)
  • Memory: 37.8 MB (31.35%)