## The fruits in basket problem

You have a list of integers which are fruits.

Each int value is a fruit type

You have two baskets

Each baskets can ONLY contain ONE type of fruit.

What is the max fruits you can collect?

You can only go left to right on the list.

e.g [strawberry, **apple, mango, apple**] -> answer is 3.

[pear, **apple, orange, orange, apple**, pear, apple, orange, mango, pear ] -> answer is 4

**Solution:**

import java.util.HashMap; import java.util.Iterator; import java.util.Stack; public class Solution { HashMap<Integer, Integer> basket1 = new HashMap(); HashMap<Integer, Integer> basket2 = new HashMap(); Stack<HashMap> lastbucket = new Stack(); int maxFruits = 0; public int totalFruit(int[] tree) { for(int i=0;i<tree.length;i++){ int f = tree[i]; if(basket1.containsKey(f)|| (basket1.size()==0&&!basket2.containsKey(f))){ Integer count = basket1.get(f); if(count==null){count=0;} basket1.put(f,count+1); lastbucket.push(basket1); }else if(basket2.containsKey(f)|| (basket2.size()==0&&!basket1.containsKey(f))){ Integer count = basket2.get(f); if(count==null){count=0;} basket2.put(f,count+1); lastbucket.push(basket2); }else{ if(fruitCount(basket1)+fruitCount(basket2)>maxFruits){ maxFruits = fruitCount(basket1)+fruitCount(basket2); } if(lastbucket.peek()==basket1){ HashMap tmp = lastbucket.pop(); int ct=0; while(tmp==basket1){ ct = ct+1; basket1.put(basket1.keySet().iterator().next(),ct); if(lastbucket.size()>0){ tmp = lastbucket.pop(); }else{ break; } } lastbucket.push(basket1); basket2.clear(); basket2.put(f,1); lastbucket.push(basket2); }else{ HashMap tmp = lastbucket.pop(); int ct=0; while(tmp==basket2){ ct = ct+1; basket2.put(basket2.keySet().iterator().next(),ct); if(lastbucket.size()>0){ tmp = lastbucket.pop(); }else{ break; } } lastbucket.push(basket2); basket1.clear(); basket1.put(f,1); lastbucket.push(basket1); } } } if(fruitCount(basket1)+fruitCount(basket2)>maxFruits){ maxFruits = fruitCount(basket1)+fruitCount(basket2); } return maxFruits; } private int fruitCount(HashMap<Integer,Integer> basket){ Iterator<Integer> it = basket.keySet().iterator(); while(it.hasNext()){ Integer key = it.next(); return basket.get(key); } return 0; } }

Advertisements