Heap: kth largest element in a stream
Problem Statement: You are given an infinite stream of integers, you need to find the kth largest element at any point of time. Example Input: Infinite stream of integers k = 3 10, 20, 11, 70, 50, 40, 100, 5, … Output: The k’th largest element is NA. The k’th largest element is NA. The […]
Heap: Sum of all the elements between k1 and k2 smallest elements
Problem Statement: You are given array of integers and 2 numbers k1 and k2. You need to find the sum of all the elements between the given 2 k1 and k2 elements in the array. Example Input : arr[] = {20, 8, 22, 4, 12, 10, 14}, k1 = 3, k2 = 6 Output : […]
Heap: Connect ropes with minimum cost
Problem Statement: You are given n ropes of different lengths. You need to connect the ropes into one rope. The cost to connect 2 ropes is equal to the sum of their lengths. You need to connect the rpoes with minimum cost. Example Input: 4, 3, 2, 6. If you connect the ropes in below […]
Heap: Top K Frequent Words
Problem Statement: You are given an array of repeated numbers and a integer K. You need to find the top K numbers that are repeated maximum frequency. Example Input: arr[] = {3, 1, 4, 4, 5, 2, 6, 1}, k = 2 Output: 4 1 Solution This solution is very simple. We will use HashMap […]
Heap: Frequency sort
Problem Statement: You are given an array with repeated elements. You need to sort such that the one that has ore frequency should come first. Example Input: arr[] = {1, 1, 1, 3, 2, 2, 4} Output: arr[] = {1, 1, 1, 2, 2, 3, 4} Solution The solution is similar to previous question. Convert […]
Heap: Top K Frequent Elements
Problem Statement: You are given an integer array and a value k, you need to return the k most frequest elements. Example Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] Here both 1 and 2 repeated 2 or more times. Solution Here they have asked top or largest or greatest, then we have to […]
Heap: K closest number
Problem Statement: You are given an array and a value k and x. You need to find the k closest elements to x in arr[] Example arr[] = { 5, 6, 7, 8, 9} k = 3 x = 7 The closest values of x are 6, 7, 8 Solution Subtract x with all the […]
Heap: Sort a K sorted array or nearly sorted array
Problem Statement: You are given an array elements in which each element is at k away from its target position. Example Input: arr[] = {6, 5, 3, 2, 8, 10, 9} k = 3 Solution First we will understand the question. Here the array is nearly sorted. It means an element at index “n” can […]
Heap: Return k largest element
Problem Statement: You are given an unsorted array of integer elements and “k”. You need to get the “k” largest elements. Example Input: arr[] = {7, 10, 4, 3, 20, 15} k = 3 Output: 20, 15, 10. Solution We can solve this problem by using sorting and get the result. But the time complexity […]
Heap: Kth smallest element.
Problem Statement: You are given an unsorted array of integer elements and “k”. You need to get the “k”th smallest element. Example Input: arr[] = {7, 10, 4, 3, 20, 15} k = 3 Output: 7. Solution Before we start the solution, let us understand few points related to heap and identification of heap related […]