Three Sum - Leet Code Solution
Problem Statement Given an array nums of n integers, are there elements a, b, c…
July 10, 2019
Min Priority Queue is a data structure which manage a list of keys(values). And, gives priority to element with minimum value.
It supports following operations:
(Heap data structure)[/coding-interview/what-is-heap-data-structure/] can be used for its implementation.
Lets see each one of them:
public class MinPriorityQueue {
private int[] heap;
private int maxSize;
private int heapSize;
public MinPriorityQueue(int maxSize) {
this.maxSize = maxSize;
this.heap = new int[maxSize];
this.heapSize = 0;
}
@Override
public String toString() {
return ArrayUtils.toString(this.heap, this.heapSize);
}
private int getLeftChild(int index) { return 2*index + 1;}
private int getRightChild(int index) { return 2*index + 2;}
private int getParent(int index) {
if (index == 0) {
return -1;
}
return (index-1)/2;
}
private void minHeapify(int index) {
int smallest = index;
int l = this.getLeftChild(index);
int r = this.getRightChild(index);
if (l < this.heapSize && this.heap[l] < this.heap[index]) {
smallest = l;
}
if (r < this.heapSize && this.heap[r] < this.heap[smallest]) {
smallest = r;
}
if (smallest != index) {
ArrayUtils.swap(this.heap, smallest, index);
this.minHeapify(smallest);
}
}
/**
* Get the min element, do not delete
*/
public int getMin() throws Exception {
if (this.heapSize == 0) {
throw new Exception("Heap underflow");
}
return this.heap[0];
}
/**
* Get the min, and delete from heap
* Runs in O(log n)
*/
public int extractMin() throws Exception {
if (this.heapSize == 0) {
throw new Exception("Heap underflow");
}
int ret = this.heap[0];
this.heap[0] = this.heap[this.heapSize-1];
this.heapSize --;
this.minHeapify(0);
return ret;
}
/**
* Set the value at index specified to new value specified
*/
public void decrement(int index, int newValue) throws Exception {
if (index > this.heapSize-1) {
throw new Exception("Overflow");
}
this.heap[index] = newValue;
while (index > 0 && this.heap[index] < this.heap[this.getParent(index)]) {
ArrayUtils.swap(this.heap, index, this.getParent(index));
index = this.getParent(index);
}
}
public void insert(int val) throws Exception {
if (this.heapSize >= this.maxSize) {
throw new Exception("Overflow");
}
this.heapSize ++;
this.heap[this.heapSize-1] = Integer.MAX_VALUE;
this.decrement(this.heapSize-1, val);
}
public static void main(String[] args) throws Exception {
MinPriorityQueue q = new MinPriorityQueue(10);
//fresh state
System.out.println(q);
//lets insert 5 elements
q.insert(10); q.insert(5); q.insert(4); q.insert(6); q.insert(20);
System.out.println(q);
System.out.println("Min: " + q.getMin());
System.out.println("Extracting min: " + q.extractMin());
System.out.println("State: " + q);
System.out.println("Decrementing index-2 to 4");
q.decrement(2, 4);
System.out.println("State: " + q);
System.out.println("Extracting min: " + q.extractMin());
System.out.println("State: " + q);
System.out.println("Extracting min: " + q.extractMin());
System.out.println("State: " + q);
}
}
To know about basic Heap data structure, and its heapify operation. See: (Heap data structure)[/coding-interview/what-is-heap-data-structure/] Its an important data structure for interview purpose.
Runtime complexity is O(1) Since we are maintaining min heap. The minimum value is always at 0th index. Just return it.
Runtime complexity is O(log n)
Runtime complexity is O(log n)
Runtime complexity is O(log n)
Problem Statement Given an array nums of n integers, are there elements a, b, c…
Introduction You are given an array of integers with size N, and a number K…
Problem Statement You are given an array of integers. And, you have find the…
Problem Statement Maximum Length of Subarray With Positive Product. Given an…
Problem Statement Given a signed integer, reverse digits of an integer. Return…
** Inversion There is an array(a) and two indexes i and j. Inversion is the…
In this post, we will see some of the frequently used concepts/vocabulary in…
System design interview is pretty common these days, specially if you are having…
Introduction You are given an array of integers with size N, and a number K…
Graph Topological Sorting This is a well known problem in graph world…
Problem Statement Given a Binary tree, print out nodes in level order traversal…
Problem Statement Given an array nums of n integers and an integer target, are…