FilesExpand file tree

 master

/

FruitIntoBaskets.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

87 lines (82 loc) · 2.61 KB

 master

/

FruitIntoBaskets.java

Copy path

Top

File metadata and controls

• Code
• Blame

87 lines (82 loc) · 2.61 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

package array;

import java.util.Stack;

/**

* Created by gouthamvidyapradhan on 02/03/2019 In a row of trees, the i-th tree produces fruit with

* type tree[i].

*

* <p>You start at any tree of your choice, then repeatedly perform the following steps:

*

* <p>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.

*

* <p>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.

*

* <p>What is the total amount of fruit you can collect with this procedure?

*

* <p>Example 1:

*

* <p>Input: [1,2,1] Output: 3 Explanation: We can collect [1,2,1]. Example 2:

*

* <p>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:

*

* <p>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:

*

* <p>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.

*

* <p>Note:

*

* <p>1 <= tree.length <= 40000 0 <= tree[i] < tree.length

*/

public class FruitIntoBaskets {

private int count = 0;

private int max = 0;

/**

* Main method

*

* @param args

*/

public static void main(String[] args) {

int[] trees = {1, 0, 3, 4, 3};

System.out.println(new FruitIntoBaskets().totalFruit(trees));

}

public int totalFruit(int[] tree) {

int t1 = -1, t2 = -1;

Stack<Integer> stack = new Stack<>();

for (int i : tree) {

if (i == t1 || i == t2) {

countAndMax(stack, i);

} else {

if (t1 == -1) {

t1 = i;

countAndMax(stack, i);

} else if (t2 == -1) {

t2 = i;

countAndMax(stack, i);

} else {

Stack<Integer> temp = new Stack<>();

count = 0;

t1 = stack.pop();

countAndMax(temp, t1);

while (!stack.isEmpty() && stack.peek() == t1) {

countAndMax(temp, stack.pop());

}

t2 = i;

stack = temp;

countAndMax(stack, i);

}

}

}

return max;

}

private void countAndMax(Stack<Integer> stack, int i) {

count++;

stack.push(i);

max = Math.max(max, count);

}

}