**PriorityQueue**

- Related with greedy algorithm

- Use minQueue to get kth max, maxQueue to get kth min

- merge sort with PQ

Misc

- Remove is O(n)

**LeetCode 414 - Third Maximum Number**

- Use PriorityQueue with HashSet to check duplicate

https://discuss.leetcode.com/topic/63086/java-priorityqueue-o-n-o-1

- TreeSet (not PQ as need call contains)

set.add(num);

if(set.size() > 3) {set.remove(set.first());}

- Maitain state: first, second, third

**LeetCode 502 - IPO**

**find a project with max profit and within current capital capability**

- 2 PriorityQueue

```
PriorityQueue<int[]> pqCap = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
PriorityQueue<int[]> pqPro = new PriorityQueue<>((a, b) -> (b[1] - a[1]));
for (int i = 0; i < k; i++) {
while (!pqCap.isEmpty() && pqCap.peek()[0] <= W) {
pqPro.add(pqCap.poll());
}
W += pqPro.poll()[1];
}
```

LeetCode 632 - Smallest Range

LeetCode 630 - Course Schedule III

There are n different online courses numbered from 1 to n. Each course has some duration(course length) t and closed on dthday. A course should be taken continuously for t days and must be finished before or on the dth day. You will start at the 1st day.

Given n online courses represented by pairs (t,d), your task is to find the maximal number of courses that can be taken.

```
public int scheduleCourse(int[][] courses) {
Arrays.sort(courses,(a,b)->a[1]-b[1]); //Sort the courses by their deadlines (Greedy! We have to deal with courses with early deadlines first)
PriorityQueue
``` pq=new PriorityQueue<>((a,b)->b-a);
int time=0;
for (int[] c:courses)
{
time+=c[0]; // add current course to a priority queue
pq.add(c[0]);
if (time>c[1]) time-=pq.poll(); //If time exceeds, drop the previous course which costs the most time. (That must be the best choice!)
}
return pq.size();
}

LeetCode 378 - Kth Smallest Element in a Sorted Matrix

- Bisection O(nlogm) while m = max - min

https://discuss.leetcode.com/topic/52868/java-heap-klog-k

```
public int kthSmallest(final int[][] matrix, int k) {
int c = 0;
PriorityQueue<int[]> queue = new PriorityQueue<>(
k, (o1, o2) -> matrix[o1[0]][o1[1]] - matrix[o2[0]][o2[1]]);
queue.offer(new int[] {0, 0});
while (true) {
int[] pair = queue.poll();
if (++c == k) {
return matrix[pair[0]][pair[1]];
}
if (pair[0] == 0 && pair[1] + 1 < matrix[0].length) {
queue.offer(new int[] {0, pair[1] + 1});
}
if (pair[0] + 1 < matrix.length) {
queue.offer(new int[] {pair[0] + 1, pair[1]});
}
}
```

LeetCode 373 - Find K Pairs with Smallest SumsYou are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.

Define a pair (u,v) which consists of one element from the first array and one element from the second array.

Find the k pairs (u1,v1),(u2,v2) ...(uk,vk) with the smallest sums.

**Find elements more than K times**

Given m sorted lists, find out the elements more than k times. If an element appear more than once in a list, count it only once.

- Use PriorityQueue instead of HashMap to save space

**POJ 4302 Holedox Eating**

- 2 PriorityQueue

**LeetCode 621 - Task Scheduler**

- Use Priority Queue

- Calculating Idle slots

**LeetCode 358 - Rearrange String k Distance Apart**

Rearrange Characters in String With No Adjacent Duplicate Characters

**LeetCode 632 - Smallest Range**

You have k lists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of the klists.

- Merge k sorted list

LeetCode 407 - Trapping Rain Water II

**Queue**

**Double Monotonic Queue**

Deque

Deque

**LeetCode 239 - Sliding Window Maximum**

- Store index instead of the value

- Only keep promising elements in the deque

**LeetCode 102 - Binary Tree Level Order Traversal**

queue.offer(root);

while(!queue.isEmpty()){

for(int i=0; i

LeetCode 127 - Word Ladder I

- BFS, Two-end BFS

Deque

queue.offer(start);

Set

LeetCode 111 - Minimum Depth of Binary Tree

Interval tree

http://www.davismol.net/2016/02/07/data-structures-augmented-interval-tree-to-search-for-interval-overlapping/

- augmented self-balancing bst: low, high, max

- logn: add/Remove(interval), overlapping(x)

Google – Toggle Problem

https://reeestart.wordpress.com/2016/06/24/google-toggle-problem/

**Using Multiple Data Structures**

**Google – Manager Peer Problem**

- Tree + Hash Table

Map

private class TNode {

int val;

TNode parent;

List

}

Design a data structure that supports insert, delete, search and getRandom in constant time

//A hash where keys are array elements and vlaues are ndexes in arr[]

HashMap

ArrayList

LeetCode 432 - All O`one Data Structure

Inc(Key), Dec(Key), GetMaxKey(), GetMinKey()

```
private Bucket head;
private Bucket tail;
// for accessing a specific Bucket among the Bucket list in O(1) time
private Map
``` countBucketMap;
// keep track of count of keys
private Map keyCountMap; or the value can be Bucket
// each Bucket contains all the keys with the same count
private class Bucket {
int count;
Set keySet;
Bucket next, prev;
}

LeetCode - LRU Cache

isTaken(String phone) takeNumber(String phone) giveMeANumber()

- Trie

Stock Ticker

Implementing Stack using priority queue.

- assign priority to the elements that are being pushed

* insert(key, value, timestamp)

* get(key, timestamp)

//> = =

HashMap> map = new HashMap<>();

Design a stack with operations on middle element

- push, pop

3) findMiddle() which will return middle element of the stack.

4) deleteMiddle() which will delete the middle element.

- Doubly Linked List

Min Stack

```
private int capacity;
private HashMap
``` hs = new HashMap();
private Node head = new Node(-1, -1);
private Node tail = new Node(-1, -1);
public LRUCache(int capacity) {
this.capacity = capacity;
tail.prev = head;
head.next = tail;
}
public int get(int key) {
if( !hs.containsKey(key)) {
return -1;
}
// remove current
Node current = hs.get(key);
current.prev.next = current.next;
current.next.prev = current.prev;
// move current to tail
move_to_tail(current);
return hs.get(key).value;
}
public void set(int key, int value) {
// this internal `get` method will update the key's position in the linked list.
if (get(key) != -1) {
hs.get(key).value = value;
return;
}
if (hs.size() == capacity) {
hs.remove(head.next.key);
head.next = head.next.next;
head.next.prev = head;
}
Node insert = new Node(key, value);
hs.put(key, insert);
move_to_tail(insert);
}
private void move_to_tail(Node current) {
current.prev = tail.prev;
tail.prev = current;
current.prev.next = current;
current.next = tail;
}

LeetCode 460 - LFU Cache

when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.

- Doubly Linked List + HashMap

Design Phone Directorywhen there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.

- Doubly Linked List + HashMap

```
private Node head = null;
private int cap = 0;
private HashMap
``` valueHash = null;
private HashMap nodeHash = null;

isTaken(String phone) takeNumber(String phone) giveMeANumber()

- Trie

Stock Ticker

`void addOrUpdate(String stock, double price)`

add or update the price of a stock to the data structure.`List`

return the top k price stocks and their current prices.

**Sparse Matrix**Implementing Stack using priority queue.

- assign priority to the elements that are being pushed

**TimeTravelingHashTable*** insert(key, value, timestamp)

* get(key, timestamp)

//

HashMap

Design a stack with operations on middle element

- push, pop

3) findMiddle() which will return middle element of the stack.

4) deleteMiddle() which will delete the middle element.

- Doubly Linked List

Min Stack