Fruits Into Baskets III - Practice Coding Problems

Fruits Into Baskets III - Problem

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 = [4,2,1], baskets = [5,1,3]

› Output: 0

💡 Note: Fruit 4 goes to basket 5 (index 0), fruit 2 goes to basket 3 (index 2), fruit 1 goes to basket 1 (index 1). All fruits are placed.

Example 2 — Some Unplaced

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

› Output: 2

💡 Note: First fruit 3 goes to basket 3 (index 0). Second and third fruits cannot be placed as remaining baskets have capacity 1 < 3.

Example 3 — All Unplaced

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

› Output: 2

💡 Note: No basket has sufficient capacity (5) for any fruit, so both remain unplaced.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ fruits[i], baskets[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Arrays of fruit quantities and basket capacities

Process

Match each fruit to leftmost suitable basket

Output

Count of unplaced fruits

Key Takeaway

🎯 Key Insight: Always choose the leftmost available basket that can accommodate each fruit

Asked in

G Google 45 A Amazon 38 M Microsoft 32

The key insight is to efficiently find the leftmost available basket with sufficient capacity for each fruit. The brute force approach scans all baskets for each fruit in O(n²). An optimized approach can use binary search after sorting baskets, though we still need to find the leftmost among candidates. Best approach: Time O(n²), Space O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Linear Search	O(n²)	O(n)	For each fruit, scan all baskets from left to right to find the first available one with enough capacity
Optimized with Sorted Baskets	O(n² log n)	O(n)	Sort baskets with indices, then use binary search to find the leftmost available basket for each fruit

Brute Force - Linear Search — Algorithm Steps

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

Visualization

Tap to expand

Step-by-Step Walkthrough

Process Fruit 1

Scan baskets left to right for first fit

Process Fruit 2

Scan remaining baskets for next fruit

Count Unplaced

Return number of 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++) {
        int fruitQuantity = fruits[i];
        bool placed = false;
        
        // Find leftmost available basket with enough capacity
        for (int j = 0; j < n; j++) {
            if (!used[j] && baskets[j] >= fruitQuantity) {
                used[j] = true;
                placed = true;
                break;
            }
        }
        
        if (!placed) {
            unplaced++;
        }
    }
    
    free(used);
    return unplaced;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse fruits array
    int fruits[100], baskets[100];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL && n < 100) {
        if (strlen(token) > 0 && token[0] != '\n') {
            fruits[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    fgets(line, sizeof(line), stdin);
    int m = 0;
    token = strtok(line, "[,]");
    while (token != NULL && m < 100) {
        if (strlen(token) > 0 && token[0] != '\n') {
            baskets[m++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(fruits, baskets, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

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

⚠ Quadratic Growth

Space Complexity

O(n)

Boolean array to track which baskets are used

⚡ Linearithmic Space

23.0K Views

Medium Frequency

~25 min Avg. Time

890 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 - Linear Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler