Back to top

Heaps

Overview

Heap is a tree-based data-structure which satisfies the heap property that in case of a max-heap for every node C, if a node P is a parent of node C then the value of P is greater than or equal to the value of node C. In the subsequent sections, we will be providing different patterns of programming questions commonly asked in coding interviews which can be solved using heaps. We don’t want to overwhelm our readers with a plethora of heap questions. So, we have done the heavy lifting for you by going through almost all the questions on leetcode and categorizing the different patterns of questions commonly asked in the interviews.

Pattern -1 : Maintaining k-closest elements

Prob 378 - Kth Smallest Element in a Sorted Matrix

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

        /**
         * We want to fetch the kth smallest element in a matrix.
         * https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/
         *
         * Approach: We will iterate through the elements in the matrix and add it
         * to a max heap. We keep on adding the first k elements to the queue.
         * After that, if we encounter an element smaller than the root of the heap
         * then we pop the root of the heap and add the new element to the heap.
         *
         * Time Complexity: O(nlgk) where n is the number of elements in the matrix
         * Space Complexity: k
         *
         * @param matrix - the input matrix
         * @param k - input parameter
         * @return the kth smallest element
         */
        public int kthSmallest(int[][] matrix, int k) {

            PriorityQueue<Integer> priorityQueue =
                    new PriorityQueue<>((o1, o2) -> Integer.compare(o2, o1));

            int counter = 0;

            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++, counter++) {
                    if(counter < k) {
                        priorityQueue.add(matrix[i][j]);
                    } else if(priorityQueue.peek() > matrix[i][j]) {
                        priorityQueue.poll();
                        priorityQueue.add(matrix[i][j]);
                    }
                }
            }

            return priorityQueue.peek();
        }

Prob 973 - K Closest Points to Origin

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

        /**
         * We need to find the k-closest points to the origin.
         * https://leetcode.com/problems/k-closest-points-to-origin/
         *
         * Approach: We will maintain the points in a min heap and
         * add all the points in the heap. After that, we will keep
         * popping the elements from the heap.
         *
         * Time Complexity: O(nlgk) given n is the number of points
         * Space Complexity: O(k)
         *
         * @param points - input points
         * @param K - input K
         * @return array of K closest points
         */
        public int[][] kClosest(int[][] points, int K) {

            PriorityQueue<Point> priorityQueue =
                    new PriorityQueue<>((o1, o2) -> Double.compare(o1.distance, o2.distance));

            for (int[] idx : points) {
                double distance = Math.sqrt((idx[0] * idx[0]) + (idx[1] * idx[1]));
                Point point = new Point(idx, distance);
                priorityQueue.add(point);
            }

            int[][] pts = new int[K][];

            for (int i = 0; i < K; i++) {
                pts[i] = priorityQueue.poll().idx;
            }

            return pts;
        }

       class Point {
            int[] idx;
            double distance;

            public Point(int[] idx, double distance) {
                this.idx = idx;
                this.distance = distance;
            }
        }

Pattern -2 : Using auxiliary data structure

Prob 767 - Reorganize String

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

       /**
         * We need to check if the letters can be rearranged
         * so that two characters that are adjacent to each other
         * are not the same and if possible, output any possible result.
         * https://leetcode.com/problems/reorganize-string/
         *
         * Approach: We will use a map to store the frequency of each
         * character. If any of the characters occurs more than half
         * of the string then we return an empty string.
         *
         * After that, we will use a greedy approach to add characters who
         * have a more frequency. For this, we will add the characters in a max heap
         * which uses the frequency of characters to order them.
         *
         * We fetch the top two frequent elements and add them in a string.
         * We will then decrease the frequency of the two popped characters
         * and add them back if the frequency is greater than zero. At the end,
         * we can add the last remaining character in cases of odd length
         * strings.
         *
         * Time Complexity: O(klgk) where k is the number of unique characters in string
         * Space Complexity: O(k)
         *
         * @param S
         * @return
         */
        public String reorganizeString(String S) {

            Map<Character, Integer> map = new HashMap<>();
            for (char c : S.toCharArray()) {
                int count = map.getOrDefault(c, 0) + 1;
                if(count > (S.length() + 1) / 2) {
                    return "";
                }
                map.put(c, count);
            }

            PriorityQueue<Character> pq =
                    new PriorityQueue<>((o1, o2)
                            -> Integer.compare(map.get(o2), map.get(o1)));
            pq.addAll(map.keySet());

            StringBuilder sb = new StringBuilder();
            while (pq.size() >= 2) {
                char ch1 = pq.poll();
                char ch2 = pq.poll();
                sb.append(ch1);
                sb.append(ch2);
                map.put(ch1, map.get(ch1) - 1);
                map.put(ch2, map.get(ch2) - 1);
                if(map.get(ch1) > 0) {
                    pq.add(ch1);
                }
                if(map.get(ch2) > 0) {
                    pq.add(ch2);
                }
            }

            if(pq.size() > 0) {
                sb.append(pq.poll());
            }
            return sb.toString();
        }

Pattern -3 : Graph Traversal

Prob 787 - Cheapest Flights Within K stops

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

       /**
         * We want to find the cheapest price from src to dst with upto
         * k stops. If there is no such route, output -1.
         * https://leetcode.com/problems/cheapest-flights-within-k-stops/
         *
         * Approach: We store the flights info in a map. We can then use
         * a min heap to find the flight route with cheapest prices. We use
         * an array to keep track of the cost so far, source stop and stops
         * left.
         *
         * After that, we pop the element from the queue which is an array.
         * If the dst stop is reached then we return the cost. Otherwise,
         * we add the adjacent stops in the queue by updating the price
         * and the number of stops.
         *
         * Time Complexity: O(nlgn)
         * Space Complexity: O(n)
         *
         * @param n - the total number of stops
         * @param flights - the flights represented by the edges
         * @param src - the source stop
         * @param dst - the destination stop
         * @param k - the number of stops
         * @return the cheapest price to reach from src to dst within k stops
         */
        public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
            Map<Integer, Map<Integer, Integer>> prices = new HashMap<>();
            for (int[] flight : flights) {
                if(!prices.containsKey(flight[0])) {
                    prices.put(flight[0], new HashMap<>());
                }
                prices.get(flight[0]).put(flight[1], flight[2]);
            }

            Queue<int[]> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1[0], o2[0]));

            // the cost so far, source stop and stops left
            pq.add(new int[]{0, src, k + 1});

            while (!pq.isEmpty()) {
                int[] top = pq.remove();
                int price = top[0];
                int s = top[1];
                int stops = top[2];
                if(s == dst) return price;
                if(stops > 0) {
                    Map<Integer, Integer> adj = prices.getOrDefault(s, new HashMap<>());
                    for (int e: adj.keySet()){
                        pq.add( new int[] { adj.get(e) + price, e, stops - 1});
                    }
                }
            }
            return -1;
        }

Pattern -4: Application Oriented

Prob 621- Task Scheduler

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

       /**
         *
         * We want to find the least number of units of times that the CPU will take
         * to finish all the tasks.
         * https://leetcode.com/problems/task-scheduler/
         *
         * Approach: We use a max heap to maintain the list of frequencies of all the
         * characters. Given that there must be atleast n units of time between any two
         * same tasks we fetch n+1 elements from the max heap and add them to the list.
         * We then reduce the frequency of each of the elements by 1 and add it back to
         * max heap. After that, if the heap is empty then we just add the size of the list
         * to the cycles. Otherwise, we just use n+1 as the number of elements.
         *
         * Time Complexity: O(Mlgk), where M = tasks.length and k is the number of distinct characters
         * Space Complexity: O(lgk), where K is the number of distinct characters.
         *
         * @param tasks
         * @param n
         * @return
         */
        public int leastInterval(char tasks[], int n) {
            Map<Character, Integer> map = new HashMap<>();
            for( char c : tasks ) {
                map.put(c, map.getOrDefault(c, 0) + 1);
            }

            PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
            maxHeap.addAll(map.values());

            int cycles = 0;
            while (!maxHeap.isEmpty()){
                List<Integer> temp = new ArrayList<>();
                for(int i = 1; i <= n + 1; i++){
                    if(!maxHeap.isEmpty()) {
                        temp.add(maxHeap.remove());
                    }
                }

                for(int i : temp) {
                    if(--i > 0) {
                        maxHeap.add(i);
                    }
                }

                cycles += maxHeap.isEmpty() ? temp.size() : n + 1;
            }
            return cycles;
        }

References