C# || Fruit Into Baskets – How To Find The Maximum Number Of Fruits Using C#
The following is a module with functions which demonstrates how to find the maximum number of fruits using C#.
1. Total Fruit – Problem Statement
You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array fruits where fruits[i] is the type of fruit the ith tree produces.
You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:
- You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold.
- Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets.
- Once you reach a tree with fruit that cannot fit in your baskets, you must stop.
Given the integer array fruits, return the maximum number of fruits you can pick.
Example 1:
Input: fruits = [1,2,1]
Output: 3
Explanation: We can pick from all 3 trees.
Example 2:
Input: fruits = [0,1,2,2]
Output: 3
Explanation: We can pick from trees [1,2,2].
If we had started at the first tree, we would only pick from trees [0,1].
Example 3:
Input: fruits = [1,2,3,2,2]
Output: 4
Explanation: We can pick from trees [2,3,2,2].
If we had started at the first tree, we would only pick from trees [1,2].
2. Total Fruit – Solution
The following is a solution which demonstrates how to find the maximum number of fruits.
|
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 |
// ============================================================================ // Author: Kenneth Perkins // Date: Jul 28, 2023 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to find the maximum number of fruits // ============================================================================ public class Solution { public int TotalFruit(int[] fruits) { // We use a hash map 'basket' to store the number of each type of fruit. var basket = new Dictionary<int, int>(); int left = 0; int maxPicked = 0; // Add fruit from the right index (right) of the window. for (int right = 0; right < fruits.Length; ++right) { basket[fruits[right]] = basket.GetValueOrDefault(fruits[right], 0) + 1; // If the current window has more than 2 types of fruit, // we remove fruit from the left index (left) of the window, // until the window has only 2 types of fruit. while (basket.Count > 2) { basket[fruits[left]] = basket[fruits[left]] - 1; if (basket[fruits[left]] == 0) { basket.Remove(fruits[left]); } ++left; } // Update maxPicked. maxPicked = Math.Max(maxPicked, right - left + 1); } // Return maxPicked as the maximum number of fruits we can collect. return maxPicked; } }// http://programmingnotes.org/ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
Once compiled, you should get this as your output for the example cases:
3
3
4
Hi, I'm a software engineer. I write articles about programming and design in my spare time.
Leave a Reply