3477. Fruits Into Baskets II
Approach
Greedy; sort baskets; for each fruit find smallest capable basket using binary search.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Binary search reduces search space by half each step, giving O(log n) time. Beyond sorted arrays, apply it on the answer space ("binary search on result") when you can define a monotonic predicate — e.g., "can we achieve X with k resources?"
The sliding window technique maintains a dynamic sub-array (or substring) of interest, expanding the right boundary and shrinking the left boundary based on a constraint. It reduces O(n²) substring enumeration to O(n). Track state (frequency map, sum, distinct count) incrementally.
// Approach: Greedy; sort baskets; for each fruit find smallest capable basket using binary search.
// Time: O(n log n) Space: O(1)
public class Solution
{
public int NumOfUnplacedFruits(int[] fruits, int[] baskets)
{
int n = fruits.Length; // Number of fruits
bool[] visited = new bool[n]; // Array to track used baskets
int unplacedFruits = n; // Initialize all fruits as unplaced
// Loop through each fruit
foreach (int fruit in fruits)
{
// Try to place each fruit in an available basket
for (int i = 0; i < n; ++i)
{
// Check if the current basket can hold the fruit
// and if it hasn't been used yet
if (baskets[i] >= fruit && !visited[i])
{
visited[i] = true; // Mark the basket as used
--unplacedFruits; // Decrease count of unplaced fruits
break; // Move to the next fruit
}
}
}
return unplacedFruits; // Return the count of unplaced fruits
}
}