DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Heap(Priority Queue)

Find kth largest element in the array

TC:O(NlogN) as heap sort will take nlogn time to build heap

class Solution { public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> q = new PriorityQueue<>(); for(int i : nums){ q.add(i); while(!q.isEmpty() && q.size() > k){ q.remove(); } } return q.peek(); } }
Enter fullscreen mode Exit fullscreen mode

K max sum combination

TC: O(N^2), for using two for loops

import java.util.*; public class Solution{ public static ArrayList<Integer> kMaxSumCombination(ArrayList<Integer> a, ArrayList<Integer> b, int n, int k){ // Write your code here. PriorityQueue<Integer> q = new PriorityQueue<>(); for(int i : a) for(int j : b) if(q.size()<k) q.add(i+j); else if(q.peek() < i+j){ q.remove(); q.add(i+j); } ArrayList<Integer> list = new ArrayList<>(); while(!q.isEmpty()) list.add(0,q.remove()); // it will add values at index 0 only by that way values will keep on shifting return list; } }
Enter fullscreen mode Exit fullscreen mode

Merge n sorted Arrays

TC: O(N^2) + O(2*N^2log(N))

import java.util.*; public class Solution { public static ArrayList<Integer> mergeKSortedArrays(ArrayList<ArrayList<Integer>> kArrays, int k) { PriorityQueue<Integer> q = new PriorityQueue<>(); for(ArrayList<Integer> l : kArrays){ for(Integer i : l){ q.add(i); } } ArrayList<Integer> list = new ArrayList<>(); while(!q.isEmpty()){ list.add(q.remove()); } return list; } }
Enter fullscreen mode Exit fullscreen mode

Maximum xor from an element in the array

TC: O(N*MLogM), where N is size of queries list, M is size of arr List and LogM is the cost of adding value to priority queue

import java.util.*; public class Solution { public static ArrayList<Integer> maxXorQueries(ArrayList<Integer> arr, ArrayList<ArrayList<Integer>> queries) { PriorityQueue<Integer> q = new PriorityQueue<>((a,b)-> b-a); ArrayList<Integer> result = new ArrayList<>(); for( int i =0;i<queries.size();i++){ int X = queries.get(i).get(0); int A = queries.get(i).get(1); for(Integer j : arr){ if(j<=A){ q.add(X^j); } } if(!q.isEmpty()){ result.add(q.remove()); } else result.add(-1); q.clear(); } return result; } }
Enter fullscreen mode Exit fullscreen mode

This is will lead to TLE
Hence, Optimized solution can achieve this in O(N*M), ( we won't be using priority queue)

import java.util.*; public class Solution { public static ArrayList<Integer> maxXorQueries(ArrayList<Integer> arr, ArrayList<ArrayList<Integer>> queries) { ArrayList<Integer> result = new ArrayList<>(); for( int i =0;i<queries.size();i++){ int X = queries.get(i).get(0); int A = queries.get(i).get(1); int max = -1; for(Integer j : arr){ if(j<=A){ max = Integer.max(max,X^j); } } result.add(max); } return result; } }
Enter fullscreen mode Exit fullscreen mode

Top comments (0)