Prashant Mishra

Posted on

# 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){
while(!q.isEmpty() && q.size() > k){
q.remove();
}
}
return q.peek();
}
}
``````

# 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){
PriorityQueue<Integer> q = new PriorityQueue<>();
for(int i  : a)
for(int j : b)
if(q.size()<k)
else
if(q.peek() < i+j){
q.remove();
}
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;
}
}
``````

# 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){
}
}
ArrayList<Integer> list = new ArrayList<>();
while(!q.isEmpty()){
}
return list;
}
}
``````

# 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){
}
}
if(!q.isEmpty()){
}
q.clear();
}
return result;

}
}
``````

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);
}
}
}
return result;

}
}
``````

DEV Community

## Why You Need to Study Javascript Fundamentals

>> Check out this classic DEV post <<