aboutsummaryrefslogtreecommitdiff
path: root/fruit_into_baskets.c
blob: e57c1a78d35e41c23ac421eb5e057866a22d6951 (plain)
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
// 904. Fruit Into Baskets
#include "leetcode.h"

/*
 * you are visiting a farm that has a single row of fruit trees arranged from
 * left t oright. the trees are represented by an integer array 'fruits' where
 * 'fruits[i]' is the type of fruit the i'th tree produces. you want to collect
 * as much fruit as possible. however, the owner has some strict rules that you
 * must follow: you can only have two baskets and each can only hoold a single
 * type of fruit (unlimited quantity). starting from any tree, you must pick
 * exacty one fruit from every tree while moving to the right. once you reach a
 * tree with fruit that cannot fit in your baskets, you must stop. given the int
 * array 'fruits', return the maximum number of fruits you can pick
 */

int totalFruit(int *fruits, int fruitsSize) {
  int max = 0, p1 = 0, p2 = 0, f1 = -1, f2 = -1, i, j = 0;
  for (i = 0; i < fruitsSize; ++i) {
    if (fruits[i] == f1)
      ++p1;
    else if (f1 < 0) {
      f1 = fruits[i];
      p1 = 1;
    } else {
      f2 = fruits[i];
      p2 = 1;
      break;
    }
  }
  while (++i < fruitsSize) {
    if (fruits[i] == f1)
      ++p1;
    else if (fruits[i] == f2)
      ++p2;
    else {
      if (i - j > max)
        max = i - j;
      while (p1 > 0 && p2 > 0) {
        if (fruits[j] == f1)
          --p1;
        else
          --p2;
        ++j;
      }
      if (!p1) {
        f1 = fruits[i];
        p1 = 1;
      } else {
        f2 = fruits[i];
        p2 = 1;
      }
    }
  }
  if (fruitsSize - j > max)
    return fruitsSize - j;
  return max;
}

int main() {
  int f1[] = {1, 2, 1}, f2[] = {0, 1, 2, 2}, f3[] = {1, 2, 3, 2, 2};
  printf("%d\n", totalFruit(f1, ARRAY_SIZE(f1))); // expect: 3
  printf("%d\n", totalFruit(f2, ARRAY_SIZE(f2))); // expect: 3
  printf("%d\n", totalFruit(f3, ARRAY_SIZE(f3))); // expect: 4
}