In a row of trees, the i-th tree produces fruit with type tree[i].
You start at any tree of your choice, then repeatedly perform the following steps:
- Add one piece of fruit from this tree to your baskets. If you cannot, stop.
- Move to the next tree to the right of the current tree. If there is no tree to the right, stop.
Note that you do not have any choice after the initial choice of starting tree: you must perform step 1, then step 2, then back to step 1, then step 2, and so on until you stop.
You have two baskets, and each basket can carry any quantity of fruit, but you want each basket to only carry one type of fruit each.
What is the total amount of fruit you can collect with this procedure?
Example 1:
Input:
[1,2,1]
Output:
3
Explanation:
We can collect [1,2,1].
Example 2:
Input:
[0,1,2,2]
Output:
3
Explanation:
We can collect [1,2,2]. If we started at the first tree, we would only collect [0, 1].
Example 3:
Input:
[1,2,3,2,2]
Output:
4
Explanation:
We can collect [2,3,2,2]. If we started at the first tree, we would only collect [1, 2].
Example 4:
Input:
[3,3,3,1,2,1,1,2,3,3,4]
Output:
5
Explanation:
We can collect [1,2,1,1,2]. If we started at the first tree or the eighth tree, we would only collect 4 fruits.
Note:
1 <= tree.length <= 400000 <= tree[i] < tree.length
First Draft.
Code is accepted, but the quality is a JOKE.
class Solution {
public int totalFruit(int[] tree) {
if (tree.length <= 2){
return tree.length;
}
int max = 2;
int cur_max = 2;
int a = tree[0];
int b = tree[1];
int a_last_index = 0;
Integer b_last_index = null;
boolean a_is_eldest = true;
// get the second <Unique> number
for(int i = 1; i < tree.length; i ++){
if (tree[i] != a){
b = tree[i];
b_last_index = i;
break;
} else {
// And we have to update last index of a as well
cur_max ++;
a_last_index = i;
a_is_eldest = false;
}
}
// update max here
max = Math.max(max, cur_max);
// if only single unique number in the array...
if (b_last_index == null){
return tree.length;
}
// Scan from the right of the second unique number
for(int i = b_last_index+1; i < tree.length; i ++){
int cur = tree[i];
if(cur == a){
cur_max ++;
a_last_index = i;
a_is_eldest = false;
} else if (cur == b){
cur_max ++;
b_last_index = i;
a_is_eldest = true;
} else {
// Third unique number appeared!
// Remove eldest, and reduce current max to the last occurance of the number to be removed.
if(a_is_eldest){
cur_max = i - a_last_index;
a = cur;
a_last_index = i;
a_is_eldest = false;
} else {
cur_max = i - b_last_index;
b = cur;
b_last_index = i;
a_is_eldest = true;
}
}
max = Math.max(max, cur_max);
}
return max;
}
}
Code after refactoring:
class Solution {
public int totalFruit(int[] tree) {
if (tree.length <= 2){
return tree.length;
}
int max = 2;
int cur_max = 1;
int a = tree[0];
int a_last_index = 0;
Integer b = null;
Integer b_last_index = null;
boolean a_is_eldest = true;
for(int i = 1; i < tree.length; i ++){
int cur = tree[i];
if(cur == a){
cur_max ++;
a_last_index = i;
a_is_eldest = false;
} else if (b == null || cur == b) {
if(b == null){
b = cur;
}
cur_max ++;
b_last_index = i;
a_is_eldest = true;
} else {
if(a_is_eldest){
cur_max = i - a_last_index;
a = cur;
a_last_index = i;
a_is_eldest = false;
} else {
cur_max = i - b_last_index;
b = cur;
b_last_index = i;
a_is_eldest = true;
}
}
max = Math.max(max, cur_max);
}
return max;
}
}
There could be more things for refactoring, putting that aside, can we use any data structure?
Maybe LinkedHashMap<Type, LastSeenIndex> in access order mode? it’s an overkill for ‘collecting two types’, but could be useful for 3 or more types.
Starting by copy & paste from LRUCache. I added a variable to save the value of the most recent removed entry. The value of it is updated before the eldest entry is removed.
The modified LRUCache
class LRUCache extends LinkedHashMap<Integer, Integer>{
private int capacity;
// Save the latest index of the recent removed item.
int index_removed = 0;
public LRUCache(int capacity) {
super(capacity, 0.75F, true);
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
// If the eldest has to be removed, save it's value (most recent index)
if(size() > capacity){
index_removed = eldest.getValue();
}
return size() > capacity;
}
}
Then, update the main function… and combine them
class Solution {
public static final int TYPES_ALLOWED = 2;
public int totalFruit(int[] tree) {
if (tree.length <= TYPES_ALLOWED){
return tree.length;
}
int cur_max = 1;
int max = 1;
// For a follow-up of more than 2 types is allowed.. just change the number here
LRUCache map = new LRUCache(TYPES_ALLOWED);
map.put(tree[0], 0);
for(int i = 1; i < tree.length; i ++){
int cur = tree[i];
if (map.get(cur) != -1 || map.size() < 2){
cur_max ++;
map.put(cur, i);
} else {
map.put(cur, i);
cur_max = i - map.index_removed;
}
max = Math.max(max, cur_max);
}
return max;
}
}
class LRUCache extends LinkedHashMap<Integer, Integer>{
private int capacity;
int index_removed = 0;
public LRUCache(int capacity) {
super(capacity, 0.75F, true);
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
if(size() > capacity){
index_removed = eldest.getValue();
}
return size() > capacity;
}
}
Time complexity. O(n). basically going through all elements once (n), times LRUCache O(1).
This is basically a sliding window solution, while the Map is used for maintaining the valid window status.
Well, we can also use other Collections, giving the accepted types is two. The search and insertion time have to be counted after the number of accepted types is increased. So a Hash* will have a better performance.
Can we use a LinkedHashSet? Yes, then giving the type to be removed, find the closest index before the current index.