Solution

Method 1 – Square Root Decomposition with Block Optimization

Intuition

This problem extends the concept from Fruits Into Baskets II, but with significantly larger input constraints that make direct simulation inefficient. The key insight is to use square root decomposition to optimize the search process while maintaining the leftmost placement requirement.

We partition the baskets array into √n blocks of approximately equal size. Within each block, we maintain sorted order and track the maximum capacity. This allows us to quickly skip entire blocks that cannot accommodate a fruit, while still preserving the leftmost placement property within viable blocks.

Approach

Block Partitioning: Divide the baskets array into √n blocks, each containing approximately √n baskets
Block Preprocessing: For each block, store baskets as (capacity, original_index) pairs and sort them by capacity for efficient searching
Fruit Placement Process: For each fruit in sequence:
- Iterate through blocks from left to right
- Block Filtering: If the maximum capacity in a block is less than the fruit's requirement, skip the entire block
- Intra-block Search: Within a viable block, find the basket with smallest original index that can accommodate the fruit
- Basket Removal: Remove the selected basket from its block and continue to the next fruit
- Unplaced Counting: If no suitable basket is found across all blocks, increment the unplaced counter
Return the total count of unplaced fruits

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int numOfUnplacedFruits(vector<int>& fruits, vector<int>& baskets) {\n        int n = fruits.size();\n        int block_size = (int)ceil(sqrt(n));\n        \n        vector<vector<pair<int, int>>> blocks(block_size);\n        \n        // Distribute baskets into blocks\n        for (int i = 0; i < n; i++) {\n            int block_idx = i / block_size;\n            blocks[block_idx].push_back({baskets[i], i});\n        }\n        \n        // Sort each block by capacity\n        for (auto& block : blocks) {\n            sort(block.begin(), block.end());\n        }\n        \n        int unplaced_count = 0;\n        \n        for (int fruit_quantity : fruits) {\n            bool placed = false;\n            \n            for (auto& block : blocks) {\n                if (block.empty()) continue;\n                \n                // Skip if max capacity in block is insufficient\n                if (block.back().first < fruit_quantity) continue;\n                \n                // Find leftmost viable basket\n                int best_idx = -1;\n                int min_original_idx = INT_MAX;\n                \n                for (int i = 0; i < block.size(); i++) {\n                    if (block[i].first >= fruit_quantity && block[i].second < min_original_idx) {\n                        min_original_idx = block[i].second;\n                        best_idx = i;\n                    }\n                }\n                \n                if (best_idx != -1) {\n                    block.erase(block.begin() + best_idx);\n                    placed = true;\n                    break;\n                }\n            }\n            \n            if (!placed) unplaced_count++;\n        }\n        \n        return unplaced_count;\n    }\n};","lang":"cpp"},{"language":"Go","code":"import (\n    \"math\"\n)\n\nfunc numOfUnplacedFruits(fruits []int, baskets []int) int {\n    n := len(fruits)\n    blockSize := in

Related Tags