703. Kth Largest Element in a Stream (Easy)

https://leetcode.com/problems/kth-largest-element-in-a-stream/

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Your `KthLargest` class will have a constructor which accepts an integer `k` and an integer array `nums`, which contains initial elements from the stream. For each call to the method `KthLargest.add`, return the element representing the kth largest element in the stream.

Example:

```int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
```

Note:
You may assume that `nums`' length ≥ `k-1` and `k` ≥ 1.

Solutions

1.

``````class KthLargest {
private int k;
private Queue<Integer> pq = new PriorityQueue<>();

public KthLargest(int k, int[] nums) {
this.k = k;

for (int num : nums) {
}
}

pq.offer(val);

// drop all that after the kth element
if (pq.size() > k) {
pq.poll();
}

return pq.peek();
}
}
``````

2.

``````class KthLargest {
// This solution is too trivial and you will make mistakes.
// The preferred choice is to use array or list instead of linked list.
// It's easy to come across setback due to the complexity of linked list.
// It is strongly advised to make a draft before get down to coding, or the
// bugs will drive you crazy.

class Node {
int val = 0;
Node prev = null;
Node next = null;

public Node(int val) {
this.val = val;
}
}

int k = 0;
int size = 0;

Node kthNode = null;

public KthLargest(int k, int[] nums) {
this.k = k;

for (int i = 0; i < nums.length; i++) {
}
}

Node newP = new Node(val);

int count = 1;
while(pointer.next != null) {
if (pointer.next.val < val) {
break;
}

count++;
pointer = pointer.next;
}

if (pointer.next != null) {
pointer.next.prev = newP;
}

newP.next = pointer.next;
newP.prev = pointer;
pointer.next = newP;

size++;
// If the length of list is not as long as k, move kthNode forward
if (size <= k && kthNode.next != null) {
kthNode = kthNode.next;
}

// If the insert slot is in front of or just in kth position, move
// back the pointer of kthNode

// Be aware that only list length > k, you can move back.
if (size > k && count <= k) {
kthNode = kthNode.prev;
}

return kthNode.val;
}
}
``````