Top K Elements
FUNCTION findTopKElements(arr, k):
# Initialize a min heap
minHeap = new MinHeap()
# Insert the first k elements into the heap
FOR i FROM 0 TO k - 1:
minHeap.insert(arr[i])
# Process the remaining elements
FOR i FROM k TO length of arr - 1:
IF arr[i] > minHeap.peek(): # Compare with the smallest in heap
minHeap.extractMin() # Remove the smallest element
minHeap.insert(arr[i]) # Insert the new larger element
RETURN minHeap.toList() # Convert heap to list and return
Reorganize String
Statement
Given a string, str, rearrange it so that any two adjacent characters are not the same. If such a reorganization of the characters is possible, output any possible valid arrangement. Otherwise, return an empty string.
Constraints:
1≤1≤ str.length ≤500≤500 Input string consists of lowercase English letters.
class Reorganize {
public static String reorganizeString(String str) {
Map <Character, Integer> charCounter = new HashMap <> ();
for (char c: str.toCharArray()) {
int freq = charCounter.getOrDefault(c, 0) + 1;
charCounter.put(c, freq);
}
PriorityQueue <Map.Entry <Character, Integer>> maxFreqChar = new PriorityQueue <Map.Entry <Character, Integer>> (
(item1, item2) -> item2.getValue() - item1.getValue());
maxFreqChar.addAll(charCounter.entrySet());
Map.Entry <Character, Integer> previous = null;
StringBuilder result = new StringBuilder(str.length());
while (!maxFreqChar.isEmpty() || previous!=null) {
if (previous != null && maxFreqChar.isEmpty())
return "";
Map.Entry <Character, Integer> currentEntry = maxFreqChar.poll();
int count=currentEntry.getValue()-1;
result.append(currentEntry.getKey());
if(previous!=null){
maxFreqChar.add(previous);
previous=null;
}
if(count != 0){
previous = new AbstractMap.SimpleEntry<>(currentEntry.getKey(), count);
}
}
return result.toString();
}K Closest Points to Origin
Top K Frequent Elements hashMap -> Entry -> PQ
Kth Largest Element in an Array – Return root of heap
Third Maximum Number
Let’s solve the Third Maximum Number problem using the Top K Elements pattern.
Statement
Given an integer array nums, determine and return the third distinct maximum element in the array. If the array contains fewer than three distinct elements, return the maximum element instead.
Constraints:
1<=1<= nums.length <=103<=103 −231<=−231<=nums[i] <=231−1<=231−1
public static int thirdMax(int[] nums) {
PriorityQueue<Integer> heap = new PriorityQueue<>();</Integer>
Set<Integer> taken = new HashSet<>();
for (int num : nums) {
if (taken.contains(num)) {
continue;
}
if (heap.size() == 3) {
if (heap.peek() < num) {
taken.remove(heap.poll());
heap.offer(num);
taken.add(num);
}
} else {
heap.offer(num);
taken.add(num);
}
}
if (heap.size() == 1) {
return heap.peek();
} else if (heap.size() == 2) {
int firstNum = heap.poll();
return Math.max(firstNum, heap.peek());
}
return heap.peek();
}Find Subsequence of Length K with the Largest Sum
You are given an integer array nums and an integer k. Your task is to find a subsequence of nums of length k that has the largest possible sum.
Constraints:
1≤1≤ nums.length ≤1000≤1000 −105≤−105≤ nums[i] ≤105≤105 1≤1≤ k ≤≤ nums.length
public static int[] maxSubsequence(int[] nums, int k) {
PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
for (int i = 0; i < nums.length; i++) {
minHeap.offer(new int[]{nums[i], i});
if (minHeap.size() > k) {
minHeap.poll();
}
}
List<int[]> pairsList = new ArrayList<>(minHeap);
pairsList.sort(Comparator.comparingInt(a -> a[1])); // Sort by the original index
int[] result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = pairsList.get(i)[0];
}
return result;
}Minimum Cost to Hire K Workers
Let’s solve the Minimum Cost to Hire K Workers problem using the Top K Elements pattern.
Statement
You are given nn workers, each characterized by two attributes:
quality[i]: Represents the work quality of the ithith worker. wage[i]: Represents the minimum wage expectation of the ithith worker.
You want to hire exactly k workers to form a paid group, and you must follow these payment rules:
Wage expectation: Every worker in the group must be paid at least their minimum wage expectation. Proportional pay: The pay for each worker must be directly proportional to their quality. For example, if one worker’s quality is twice that of another, they must be paid twice as much.
Your goal is to determine the least amount of money required to hire exactly k workers while satisfying the above conditions.
public static double minCostToHireWorkers(int[] quality, int[] wage, int k) {
List<double[]> workers = new ArrayList<>();
for (int i = 0; i < quality.length; i++) {
workers.add(new double[]{(double) wage[i] / quality[i], (double) quality[i]});
}
Collections.sort(workers, Comparator.comparingDouble(a -> a[0]));
PriorityQueue<Double> heap = new PriorityQueue<>(Collections.reverseOrder());
double totalQuality = 0;
double minCost = Double.MAX_VALUE;
for (double[] worker : workers) {
double ratio = worker[0];
double q = worker[1];
heap.add(q);
totalQuality += q;
if (heap.size() > k) {
totalQuality -= heap.poll();
}
if (heap.size() == k) {
minCost = Math.min(minCost, ratio * totalQuality);
}
}
return minCost;
}Maximum Performance of a Team
Let’s solve the Maximum Performance of a Team problem using the Top K Elements pattern.
Statement
You are given two integers, n and k, and two integer arrays, speed and efficiency, both of length n. There are n engineers numbered from 1 to n. The value speed[i] represents the speed of the i-th engineer, and efficiency[i] represents their efficiency.
To form a team with the maximum performance, you need to select at most k different engineers from the n engineers.
The performance of a team is calculated as follows:
The sum of the selected engineers’ speeds ×× the minimum efficiency among the selected engineers
Return the maximum perf
public static int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
final int MOD = (int)1e9 + 7;
// Pair each engineer's efficiency and speed, and sort by efficiency in descending order
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
List<int[]> engineers = new ArrayList<>();
for (int i = 0; i < n; i++) {
engineers.add(new int[]{efficiency[i], speed[i]});
}
engineers.sort((a, b) -> b[0] - a[0]); // Sort by efficiency descending
long maxPerf = 0, speedSum = 0;
// Iterate over engineers sorted by decreasing efficiency
for (int[] eng : engineers) {
int eff = eng[0];
int spd = eng[1];
// If the team already has k engineers, remove the one with the smallest speed
if (minHeap.size() == k) {
speedSum -= minHeap.poll();
}
// Add the current engineer's speed to the heap and update the speed sum
minHeap.offer(spd);
speedSum += spd;
// Calculate current performance using current engineer's efficiency
long perf = speedSum * eff;
// Update the maximum performance if the current one is greater
maxPerf = Math.max(maxPerf, perf);
}
// Return the maximum performance modulo 10^9 + 7 to avoid overflow
return (int)(maxPerf % MOD);
}Smallest Range Covering Elements from K Lists
Let’s solve the Smallest Range Covering Elements from K Lists problem using the Top K Elements pattern.
Statement
You are given kk sorted lists of integers, nums, where each list in nums is in non-decreasing order. Your task is to find the smallest range that contains at least one element from each of the kk lists.
A range [a,b][a,b] is considered sm
{
static class Element implements Comparable<Element> {
int value;
int listIndex;
int elementIndex;
public Element(int value, int listIndex, int elementIndex) {
this.value = value;
this.listIndex = listIndex;
this.elementIndex = elementIndex;
}
@Override
public int compareTo(Element other) {
return Integer.compare(this.value, other.value);
}
}
public int[] smallestRange(List<List<Integer>> nums) {
PriorityQueue<Element> pq = new PriorityQueue<>();
int maxVal = Integer.MIN_VALUE;
int rangeStart = 0;
int rangeEnd = Integer.MAX_VALUE;
for (int i = 0; i < nums.size(); i++) {
int val = nums.get(i).get(0);
pq.offer(new Element(val, i, 0));
if (val > maxVal) {
maxVal = val;
}
}
while (pq.size() == nums.size()) {
Element minElem = pq.poll();
int minVal = minElem.value;
if (maxVal - minVal < rangeEnd - rangeStart) {
rangeStart = minVal;
rangeEnd = maxVal;
}
int nextIndex = minElem.elementIndex + 1;
if (nextIndex < nums.get(minElem.listIndex).size()) {
int nextVal = nums.get(minElem.listIndex).get(nextIndex);
pq.offer(new Element(nextVal, minElem.listIndex, nextIndex));
if (nextVal > maxVal) {
maxVal = nextVal;
}
} else {
break;
}
}
return new int[]{rangeStart, rangeEnd};
}Maximum Product After K Increments
Let’s solve the Maximum Product After K Increments using the Top K Elements pattern.
Statement
You are given an array, nums, consisting of non-negative integers, and an integer k representing the maximum number of allowed operations.
In each operation, you may select any element in nums and increment it by 11. You can perform, at most, k such operations.
Your task is to maximize the product of all elements in the array after performing up to k operations. As the resulting product can be very large, return the product modulo 109+7109+7.
public class Solution
{
// Function to maximize product after k increments
public int maximumProduct(int[] nums, int k)
{
int MOD = 1_000_000_007;
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
minHeap.offer(num);
}
for (int i = 0; i < k; i++) {
int smallest = minHeap.poll();
minHeap.offer(smallest + 1);
}
long result = 1;
while (!minHeap.isEmpty()) {
result = (result * minHeap.poll()) % MOD;
}
return (int) result;
}
**Find the K-Sum of an Array
**
Try to solve the Find the K-Sum of an Array problem.
Statement
You are given an integer array, nums, and a positive integer k. Your task is to determine and return the kthkth largest possible sum among all subsequences of the array. A subsequence is formed by deleting no or more elements from the array without changing the order of the remaining elements. The sum of a subsequence is the total of its elements.
public class Solution {
public static long kSum(int[] nums, int k) {
// Step 1: Calculate the maximum possible subsequence sum
// and convert all elements to their absolute values (to represent potential losses)
long maxSum = 0L;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
maxSum += nums[i]; // Add positive values to the maxSum
} else {
nums[i] = -nums[i]; // Convert negative values to positive for loss tracking
}
}
// Step 2: Sort the array of absolute values to process smaller losses first
Arrays.sort(nums);
// Step 3: Initialize a min heap with a starting sum of 0 and index 0
// The heap stores tuples of (current loss sum, index in nums)
PriorityQueue<long[]> minHeap = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
minHeap.offer(new long[]{0L, 0L}); // current sum, index
// Step 4: Generate the (k - 1) smallest loss sums using the heap
for (int i = 0; i < k - 1; i++) {
long[] top = minHeap.poll();
long currentSum = top[0];
int index = (int) top[1];
if (index < nums.length) {
// Push the sum that includes nums[index] (i.e., expand the current subset)
minHeap.offer(new long[]{currentSum + nums[index], index + 1});
if (index > 0) {
// Push the sum where the last included number is replaced by the current one
// This explores a new combination path in the subset space
minHeap.offer(new long[]{currentSum + nums[index] - nums[index - 1], index + 1});
}
}
}
// Step 5: The k-th largest subsequence sum is the max sum minus the (k-1)th smallest loss
return maxSum - minHeap.peek()[0];
}Least Number of Unique Integers after K Removals
Let’s solve the Least Number of Unique Integers after K Removals problem using the Top K Elements pattern.
Statement
You are given an integer array, arr, and an integer, k. Your task is to remove exactly k elements from the array so that the number of distinct integers remaining in the array is minimized. Determine the minimum possible count of unique integers after the removals.
public int findLeastNumOfUniqueInts(int[] arr, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : arr) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
PriorityQueue<Integer> frequencies = new PriorityQueue<>();
for (int freq : map.values()) {
frequencies.offer(freq);
}
int counter = 0;
// Traversing all frequencies
while (!frequencies.isEmpty()) {
// Removing the least frequent element
counter += frequencies.peek();
// If the number of elements removed exceeds k, return
// the remaining number of unique elements
if (counter > k) {
return frequencies.size();
}
frequencies.poll();
}
// We have removed all elements, so no unique integers remain
return 0;
}
