Any problem that asks us to find the top/smallest/frequent K elements among a given set falls under this pattern.
The best data structure that comes to mind to keep track of K elements is Heap. This pattern will make use of the Heap to solve multiple problems dealing with K elements at a time from a set of given elements.
Although this course uses Heaps to solve Top 'K' Elements problems, JavaScript does not have a built in method for Heaps/Priority Queues. It can be very time consuming to implement a Heap class from scratch, especially during an interview. After reviewing the JavaScript solutions on Leetcode the most effecient way to solve a Top 'K' Elements problem is usually with QuickSort, BinarySearch, BucketSort, Greedy Algorithms, or HashMaps. For more information take a look at these
Given an unsorted array of numbers, find the
Klargest numbers in it.
Note: For a detailed discussion about different approaches to solve this problem, take a look at Kth Smallest Number.
A brute force solution could be to sort the array and return the largest K numbers. The time complexity of such an algorithm will be O(N*logN) as we need to use a sorting algorithm like Quicksort. Can we do better than that?
function findKLargestNumbers(nums, k) {
return quickSort(nums).slice(-k);
}
function quickSort(array) {
//recursive base case
if (array.length === 1) return array;
//set pivot to end value
const pivotPoint = array[array.length - 1];
const firstHalf = [];
const secondHalf = [];
for (let i = 0; i < array.length - 1; i++) {
if (array[i] < pivotPoint) {
firstHalf.push(array[i]);
} else {
secondHalf.push(array[i]);
}
}
//recursively sort
if (firstHalf.length > 0 && secondHalf.length > 0) {
return [...quickSort(firstHalf), pivotPoint, ...quickSort(secondHalf)];
} else if (firstHalf.length > 0) {
return [...quickSort(firstHalf), pivotPoint];
} else {
//secondHalf.length> 0
return [pivotPoint, ...quickSort(secondHalf)];
}
}
console.log(
`Here are the top K numbers: ${findKLargestNumbers([3, 1, 5, 12, 2, 11], 3)}`
);
console.log(
`Here are the top K numbers: ${findKLargestNumbers([5, 12, 11, -1, 12], 3)}`
);- As discussed above, the time complexity of this algorithm is
O(K * log K +(N - K) * logK), which is asymptotically equal toO(N*logK). - The space complexity will be
O(K)since we need to store the topKnumbers in an array.
https://leetcode.com/problems/kth-largest-element-in-an-array/
Given an unsorted array of numbers, find
Kthsmallest number in it.Please note that it is the
Kthsmallest number in the sorted order, not theKthdistinct element.
function findKLargestNumbers(nums, k) {
const finalIndex = nums.length - k;
let start = 0;
let end = nums.length - 1;
while (start <= end) {
//random number between start and end for pivot
const pivot = Math.floor(Math.random() * (end - start + 1) + start);
//final postion of the pivot in a sorted array
const pivotIndex = sort(nums, pivot, start, end);
if (pivotIndex === finalIndex) return nums[finalIndex];
//if pivotIndex is smaller we undershot, so look only on the first half
if (pivotIndex < finalIndex) start = pivotIndex + 1;
//if pivotIndex is larger we overshot, so look only on the first half
else end = pivotIndex - 1;
}
}
function sort(array, pivot, start, end) {
//swap the pivot to the end
[array[pivot], array[end]] = [array[end], array[pivot]];
let i = start;
let j = start;
while (j < end) {
if (array[j] <= array[end]) {
[array[i], array[j]] = [array[j], array[i]];
i++;
}
j++;
}
//swap pivot to its final position
[array[i], array[end]] = [array[end], array[i]];
return i;
}
console.log(
`Here is the top K number: ${findKLargestNumbers(
[3, 2, 3, 1, 2, 4, 5, 5, 6],
4
)}`
);
//4
console.log(
`Here is the top K number: ${findKLargestNumbers([3, 1, 5, 12, 2, 11], 3)}`
);
//5
console.log(
`Here is the top K number: ${findKLargestNumbers([5, 12, 11, -1, 12], 3)}`
);
//11- As discussed above, the time complexity of this algorithm is
O(K * log K +(N - K) * logK), which is asymptotically equal toO(N*logK). - The space complexity will be
O(K)since we need to store the topKnumbers in an array.
https://leetcode.com/problems/k-closest-points-to-origin/
Given an array of points in a 2D plane, find
Kclosest points to the origin.
Note: For a detailed discussion about different approaches to solve this problem, take a look at Kth Smallest Number.
function findClosestPoints(points, k) {
let result = [];
points = points.sort(
([x1, y1], [x2, y2]) =>
Math.pow(x1, 2) + Math.pow(y1, 2) - (Math.pow(x2, 2) + Math.pow(y2, 2))
);
result = [...points.slice(0, k)];
return result;
}
console.log(
`"Here are the k points closest the origin: " ${findClosestPoints(
[
[1, 2],
[1, 3],
],
1
)}`
);
//The Euclidean distance between (1, 2) and the origin is sqrt(5).
//The Euclidean distance between (1, 3) and the origin is sqrt(10).
//Since sqrt(5) < sqrt(10), therefore (1, 2) is closer to the origin.
console.log(
`"Here are the k points closest the origin: " ${findClosestPoints(
[
[1, 3],
[3, 4],
[2, -1],
],
2
)}`
);
//[[1, 3], [2, -1]]https://leetcode.com/problems/minimum-cost-to-connect-sticks/
Given
Nropes with different lengths, we need to connect these ropes into one big rope with minimum cost. The cost of connecting two ropes is equal to the sum of their lengths.
function minimumCostToConnectRopes(ropeLengths) {
if (ropeLengths.length === 1) return 0;
ropeLengths.sort((a, b) => a - b);
let totalCost = 0;
while (ropeLengths.length) {
let firstRope = ropeLengths.shift();
let secondRope = ropeLengths.shift();
let currentCost = firstRope + secondRope;
totalCost += currentCost;
if (ropeLengths.length === 0) return totalCost;
//Binary Search
let start = 0;
let end = ropeLengths.length;
while (start < end) {
let mid = start + Math.floor((end - start) / 2);
if (currentCost < ropeLengths[mid]) end = mid;
else start = mid + 1;
}
ropeLengths.splice(start, 0, currentCost);
}
}
console.log(
`Minimum cost to connect ropes: ${minimumCostToConnectRopes([1, 3, 11, 5])}`
);
//33
//First connect 1+3(=4), then 4+5(=9), and then 9+11(=20). So the total cost is 33 (4+9+20)
console.log(
`Minimum cost to connect ropes: ${minimumCostToConnectRopes([3, 4, 5, 6])}`
);
//36
//First connect 3+4(=7), then 5+6(=11), 7+11(=18). Total cost is 36 (7+11+18)
console.log(
`Minimum cost to connect ropes: ${minimumCostToConnectRopes([
1, 3, 11, 5, 2,
])}`
);
//42
//First connect 1+2(=3), then 3+3(=6), 6+5(=11), 11+11(=22). Total cost is 42 (3+6+11+22)- Given
Nropes, we needO(N^2)for the Binary Search. - The space complexity will be
O(1).
https://leetcode.com/problems/top-k-frequent-elements/
Given an unsorted array of numbers, find the top
Kfrequently occurring numbers in it.
function findKFrequentNumbers(nums, k) {
const numMap = new Map();
for (number of nums) {
numMap.set(number, (numMap.get(number) || 0) + 1);
}
const mapKeys = [...numMap.keys()];
const finalIndex = mapKeys.length - k;
let start = 0;
let end = mapKeys.length - 1;
//Quicksort
while (start <= end) {
const pivotPoint = Math.floor(Math.random() * (end - start + 1) + start);
const pivotIndex = pivotHelper(pivotPoint, start, end);
if (pivotIndex === finalIndex) {
return mapKeys.slice(finalIndex);
}
if (pivotIndex < finalIndex) {
start = pivotIndex + 1;
} else {
end = pivotIndex - 1;
}
function pivotHelper(pivotPoint, start, end) {
//move the pivotPoint to the end
[mapKeys[pivotPoint], mapKeys[end]] = [mapKeys[end], mapKeys[pivotPoint]];
let swapIndex = start;
for (let i = start; i < end; i++) {
if (numMap.get(mapKeys[i]) < numMap.get(mapKeys[end])) {
[mapKeys[i], mapKeys[swapIndex]] = [mapKeys[swapIndex], mapKeys[i]];
swapIndex++;
}
}
[mapKeys[end], mapKeys[swapIndex]] = [mapKeys[swapIndex], mapKeys[end]];
return swapIndex;
}
}
}
console.log(
`Here are the K frequent numbers: ${findKFrequentNumbers(
[1, 3, 5, 12, 11, 12, 11],
2
)}`
);
console.log(
`Here are the K frequent numbers: ${findKFrequentNumbers(
[5, 12, 11, 3, 11],
2
)}`
);https://leetcode.com/problems/sort-characters-by-frequency/
Given a string, sort it based on the decreasing frequency of its characters.
function sortCharacterByFrequency(str) {
let counts = {}
for(let char of str){
counts[char] ? counts[char]++ : counts[char] = 1
}
let sortedCharactersArray = Object.keys(counts).sort((a,b) => counts[b] -counts[a])
let sortedString = ""
for(let char of sortedCharactersArray){
sortedString += char.repeat(counts[char])
}
return sortedString
};
console.log('string after sorting characters by frequency: ${sortCharacterByFrequency("Programming")}`)
//"rrggmmPiano"
//'r', 'g', and 'm' appeared twice, so they need to appear before any other character.
console.log('string after sorting characters by frequency: ${sortCharacterByFrequency("abcbab")}`)
//"bbbaac"
//'b' appeared three times, 'a' appeared twice, and 'c' appeared only once.https://leetcode.com/problems/kth-largest-element-in-a-stream/
Design a class to efficiently find the
Kthlargest element in a stream of numbers.The class should have the following two things:
- The constructor of the class should accept an integer array containing initial numbers from the stream and an integer
K.- The class should expose a function
add(num)which will store the given number and return the Kth largest number.
class KthLargest {
constructor(k, nums) {
this.k = k;
this.nums = nums;
}
add(val) {
this.nums = this.nums.sort((a, b) => a - b).splice(-this.k);
if (val > this.nums[0] || this.nums.length < this.k) {
//sort and return kth largest with Binary Search
const insertNewNum = () => {
let start = 0;
let end = this.k;
while (start < end) {
const mid = Math.floor((start + end) / 2);
if (this.nums[mid] === val) return mid;
if (this.nums[mid] < val) {
start = mid + 1;
} else {
end = mid;
}
}
return start;
};
while (this.nums.length > this.k) this.nums.shift();
this.nums.splice(insertNewNum(), 0, val);
}
if (this.nums.length >= this.k) return this.nums[this.nums.length - this.k];
else return null;
}
}
// Input: [3, 1, 5, 12, 2, 11], K = 4
// 1. Calling add(6) should return '5'.
// 2. Calling add(13) should return '6'.
// 2. Calling add(4) should still return '6'.
let kthLargest = new KthLargest(4, [3, 1, 5, 12, 2, 11]);
kthLargest.add(6); // return 5
kthLargest.add(13); // return 6
kthLargest.add(4); // return 6- The time complexity of the above algorithm is
O(NlogN). - The space complexity of the above algorithm is
O(1)
https://leetcode.com/problems/find-k-closest-elements/
Given a sorted number array and two integers
KandX, findKclosest numbers toXin the array. Return the numbers in the sorted order.Xis not necessarily present in the array.
This problem follows the Top K Numbers pattern. The biggest difference in this problem is that we need to find the closest (to X) numbers compared to finding the overall largest numbers. Another difference is that the given array is sorted.
Utilizing a similar approach, we can find the numbers closest to X through the following algorithm:
- Since the array is sorted, we can first find the number closest to
Xthrough Binary Search. Let's say that number isY. - The
Kclosest numbers toYwill be adjacent toYin the array. We can search in both directions ofYto find the closest numbers. - We can use a
heapto efficiently search for the closest numbers. We will takeKnumbers in both directions ofYand push them in aMin Heapsorted by their absolute difference fromX. This will ensure that the numbers with the smallest difference fromX(i.e., closest toX) can be extracted easily fromMin Heap. - Finally, we will extract the top
Knumbers from theMin Heapto find the required numbers.
After finding the number closest to X through Binary Search, we can use the Two Pointers approach to find the K closest numbers. Let’s say the closest number is Y. We can have a left pointer to move back from Y and a right pointer to move forward from Y. At any stage, whichever number pointed out by the left or the right pointer gives the smaller difference from X will be added to our result list.
To keep the resultant list sorted we can use a Queue. So whenever we take the number pointed out by the left pointer, we will append it at the beginning of the list and whenever we take the number pointed out by the right pointer we will append it at the end of the list.
Here is what our algorithm will look like:
function findClosestElements(arr, K, X) {
let windowOfKClosest = [];
let idx = binarySearch(arr, X);
let windowStart = idx;
let windowEnd = idx + 1;
const n = arr.length;
for (let i = 0; i < K; i++) {
if (windowStart >= 0 && windowEnd < n) {
let diffFromStart = Math.abs(X - arr[windowStart]);
let diffFromEnd = Math.abs(X - arr[windowEnd]);
if (diffFromStart <= diffFromEnd) {
windowOfKClosest.unshift(arr[windowStart]);
windowStart--;
} else {
windowOfKClosest.push(arr[windowEnd]);
windowEnd++;
}
} else if (windowStart >= 0) {
windowOfKClosest.unshift(arr[windowStart]);
windowStart--;
} else if (windowEnd < n) {
windowOfKClosest.push(arr[windowEnd]);
windowEnd++;
}
}
return windowOfKClosest;
function binarySearch(arr, X) {
let lo = 0;
let hi = arr.length - 1;
while (lo <= hi) {
const mid = Math.floor(lo + (hi - lo) / 2);
if (arr[mid] === X) {
return mid;
}
if (arr[mid] < X) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
if (lo > 0) {
return lo - 1;
}
return lo;
}
}
console.log(
`'K' closest numbers to 'X' are: ${findClosestElements(
[5, 6, 7, 8, 9],
3,
7
)}`
);
//Output: [6, 7, 8]
console.log(
`'K' closest numbers to 'X' are: ${findClosestElements(
[2, 4, 5, 6, 9],
3,
6
)}`
);
//Output: [4, 5, 6]
console.log(
`'K' closest numbers to 'X' are: ${findClosestElements(
[2, 4, 5, 6, 9],
3,
10
)}`
);
//Output: [5, 6, 9]
console.log(
`'K' closest numbers to 'X' are: ${findClosestElements(
[1, 2, 3, 4, 5],
4,
3
)}`
);
//Output: [1,2,3,4]
console.log(
`'K' closest numbers to 'X' are: ${findClosestElements(
[1, 2, 3, 4, 5],
4,
-1
)}`
);
//Output: [1,2,3,4]- The time complexity of the above algorithm is
O(logN + K). We needO(logN)for Binary Search andO(K)for finding theKclosest numbers using the two pointers. - If we ignoring the space required for the output list, the algorithm runs in constant space
O(1).
https://leetcode.com/problems/least-number-of-unique-integers-after-k-removals/
Given an array of numbers and a number
K, we need to removeKnumbers from the array such that we are left with maximum distinct numbers.
function findMaximumDistinctElements(nums, k) {
let freqMap = new Map();
nums.forEach((number) => {
freqMap.set(number, freqMap.get(number) + 1 || 1);
});
let freq = Array.from(freqMap.values());
freq.sort((a, b) => a - b);
let results = freq.length;
for (let n of freq) {
if (k >= n) {
k -= n;
results--;
} else return results;
}
return results;
}
console.log(`Maximum distinct numbers after removing K numbers:
${findMaximumDistinctElements([5, 5, 4], 1)}`);
//1, Remove the single 4, only 5 is left.
console.log(`Maximum distinct numbers after removing K numbers:
${findMaximumDistinctElements([4, 3, 1, 1, 3, 3, 2], 3)}`);
//2, Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.
console.log(`Maximum distinct numbers after removing K numbers:
${findMaximumDistinctElements([7, 3, 5, 8, 5, 3, 3], 2)}`);
//3, We can remove two occurrences of 3 to be left with 3 distinct numbers [7, 3, 8],
//we have to skip 5 because it is not distinct and appeared twice.
// Another solution could be to remove one instance of '5' and '3' each to be left with
//three distinct numbers [7, 5, 8], in this case, we have to skip 3 because it appeared twice.
console.log(`Maximum distinct numbers after removing K numbers:
${findMaximumDistinctElements([3, 5, 12, 11, 12], 3)}`);
//2, We can remove one occurrence of 12, after which all numbers will become distinct.
//Then we can delete any two numbers which will leave us 2 distinct numbers in the result.
console.log(`Maximum distinct numbers after removing K numbers:
${findMaximumDistinctElements([1, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5], 2)}`); //3, We can remove one occurrence of '4' to get three distinct numbers.- Since we will insert all numbers in a HashMap, this will take
O(N*logN)whereNis the total input numbers. While extracting numbers from the map, in the worst case, we will need to take outKnumbers. This will happen when we have at leastKnumbers with a frequency of two. Since theheapcan have a maximum ofN/2numbers, therefore, extracting an element from theheapwill takeO(logN)and extractingKnumbers will takeO(KlogN). So overall, the time complexity of our algorithm will beO(N*logN + KlogN). We can optimize the above algorithm and only pushKelements in theheap, as in the worst case we will be extractingKelements from theheap. This optimization will reduce the overall time complexity toO(N*logK + KlogK). - The space complexity will be
O(N)as, in the worst case, we need to store all theNcharacters in the HashMap.
https://www.geeksforgeeks.org/sum-elements-k1th-k2th-smallest-elements/
Given an array, find the sum of all numbers between the
K1thandK2thsmallest elements of that array.
function findSumOfElements(nums, k1, k2) {
nums.sort((a, b) => a - b);
let kSlice = nums.slice(k1, k2 - 1);
let kSumBetween = 0;
kSlice.forEach((n) => (kSumBetween += n));
return kSumBetween;
}
console.log(
`Sum of all numbers between k1 and k2 smallest numbers: ${findSumOfElements(
[1, 3, 12, 5, 15, 11],
3,
6
)}`
);
//23
//The 3rd smallest number is 5 and 6th smallest number 15.
// The sum of numbers coming between 5 and 15 is 23 (11+12).
console.log(
`Sum of all numbers between k1 and k2 smallest numbers: ${findSumOfElements(
[3, 5, 8, 7],
1,
4
)}`
);
//12
//The sum of the numbers between the 1st smallest number (3)
//and the 4th smallest number (8) is 12 (5+7).https://leetcode.com/problems/reorganize-string/
Given a string, find if its letters can be rearranged in such a way that no two same characters come next to each other.
function rearrangeString(str) {
//Build a hashMap based on char count
const strMap = new Map();
for (const char of str) {
strMap.set(char, strMap.get(char) + 1 || 1);
}
//sort based on char frequency in descending order
const sortedMap = new Map([...strMap.entries()].sort((a, b) => b[1] - a[1]));
//is first value of sortedMap > half of str.length,
//because a character count that is larger than half of the string length is considered invalid
if (sortedMap.values().next().value > (str.length + 1) / 2) return "";
let result = [];
let index = 0;
for (let [key, value] of sortedMap) {
while (value--) {
//Start filling characters to all the even indexs, i.e. 0, 2, 4,...,
result[index] = key;
index += 2;
// when we got to the end, start filling odd indexes i.e. 1,3,5,...
//By filling the characters this way, we can make sure that no same characters will be adjacent to each other
if (index >= str.length) index = 1;
}
}
return result.join("");
}
console.log(`Rearranged string: ${rearrangeString("aappp")}`);
console.log(`Rearranged string: ${rearrangeString("Programming")}`);
console.log(`Rearranged string: ${rearrangeString("aapa")}`);https://leetcode.com/problems/rearrange-string-k-distance-apart/
Given a string and a number
K, find if the string can be rearranged such that the same characters are at leastKdistance apart from each other.
function rearrangeString(str, k) {
if (str.length < 2 || !k) return str;
const buckets = [];
let a = 'a'.charCodeAt(0);
for (let i = 0; i < str.length; i++) {
let key = str.charCodeAt(i) - a;
buckets[key] = (buckets[key] || 0) + 1;
}
let res = '';
let added = { length: 0 };
while (res.length < str.length) {
let maxIndex = -1;
for (let i = 0; i < buckets.length; i++) {
if (
buckets[i] &&
!added[i] &&
(maxIndex === -1 || buckets[i] > buckets[maxIndex])
) {
maxIndex = i;
}
}
if (maxIndex === -1) return '';
res += String.fromCharCode(a + maxIndex);
buckets[maxIndex]--;
added[maxIndex] = 1;
if (++added.length === k) added = { length: 0 };
}
return res;
}
console.log(`Reorganized string: ${rearrangeString('aabbcc', 3)}`);
//"abcabc"
//The same letters are at least a distance of 3 from each other.
console.log(`Reorganized string: ${rearrangeString('aaabc', 3)}`);
//""
//It is not possible to rearrange the string.
console.log(`Reorganized string: ${rearrangeString('aaadbbcc', 2)}`);
//"abacabcd"
//The same letters are at least a distance of 2 from each other.
console.log(`Reorganized string: ${rearrangeString('Programming', 3)}`);
//"rgmPrgmiano" or "gmringmrPoa" or "gmrPagimnor" and a few more
//All same characters are 3 distance apart.
console.log(`Reorganized string: ${rearrangeString('mmpp', 2)}`);
//"mpmp" or "pmpm"
//All same characters are 2 distance apart.
console.log(`Reorganized string: ${rearrangeString('aab', 2)}`);
//"aba"
//All same characters are 2 distance apart.
`console.log(`Reorganized string: ${rearrangeString('aapa', 3)}`);
//""
//We cannot find an arrangement of the string where any two 'a' are 3 distance apart.https://leetcode.com/problems/task-scheduler/
You are given a list of
tasksthat need to be run, in any order, on a server. Eachtaskwill take one CPU interval to execute but once ataskhas finished, it has a cooling period during which it cant be run again. If the cooling period for all tasks isKintervals, find the minimum number of CPU intervals that the server needs to finish alltasks.If at any time the server can't execute any
taskthen it must stayidle.
This problem follows the Top K Elements pattern and is quite similar to Rearrange String K Distance Apart. We need to rearrange tasks such that same tasks are K distance apart.
❗ Explaination referenced here
Consider the following input:
tasks = ["A", "A", "A", "B", "B", "B", "C", "C", "C", "D", "D", "E"]
n = 2
- First let's find the most frequently occuring task and lay it out like so (an underscore represents a cooldown period):
A _ _ A _ _ A
-
Our goal is to insert all the other tasks into this sequence by filling the cooldown periods first.
-
We know any other task can be scheduled into this sequence without creating additional cooldown slots because:
- The number of occurrences of any task
xis less than or equal to the number occurences of the most frequrntly occuring taskA; and - We can always find a sequence of
kdifferent tasks to schedule between any pair of tasksx.
- Let's insert in the second most frequently occuring task
B(we fill the two cooldown slots first and append the third task to the end):
A B _ A B _ A B
- Next let's insert in the third most frequently occuring task
C(we fill in the two cooldown slots first and append the third task to the end):
A B C A B C A B C
- Next let's insert the fourth most frequently occuring task
D. At this point we've used up all our cooldown slots so we can insert these tasks pretty much anywhere we like as long as there are at leastktasks between every pair ofDtasks.
D A B D C A B C A B C
- Lastly, the least frequently occuring task
Ecan be inserted literally anywhere we like. Because it only occurs once there is no cooldown period we need to respect.
D A B D C A B C A E B C
The sequence above is the shortest possible sequence these tasks can be scheduled in. Note that there are multiple possible sequences of this length.
The answer to the problem is the number of tasks + the number of cooldown periods.
Following a similar approach, we will use a Max Heap to execute the highest frequency task first. After executing a task we decrease its frequency and put it in a waiting list. In each iteration, we will try to execute as many as k+1 tasks. For the next iteration, we will put all the waiting tasks back in the Max Heap . If, for any iteration, we are not able to execute k+1 tasks, the CPU has to remain idle for the remaining time in the next iteration.
class Heap {
constructor(data = []) {
this.data = data;
this.comparator = (a, b) => a - b;
this.heapify();
}
heapify() {
//O(nlog(n))
if (this.size() < 2) return;
for (let i = 1; i < this.size(); i++) {
this.bubbleUp(i);
}
}
peek() {
// O(1)
if (this.size() === 0) return null;
return this.data[0];
}
offer(value) {
// O(log(n))
this.data.push(value);
this.bubbleUp(this.size() - 1);
}
poll() {
// O(log(n))
if (this.size() === 0) return null;
const result = this.data[0];
const last = this.data.pop();
if (this.size() !== 0) {
this.data[0] = last;
this.bubbleDown(0);
}
return result;
}
bubbleUp(index) {
// O(log(n))
while (index > 0) {
const parentIndex = (index - 1) >> 1;
if (this.comparator(this.data[index], this.data[parentIndex]) < 0) {
this.swap(index, parentIndex);
index = parentIndex;
} else {
break;
}
}
}
bubbleDown(index) {
// O(log(n))
const lastIndex = this.size() - 1;
while (true) {
const startIndex = index * 2 + 1;
const endIndex = index * 2 + 2;
let findIndex = ind;
if (
startIndex <= lastIndex &&
this.comparator(this.data[startIndex], this.data[findIndex]) < 0
) {
findIndex = starttIndex;
}
if (
endIndex <= lastIndex &&
this.comparator(this.data[endIndex], this.data[findIndex]) < 0
) {
findIndex = endIndex;
}
if (index !== findIndex) {
this.swap(index, findIndex);
index = findIndex;
} else {
break;
}
}
}
swap(index1, index2) {
// O(1)
[this.data[index1], this.data[index2]] = [
this.data[index2],
this.data[index1],
];
}
size() {
// O(1)
return this.data.length;
}
}
function scheduleTasks(tasks, k) {
let intervalCount = 0;
let taskFreqMap = new Map();
tasks.forEach((char) => {
taskFreqMap.set(char, taskFreqMap.get(char) + 1 || 1);
});
const maxHeap = new Heap();
//add all taks to the heap
Object.keys(taskFreqMap).forEach((char) => {
// 😕
maxHeap.offer([taskFrequencyMap[char], char]);
});
while (maxHeap.length > 0) {
const waitList = [];
let n = k + 1; // try to execute as many as 'k+1' tasks from the max-heap
while (n > 0 && maxHeap.length > 0) {
intervalCount++;
const [frequency, char] = maxHeap.pop();
if (frequency > 1) {
// decrement the frequency and add to the waitList
waitList.push([frequency - 1, char]);
}
n -= 1;
}
// put all the waiting list back on the heap
waitList.forEach((task) => maxHeap.offer(task));
if (maxHeap.length > 0) {
intervalCount += n; // we'll be having 'n' idle intervals for the next iteration
}
}
return intervalCount;
}
console.log(
`Minimum intervals needed to execute all tasks: ${scheduleTasks(
["a", "a", "a", "b", "c", "c"],
2
)}`
);
//7
//a -> c -> b -> a -> c -> idle -> a
console.log(
`Minimum intervals needed to execute all tasks: ${scheduleTasks(
["a", "b", "a"],
3
)}`
);
//5
//a -> b -> idle -> idle -> a- The time complexity of the above algorithm is
O(N∗logN)whereNis the number of tasks. Our while loop will iterate once for each occurrence of the task in the input (i.e.N) and in each iteration we will remove a task from the heap which will takeO(logN)time. Hence the overall time complexity of our algorithm isO(N*logN). - The space complexity will be
O(N), as in the worst case, we need to store all theNtasks in the HashMap.
function scheduleTasks(tasks, k) {
let taskFreqMap = new Map();
let intervalMax = 0;
let taskCountMax = 0;
tasks.forEach((char) => {
taskFreqMap.set(char, taskFreqMap.get(char) + 1 || 1);
//set intervalMax and taskCountMax only if we have a new max
if (taskFreqMap.get(char) > intervalMax) {
intervalMax = taskFreqMap.get(char);
taskCountMax = 1;
} else if (taskFreqMap.get(char) === intervalMax) {
//otherwise, increment taskCountMax
taskCountMax++;
}
});
return Math.max(tasks.length, (intervalMax - 1) * (k + 1) + taskCountMax);
}
console.log(
`Minimum intervals needed to execute all tasks: ${scheduleTasks(
["A", "A", "A", "B", "B", "B"],
2
)}`
);
// 8
// A -> B -> idle -> A -> B -> idle -> A -> B
// There is at least 2 units of time between any two same tasks.
console.log(
`Minimum intervals needed to execute all tasks: ${scheduleTasks(
["A", "A", "A", "B", "B", "B"],
0
)}`
);
// 6
// On this case any permutation of size 6 would work since n = 0.
// ["A","A","A","B","B","B"]
// ["A","B","A","B","A","B"]
// ["B","B","B","A","A","A"]
console.log(
`Minimum intervals needed to execute all tasks: ${scheduleTasks(
["A", "A", "A", "A", "A", "A", "B", "C", "D", "E", "F", "G"],
2
)}`
);
// 16
// One possible solution is
// A -> B -> C -> A -> D -> E -> A -> F -> G -> A
// -> idle -> idle -> A -> idle -> idle -> Ahttps://leetcode.com/problems/maximum-frequency-stack/
Design a class that simulates a Stack data structure, implementing the following two operations:
push(int num): Pushes the numbernumon the stack.pop(): Returns the most frequent number in the stack. If there is a tie, return the number which was pushed later.
❗ Explaination referenced here
There are many ways to solve this problem, but the description gives us two clues as to the most efficient way to do so.
- First, any time the word "frequency" is used, we're most likely going to need to make a frequency map.
- Second, they use the word "stack" in the title, so we should look at the possibility of a stack solution.
In this instance, we should consider a 2D stack, with frequency on one side and input order on the other. This stack will hold each individual instance of a value pushed separately by what the frequency was at the time of insertion.
freqStack will work here because it starts at 1 and will increment from there. If we remember to pop() off unused frequencies, then the top of the frequency dimension of our stack stack[stack.length-1] will always represent the most frequent element, while the top of the input order dimension will represent the most recently seen value.
Our frequency map freqMap() will be used to keep track of the current frequencies of seen elements, so we know where to enter new ones into our stack.
Since our frequencies are 1-indexed and the stack is 0-indexed, we have to insert a dummy 0-index for all languages except Javascript, which lets you directly access even undefined array elements by index.
class FreqStack {
constructor() {
this.freqMap = new Map();
this.freqStack = [];
}
push(value) {
let freq = this.freqMap.get(value) + 1 || 0;
this.freqMap.set(value, freq);
if (!this.freqStack[freq]) {
this.freqStack[freq] = [value];
} else {
this.freqStack[freq].push(value);
}
console.log(this.freqStack);
}
pop() {
let top = this.freqStack[this.freqStack.length - 1];
let value = top.pop();
if (!top.length) this.freqStack.pop();
this.freqMap.set(value, this.freqMap.get(value) - 1);
return value;
}
}
// Input
// ["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"]
// [[], [5], [7], [5], [7], [4], [5], [], [], [], []]
// Output
// [null, null, null, null, null, null, null, 5, 7, 5, 4]
// Explanation
let freqStack = new FreqStack();
freqStack.push(5); // The stack is [5]
freqStack.push(7); // The stack is [5,7]
freqStack.push(5); // The stack is [5,7,5]
freqStack.push(7); // The stack is [5,7,5,7]
freqStack.push(4); // The stack is [5,7,5,7,4]
freqStack.push(5); // The stack is [5,7,5,7,4,5]
freqStack.pop();
// return 5, as 5 is the most frequent. The stack becomes [5,7,5,7,4].
freqStack.pop();
// return 7, as 5 and 7 is the most frequent, but 7 is closest to the top.
//The stack becomes [5,7,5,4].
freqStack.pop();
// return 5, as 5 is the most frequent. The stack becomes [5,7,4].
freqStack.pop();
// return 4, as 4, 5 and 7 is the most frequent, but 4 is closest to the top. The stack becomes [5,7].
let frequencyStack = new FreqStack();
frequencyStack.push(1);
frequencyStack.push(2);
frequencyStack.push(3);
frequencyStack.push(2);
frequencyStack.push(1);
frequencyStack.push(2);
frequencyStack.push(5);
frequencyStack.pop();
// return 2, as it is the most frequent number
frequencyStack.pop();
// should return 1
frequencyStack.pop();
// should return 2- Time Complexity of
O(1)for bothpush()andpop()operations. - Space Complexity of
O(N), whereNis the number of elements in theFreqStack().