aboutsummaryrefslogtreecommitdiff
path: root/fruit_into_baskets.c
blob: 17316e582193c8fa280f58bdf62d9ec0c2198987 (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
// 904. Fruit Into Baskets
#include <stdio.h>
#include <stdlib.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 n = fruitsSize, type = 0, left = 0, right = 0;
  int *hash = calloc(n, sizeof(int));
  while (right < fruitsSize) {
    if (hash[fruits[right]] == 0)
      type++;
    hash[fruits[right]]++;
    right++;
    if (type > 2) {
      if (hash[fruits[left]] == 1)
        type--;
      hash[fruits[left]]--;
      left++;
    }
  }
  free(hash);
  return right - left;
}

int main() {
  int fruits1[] = {1, 2, 1}, fs1 = 3;
  int fruits2[] = {0, 1, 2, 2}, fs2 = 4;
  int fruits3[] = {1, 2, 3, 2, 2}, fs3 = 5;
  printf("%d\n", totalFruit(fruits1, fs1)); // expect: 3
  printf("%d\n", totalFruit(fruits2, fs2)); // expect: 3
  printf("%d\n", totalFruit(fruits3, fs3)); // expect: 4
}