Fruits Into Baskets II - Practice Coding Problems

Fruits Into Baskets II - Problem

Array Binary Search Segment Tree Simulation Ordered Set Easy

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.

Input & Output

Example 1 — Basic Case

$ Input: fruits = [3,1,2], baskets = [2,3,1]

› Output: 0

💡 Note: Fruit 3 goes to basket 3 (capacity 3), fruit 1 goes to basket 1 (capacity 2), fruit 2 goes to basket 2 (capacity 3). All fruits placed successfully.

Example 2 — Some Unplaced

$ Input: fruits = [4,2,1], baskets = [1,2,3]

› Output: 1

💡 Note: Fruit 4 cannot fit in any basket (max capacity is 3), fruit 2 goes to basket 2 (capacity 2), fruit 1 goes to basket 1 (capacity 1). One fruit remains unplaced.

Example 3 — All Unplaced

$ Input: fruits = [5,6,7], baskets = [1,2,3]

› Output: 3

💡 Note: All fruits are too large for any basket. All 3 fruits remain unplaced.

Constraints

1 ≤ fruits.length, baskets.length ≤ 10³
1 ≤ fruits[i], baskets[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Arrays of fruit quantities and basket capacities

Process

Place each fruit in leftmost suitable basket

Output

Count of unplaceable fruits

Key Takeaway

🎯 Key Insight: Always process fruits in order and select the leftmost available basket with sufficient capacity

Asked in

G Google 25 a Amazon 20 M Microsoft 15

The key insight is to process fruits in order and always choose the leftmost available basket that can accommodate each fruit. The greedy approach works because we must respect the left-to-right constraint. Best approach is greedy simulation with Time: O(n²), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n²)	O(n)	For each fruit, linearly search for the leftmost available basket
Greedy with Linear Search	O(n²)	O(n)	Optimize by tracking used baskets more efficiently

Brute Force — Algorithm Steps

Iterate through each fruit type
For each fruit, scan baskets left to right
Find first available basket with enough capacity
Mark basket as used or increment unplaced count

Visualization

Tap to expand

Step-by-Step Walkthrough

Process Fruit 1

Scan baskets left to right until suitable one found

Process Fruit 2

Skip used baskets, find next available

Count Result

Count fruits that couldn't be placed

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int solution(int* fruits, int* baskets, int n) {
    bool* used = (bool*)calloc(n, sizeof(bool));
    int unplaced = 0;
    
    for (int i = 0; i < n; i++) {
        bool placed = false;
        for (int j = 0; j < n; j++) {
            if (!used[j] && baskets[j] >= fruits[i]) {
                used[j] = true;
                placed = true;
                break;
            }
        }
        if (!placed) {
            unplaced++;
        }
    }
    
    free(used);
    return unplaced;
}

int main() {
    char line1[1000], line2[1000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    // Simple parsing for arrays
    int fruits[100], baskets[100];
    int n = 0;
    
    // Parse first array
    char* token = strtok(line1, "[,]");
    while (token != NULL && n < 100) {
        fruits[n++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    // Parse second array  
    int m = 0;
    token = strtok(line2, "[,]");
    while (token != NULL && m < 100) {
        baskets[m++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    printf("%d\n", solution(fruits, baskets, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n fruits, we potentially scan all n baskets

⚠ Quadratic Growth

Space Complexity

O(n)

Boolean array to track which baskets are used

⚡ Linearithmic Space

12.0K Views

Medium Frequency

~15 min Avg. Time

580 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler