Priority Queue problems

A priority queue a data structure that keeps things in order of priority. The question is how is it different from the monotonic queue we discussed earlier. The difference is in the time complexity and applicability. The time complexity to find insert an element in the priority queue is O(logn), whereas in monotonic queues it is O(n). On the point of applicability, priority queue orders the entire input set, whereas monotonic queues maintain only partial input set in a particular order, and whenever an order is violated, we remove elements from the monotonic queues.

Before we do in detail of priority queues, please refresh fundamentals of heaps.

A priority queue is a collection in which items can be added at any time, but the only item that can be removed is the one with the highest priority.

It means that no matter what the insertion order of elements, removal will always give you the highest or lowest priority element. Internally, a priority queue is implemented as heaps. A heap is a data structure that as the following property:

A parent is greater than both its children (max heap) or a parent is less than both its children (min-heap)

How do I identify that it is a priority queue question? Almost all the time, the problem statement will have top-K, smallest-k, most frequent K in it. It means this problem has something to do with ranking and for ranking problems best data structure is a priority queue.

Priority queue in Java

If your choice of language in the interview is Java, you are in luck, because Java has this in build class called priority queue.

PriorityQueue pq = new PriorityQueue();

With the above instantiation, you can define a min priority queue, it means the smallest number will be polled first.

If you want to declare it in such a way that the largest number is polled first, all you have to do is pass a comparator. We can use an in-built function provided by Comparator.

PriorityQueue pq = new PriorityQueue(Comparator.reverseOrder());

What if you are intending to store objects in a priority queue, then this default will not work as they work on integers or long only. This is a point you must read on comparators in Java. You can pass a comparator to the constructor, it will be used by the queue to order objects accordingly.

 PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(
            (a, b) -> a.getValue().compareTo(b.getValue()) //Comparator
        );

You will find problems where you have to first find the frequency or priority of elements, we use HashMap to map element to its priority.

Use Map.Entry as an object to be stored in the queue. It helps us avoid creating new objects

Enough of theory, let’s get to the business, how can I solve problems using priority queues?

Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements. For example: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]

From the problem statement, it is evident that it is a ranking problem and we know the data structure to use. All we have to do is collect the respective frequency of elements. However, we have two ways to add elements to the priority queue. The first way is to create a map of element and frequency and add the whole map into the priority queue in decreasing order of frequency (max heap). Take out K element from the priority queue and that will be your K top elements.
The time complexity of the solution is O(n) to add all the elements in the heap, and then O(klogn) to take K elements out. Remember, each take-out incurs O(logn) complexity due to heapification process.

The second way is to add only K elements in the priority queue in min heap order. We keep the size of the queue to constant K, if it goes more, we just take our the top, which will be the minimum element. Once we have processed all the elements, elements in the queue will be top K elements
The time complexity of the solution is O(nlogk). Remember, each take-out and insert incurs O(logn) complexity due to heapification process.
Depending on the relationship between n and k, you can chose which method to use.

 public List<Integer> topKFrequent(int[] nums, int k) {
        
        
        Map<Integer, Integer> map = new HashMap<>();
        for(int i : nums){
            map.put(i, map.getOrDefault(i,0) + 1);
        }
        
        PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(
            (a, b) -> a.getValue().compareTo(b.getValue())
        );
        /* We chose the second method. apparently,
           it give better performance in leetcode
        */
        for(Map.Entry e : map.entrySet()){
            pq.offer(e);
            if(pq.size() > k){
                pq.poll();
            }
        }
        
        List<Integer> res = new ArrayList<>();
        pq.stream().forEach(e -> res.add(e.getKey()));
        
        return res;
        
    }

Top K Frequent Words

Given a non-empty list of words, return the k most frequent elements. The answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.

It is more or less the same problem as above, the only change is we have to add comparator to take care of alphabetical order.

    public List<String> topKFrequent(String[] words, int k) {
        
        Map<String, Integer> map = new HashMap<>();
       
        PriorityQueue<Map.Entry<String, Integer>> pq 
            = new PriorityQueue<>(
                       (a,b) -> a.getValue()==b.getValue() 
            ? b.getKey().compareTo(a.getKey()) : a.getValue()-b.getValue()
        );
        
        for(int i=0; i<words.length; i++){
            map.put(words[i], map.getOrDefault(words[i], 0) + 1);
        }
        
        for(Map.Entry<String, Integer> entry: map.entrySet()){
            pq.offer(entry);
            if(pq.size() > k){
                pq.poll();
            }
        }
        
        List<String> res = new LinkedList<>();
        while(!pq.isEmpty())
            res.add(0, pq.poll().getKey());
        
        return res;
    }

Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

class Solution {
    public int findKthLargest(int[] nums, int k) {
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int i = 0;
        for(; i<nums.length; i++){
            pq.add(nums[i]);
            if(pq.size() > k)
                pq.poll();
        }   
        
        return pq.peek();
    }
}

K Closest Points to Origin

We have a list of points on the plane. Find the K closest points to the origin (0, 0). (Here, the distance between two points on a plane is the Euclidean distance.)

    public int[][] kClosest(int[][] points, int K) {
        
        PriorityQueue<int[]> pq = new PriorityQueue<>(
                (a, b) -> ((a[0] - 0 ) * (a[0] - 0 )  + (a[1] - 0 ) * (a[1] - 0 )
                           - (b[0] - 0 ) * (b[0] - 0 ) - (b[1] - 0 ) * (b[1] - 0 ))
        );
            
        for(int i=0; i<points.length; i++){
            pq.add(new int[]{points[i][0], points[i][1]});
        }
            
        int [][] res = new int[K][2];
        for(int i=0; i<K && !pq.isEmpty(); i++){
            res[i] = pq.poll();
        }
            
        return res;
        
    }

Sort Characters By Frequency

Given a string, sort it in decreasing order based on the frequency of characters. For example, S = “tree”, the output should be “eert”

    public String frequencySort(String s) {
        
        PriorityQueue<Map.Entry<Character, Integer>> pq 
            = new PriorityQueue<>((a,b) -> b.getValue() - a.getValue());
        
        Map<Character, Integer> map = new HashMap<>();
       
        for(int i=0; i<s.length(); i++){
            map.put(s.charAt(i), 1 + map.getOrDefault(s.charAt(i), 0));
        }
        
        pq.addAll(map.entrySet());
       
        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            Map.Entry<Character, Integer> e = pq.poll();
            int n = (int)e.getValue();
            for (int i = 0; i < n;  i++) 
                sb.append(e.getKey());
        }
        return sb.toString();
    }

Find median in a stream of integer

This problem is covered in detail here: Median in a stream of integers.

 PriorityQueue<Integer> pqMin;
    PriorityQueue<Integer> pqMax;
    
    /** initialize your data structure here. */
    public MedianFinder() {
         pqMax = new PriorityQueue<>(Collections.reverseOrder());
         pqMin = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        /* If size of max heap, i.e left bunch of numbers is 
           greater than the min heap, right bunch of numbers,
           add the number in left bunch and take the Max and 
           add it to right bunch */
        if (pqMax.size() > pqMin.size()) {
            pqMax.offer(num);
            pqMin.offer(pqMax.poll());
        } else {
            //Do the opposite.
            pqMin.offer(num);
            pqMax.offer(pqMin.poll());
        }
        
    }
    
    public double findMedian() {
        /*If the size of two heaps is equal, 
           even number of integers, take the average of two
           middle elements */
        if(pqMin.size() == pqMax.size()){
            return (double)(pqMin.peek() + pqMax.peek())/2.0;
        }
        
        //Else return from the left bunch
        return (double)(pqMax.peek() * 1.0);
    }
}

Find K-th Smallest Pair Distance

Given an integer array, return the kth smallest distance among all the pairs. The distance of a pair (A, B) is defined as the absolute difference between A and B.

  private int findKth(int [] a, int k){
        PriorityQueue<Integer> pq = 
                 new PriorityQueue<>(Comparator.reverseOrder());
        
        for(int i=0; i<a.length; i++){
            for(int j=i+1; j<a.length; j++){
                int diff =  Math.abs(a[i]-a[j]);
                pq.offer(diff);
                
                if(pq.size() > k){
                    pq.poll();
                }
            }
        }
        return pq.peek();
    }    

The above solution works but due to the constraints, it may run out of memory and time. A better solution is based on a binary search and trial and error methods.

Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. For example:
Input:
[
1->4->5,
1->3->4,
2->6
] Output: 1->1->2->3->4->4->5->6

private ListNode mergeList(ListNode[] lists){
        
        if(lists.length == 0) return null;
        
        PriorityQueue<ListNode> pq = new PriorityQueue<>(
            (a,b) -> ((Integer)a.val).compareTo(b.val)
        );
        
        for(int i=0; i<lists.length; i++){
            if(lists[i] != null)
                pq.offer(lists[i]);
        }
        
        ListNode head = pq.poll();
        ListNode tail =  head; 
        if(head != null && head.next != null)
            pq.add(head.next);
    
        while(!pq.isEmpty()){
            tail.next = pq.poll();
            tail = tail.next;
            if(tail.next != null)
                pq.offer(tail.next);
            
        }
        
        return head;
    }

As we see from the above code examples, it is easy to identify a priority queue problem and simple to solve. Please share your views and best of luck with your preparations.

Data structure with insert delete and getRandom in O(1)

Design a data structure with insert delete and getRandom in O(1)

The problem statement is to design a data structure which performs the following operations in O(1) time complexity:
1. Insert an element, insert(int value)
2. Remove an element, remove(int value)
3. Get random element, getRandom()

For example, insert 1 into the data structure insert(1): [1] insert 2 into the data structure insert(2): [1,2] insert 3 into the data structure insert(3): [1,2,3]

Remove 2 from it, remove(2). [1,3] getRandom() should return 1 and 3 with equal probabilities.

These kind of problems are easy and hard at the same time. Idea is to go step by step and solve each part. The first step is to define an interface for this data structure, which is easy given the definition of the problem.

public interface IRandomNumberGenerator {
    public boolean insert(int value);
    public boolean remove (int value);
    public int getRandom();
}

Now that interface is ready, time to start implementing the class which implements this interface. First of all, we have to find a container to store all the elements. If we take an ArrayList, insert() is O(1) as we will always add new element at the end of the ArrayList. getRandom is also O(1). However, there is problem with remove(). To remove an element from ArrayList, we have to scan the whole ArrayList and remove the element, the move all the elements on the right of the deleted element to one index left. This is O(n) operation.

Insert delete and getRandom in O(1): selection of data structures

A problem with storing elements in an ArrayList is that while removal, we have to scan the list and find the location of the element to be removed. What if we already knew the location of the element? If we store the position of each element in ArrayList in a HashMap which maps the value to its index on ArrayList

Now, insert() has to insert a value to two data structures, first into the ArrayList and then the location of the value in ArrayList to the HashMap. Remove operation can simply go to the location in the ArrayList and delete the element. Wait, still, we have to move all the elements on the right one position left. It means the worst case complexity of remove() still O(n).

We know one thing: if I remove the last element from the ArrayList then there is no shifting required. What if we copy the last value at the index of the element to be removed and then just remove the last element. Be careful, we have to update the HashMap with the new value for the element at the last index of ArrayList. In this way, remove() is also O(1).

Insert, delete and getRandom in O(1): implementation

package AlgorithmsAndMe;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class RandomNumberGenerator implements IRandomNumberGenerator {

    private ArrayList<Integer> list;
    private Map<Integer, Integer> loc;
    private Random random;

    //Initializing the class
    public RandomNumberGenerator(){
        list = new ArrayList<>();
        loc = new HashMap<>();
        random = new Random();
    }

    @Override
    public boolean insert(int value) {
        /*If hash already contains key then it is a duplicate key.
          So, we just return false.
         */
        if(loc.containsKey(value)) return false;

        //Insert into list
        list.add(value);

        //Save the location on hash map
        loc.put(value, list.size()-1);
        return true;
    }

    @Override
    public boolean remove(int value) {
        /* If there is no entry in hash, that means
        there is no element in ArrayList */
        if(!loc.containsKey(val)) return false;
 
        int location = loc.get(val);
        //Remove from hash
        loc.remove(val);

        if(location != list.size()-1){
            /*Copy the last value in the array
            list to the current location*/
            list.set(location, list.get(list.size()-1));

            //Update the location of last element in hash
            loc.put(list.get(location), location);
        }

        //remove the last location from ArrayList
        list.remove(list.size()-1);
 
        return true;
    }

    @Override
    public int getRandom() {
        return list.get(random.nextInt(list.size()));
    }
}

package AlgorithmsAndMe;

import static org.junit.Assert.*;

public class RandomNumberGeneratorTest {

    RandomNumberGenerator randomNumberGenerator =
           new RandomNumberGenerator();

    @org.junit.Test
    public void testInterface() {
        assertEquals(true, randomNumberGenerator.insert(4));
        assertEquals(true, randomNumberGenerator.insert(5));
        assertEquals(true, randomNumberGenerator.insert(3));
        assertEquals(true, randomNumberGenerator.insert(2));

        assertEquals(true, randomNumberGenerator.remove(4));

        int random = randomNumberGenerator.getRandom();
        System.out.println(random);
    }
}

The complexity of the whole data structure for insert, delete and getRandom is O(1).

Insert, delete and get random when duplicates are allowed

Let’s make this problem a bit more complex by making duplicate elements possible in the list. The first problem with the existing implementation is that it stores the location of an element in ArrayList in a HashMap. If the same element can appear multiple times in the list, then which location should we store? We should store all the locations. It will change the definition of our HashMap as

Map<Integer, HashSet<Integer>> 

Hashset implements the Set interface, backed by a hash table which is actually a HashMap instance. No guarantee is made as to the iteration order of the set which means that the class does not guarantee the constant order of elements over time, that is what we require. We require that insert and remove operation on this data structure should be O(1) or constant time complexity.
To know more about the complexity of various data structures in Java, follow Runtime Complexity of Java Collections and read reason why HashSet provides constant time insert and remove operations.
Everything else follows the same process. To insert(), we should insert the location of the element at the HashSet in the hash table. While removing we find the last location of the element, put the last element of ArrayList in that location and update the HashSet of the location corresponding to the value at the last index of the ArrayList. Remove the last element from ArrayList.
We also have to move the last element in ArrayList of location in Hash, which is O(1) operation.

getRandom() implementation remains same.

package AlgorithmsAndMe;

import java.util.*;

public class RandomNumberGenerator implements IRandomNumberGenerator {

    private ArrayList<Integer> list;
    private Map<Integer, HashSet<Integer>> loc;
    private Random random;

    //Initializing the class
    public RandomNumberGenerator(){
        list = new ArrayList<>();
        loc = new HashMap<>();
        random = new Random();
    }

    @Override
    public boolean insert(int value) {

        if(!loc.containsKey(value)){
            loc.put(value, new HashSet<>());
        };

        //Insert into list
        list.add(value);

        //Save the location on hash map
        loc.get(value).add(list.size()-1);
        return true;
    }

    @Override
    public boolean remove(int value) {
        /* If there is no entry in hash, that means
        there is no element in ArrayList */
        if(!loc.containsKey(value)) return false;

        //Get the last location of the element in ArrayList
        HashSet<Integer> listLocations = loc.get(value);
        int location = listLocations.iterator().next();
        loc.get(value).remove(location);

        int lastElement = list.get(list.size()-1);
        if( lastElement != value) {
        /*Copy the last value in the array
        list to the current location*/
            list.set(location, lastElement);
            //Update the location of last element in hash
            loc.get(lastElement).remove(list.size()-1);
            loc.get(lastElement).add(location);
        }
        //remove the last location from ArrayList
        list.remove(list.size()-1);

        if(listLocations.isEmpty()) loc.remove(value);
        return true;
    }

    @Override
    public int getRandom() {
        return list.get(random.nextInt(list.size()));
    }
}

Other problems which are very similar to this concept are: design an LRU cache, first non-repeated character in stream etc.

Please share if there is anything wrong or missing. If you are preparing for an interview and need one to one personalized coaching, please reach out to us on [email protected]