aboutsummaryrefslogtreecommitdiff
path: root/longest_uploaded_prefix.c
blob: 25a2b4dfa2a71bc0f0aa5c35a5cf7b3f1397fe7d (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
// 2424. Longest Uploaded Prefix
#include "leetcode.h"

/*
 * given a string of 'n' videos, each represented by a distinct number from 1 to
 * n that you need to upload to a server. you need to implement a data structure
 * that calculates the length of the longest uploaded prefix at various points
 * in the upload process. we consider i to be uploaded prefix if all videos in
 * the range 1 to i inclusive have been uploaded to the server. the longest
 * uploaded prefix is the maximum value of 'i' that satisfies this definition.
 */

typedef struct {
  bool *data;
  int size;
  int longest;
} LUPrefix;

LUPrefix *lUPrefixCreate(int n) {
  LUPrefix *res = malloc(sizeof(LUPrefix));
  res->data = calloc(n + 1, sizeof(bool));
  res->size = n;
  res->longest = 0;
  return res;
}

void lUPrefixUpload(LUPrefix *obj, int video) {
  obj->data[video] = 1;
  if (obj->data[1]) {
    int i = obj->longest + 1;
    for (i = obj->longest + 1; i <= obj->size; i++)
      if (!obj->data[i])
        break;
    obj->longest = i - 1;
  }
}

int lUPrefixLongest(LUPrefix *obj) { return obj->longest; }

void lUPrefixFree(LUPrefix *obj) {
  free(obj->data);
  free(obj);
}

/**
 * Your LUPrefix struct will be instantiated and called as such:
 * LUPrefix* obj = lUPrefixCreate(n);
 * lUPrefixUpload(obj, video);

 * int param_2 = lUPrefixLongest(obj);

 * lUPrefixFree(obj);
*/

int main() {
  LUPrefix *obj = lUPrefixCreate(4);
  lUPrefixUpload(obj, 3);
  printf("%d\n", lUPrefixLongest(obj)); // expect: 0
  lUPrefixUpload(obj, 1);
  printf("%d\n", lUPrefixLongest(obj)); // expect: 1
  lUPrefixUpload(obj, 2);
  printf("%d\n", lUPrefixLongest(obj)); // expect: 3
  lUPrefixFree(obj);
}