aboutsummaryrefslogtreecommitdiff
path: root/kth_largest_element_stream.c
blob: f7ec953811aee73971ae99c846abc24e507f7b1d (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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
// 703. Kth Largest Element in a Stream
#include <limits.h>
#include <stdlib.h>
#include <string.h>

/*
 * design a class to find the k'th largest element in a stream. note that it is
 * the k'th largest element in the sorted order, not the k'th distinct element.
 * implement 'KthLargest' class:
 * - KthLargest(int k, int[] nums) initialises the objct with the integer 'k'
 * and the stream of integers 'nums' int add(int val) appends the integer 'val'
 * to the stream and returns the element representing the k'th largest stream
 * element
 */

typedef struct {
  int *min_heap;
  int size;
  int curr;
} KthLargest;

int cmp_func(const void *a, const void *b) { return *(int *)a - *(int *)b; }

KthLargest *kthLargestCreate(int k, int *nums, int nums_size) {
  if (nums_size)
    qsort(nums, nums_size, sizeof(int), cmp_func);
  KthLargest *res = malloc(sizeof(KthLargest));
  res->size = k;
  res->min_heap = malloc(k * sizeof(int));
  if (k <= nums_size) {
    memcpy(res->min_heap, &nums[nums_size - k], k * sizeof(int));
    res->curr = k;
  } else {
    for (int i = 0; i < k; i++) {
      if (i < nums_size)
        res->min_heap[i] = nums[i];
      else
        res->min_heap[i] = INT_MAX;
      res->curr = nums_size;
    }
  }
  return res;
}

void swap(int *a, int *b) {
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

int kthLargestAdd(KthLargest *obj, int val) {
  if (obj->curr < obj->size) {
    obj->min_heap[obj->curr] = val;
    int pos = obj->curr;
    obj->curr++;
    while (pos) {
      if (obj->min_heap[pos] < obj->min_heap[(pos - 1) / 2]) {
        swap(&obj->min_heap[pos], &obj->min_heap[(pos - 1) / 2]);
        pos = (pos - 1) / 2;
      } else
        break;
    }
    if (obj->curr == obj->size)
      return obj->min_heap[0];
    else
      return -1;
  } else if (obj->curr == obj->size && val > obj->min_heap[0]) {
    obj->min_heap[0] = val;
    int idx = 0;
    while (2 * idx + 1 < obj->size && 2 * idx + 2 < obj->size) {
      if (obj->min_heap[2 * idx + 1] <= obj->min_heap[2 * idx + 1]) {
        if (obj->min_heap[idx] > obj->min_heap[2 * idx + 1]) {
          swap(&obj->min_heap[idx], &obj->min_heap[2 * idx + 1]);
          idx = 2 * idx + 1;
        } else
          break;
      } else {
        if (obj->min_heap[idx] > obj->min_heap[2 * idx + 2]) {
          swap(&obj->min_heap[idx], &obj->min_heap[2 * idx + 2]);
          idx = 2 * idx + 2;
        } else
          break;
      }
    }
    if (2 * idx + 1 < obj->size) {
      if (obj->min_heap[idx] > obj->min_heap[2 * idx + 1]) {
        swap(&obj->min_heap[idx], &obj->min_heap[2 * idx + 1]);
        idx = 2 * idx + 1;
      }
    }
  }
  return obj->min_heap[0];
}

void kthLargestFree(KthLargest *obj) {
  free(obj->min_heap);
  free(obj);
}

int main() {
  int k, nums[] = {}, nums_size, val;
  KthLargest *obj = kthLargestCreate(k, nums, nums_size);
  int param_1 = kthLargestAdd(obj, val);
  kthLargestFree(obj);
}