Recognizing Heap and Sorting Pattern Signals
1. Recognizing Top K Elements Signal
| Signal Indicators | Description | Common Use Cases |
|---|---|---|
| Find k largest/smallest elements | Problem asks for the top k elements from a dataset based on some criteria (e.g., highest scores, shortest distances) | Ranking systems, leaderboard generation, finding outliers |
| Frequency counting with limits | Need to identify elements that occur most/least frequently, up to k occurrences | Text analysis, data mining, trend identification |
| Kth largest/smallest element | Specifically asking for the kth element in a sorted list or stream | Statistical analysis, performance benchmarking |
Example: Find Top 3 Scores in a List
const scores = [85, 92, 78, 96, 88, 91];
const top3 = scores
.sort((a, b) => b - a)
.slice(0, 3);
console.log(top3); // [96, 92, 91]Example: Using Min-Heap for Efficient Top K
class MinHeap {
constructor() {
this.heap = [];
}
push(val) {
this.heap.push(val);
this.bubbleUp();
}
pop() {
if (this.heap.length === 1) return this.heap.pop();
const min = this.heap[0];
this.heap[0] = this.heap.pop();
this.bubbleDown();
return min;
}
bubbleUp() {
let index = this.heap.length - 1;
while (index > 0) {
const parentIndex = Math.floor((index - 1)/2);
if (this.heap[parentIndex] <= this.heap[index]) break;
[this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
index = parentIndex;
}
}
bubbleDown() {
let index = 0;
while (true) {
const leftChild = 2 * index + 1;
const rightChild = 2 * index + 2;
let smallest = index;
if (leftChild < this.heap.length && this.heap[leftChild] < this.heap[smallest]) {
smallest = leftChild;
}
if (rightChild < this.heap.length && this.heap[rightChild] < this.heap[smallest]) {
smallest = rightChild;
}
if (smallest === index) break;
[this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
index = smallest;
}
}
size() {
return this.heap.length;
}
}
function topKFrequent(nums, k) {
const freqMap = {};
for (const num of nums) {
freqMap[num] = (freqMap[num] || 0) + 1;
}
const minHeap = new MinHeap();
for (const [num, freq] of Object.entries(freqMap)) {
if (minHeap.size() < k) {
minHeap.push(freq);
} else if (freq > minHeap.heap[0]) {
minHeap.pop();
minHeap.push(freq);
}
}
const result = [];
for (const [num, freq] of Object.entries(freqMap)) {
if (freq >= minHeap.heap[0]) {
result.push(Number(num));
}
}
return result;
}
console.log(topKFrequent([1,1,1,2,2,3], 2)); // [1, 2]
Note: For problems involving finding top K elements, a min-heap of size K is often more efficient than sorting the entire dataset.
2. Recognizing Median Signal
| Signal | Description | Common Use Cases | Examples |
|---|---|---|---|
| Odd-length array | Array has an odd number of elements, indicating a single median value exists | Calculating central tendency in statistics | [1, 3, 5] → median = 3 |
| Even-length array | Array has an even number of elements, requiring average of two middle values | Statistical analysis and data summarization | [2, 4, 6, 8] → median = (4 + 6) / 2 = 5 |
| Sorted input | Input is already sorted or can be efficiently sorted | Efficient median calculation using binary search | [1, 2, 3, 4, 5] → median = 3 |
| Stream of data | Processing data in real-time or batches where median needs to be updated | Real-time analytics, sliding window statistics | Use min/max heaps to maintain median in streaming data |
Example: Finding Median in Sorted Array
function findMedian(sortedArray) {
const n = sortedArray.length;
if (n % 2 === 1) {
return sortedArray[Math.floor(n / 2)];
} else {
const mid1 = sortedArray[n / 2 - 1];
const mid2 = sortedArray[n / 2];
return (mid1 + mid2) / 2;
}
}
// Example usage:
const arr = [1, 3, 5, 7, 9];
console.log(findMedian(arr)); // Output: 5Example: Median in Sliding Window
class MedianFinder {
constructor() {
this.small = new MaxHeap(); // max heap for smaller half
this.large = new MinHeap(); // min heap for larger half
}
addNum(num) {
if (this.small.size() === 0 || num <= this.small.peek()) {
this.small.push(num);
} else {
this.large.push(num);
}
// Rebalance heaps
if (this.small.size() > this.large.size() + 1) {
this.large.push(this.small.pop());
} else if (this.large.size() > this.small.size() + 1) {
this.small.push(this.large.pop());
}
}
findMedian() {
if (this.small.size() > this.large.size()) {
return this.small.peek();
} else if (this.large.size() > this.small.size()) {
return this.large.peek();
} else {
return (this.small.peek() + this.large.peek()) / 2;
}
}
}
Note: When working with streams or large datasets, maintaining two heaps (max and min) allows for efficient median updates in O(log n) time per insertion.
3. Recognizing K Sorted Lists/Arrays Signal
When you encounter a problem involving multiple sorted lists or arrays, and need to merge them efficiently, it's a strong signal for using heap-based algorithms.
| Signal | Description | Use Case |
|---|---|---|
| Multiple sorted lists/arrays | Each list is sorted individually, but the overall goal is to merge them into one sorted sequence. | Merging k sorted linked lists or arrays |
| Need for efficient merging | Each list is already sorted, so the optimal approach uses a min-heap to always pick the smallest element. | External sorting, merge k sorted streams |
Example: Merging K Sorted Lists
class ListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
function mergeKLists(lists) {
const heap = new MinHeap();
for (let list of lists) {
if (list) heap.push(list);
}
const dummy = new ListNode(0);
let current = dummy;
while (!heap.isEmpty()) {
const node = heap.pop();
current.next = new ListNode(node.val);
current = current.next;
if (node.next) heap.push(node.next);
}
return dummy.next;
}
Note: The key insight is that we maintain a min-heap of the smallest elements from each list, ensuring optimal selection at every step.
4. Recognizing Intervals/Scheduling Signal
| Signal | Description | Common Use Cases |
|---|---|---|
| Overlapping intervals | When multiple time ranges intersect or overlap | Meeting scheduling, resource allocation, task planning |
| Non-overlapping intervals | When intervals do not intersect but may touch | Activity scheduling, job sequencing, event planning |
| Interval merging | Combining overlapping intervals into one | Data analysis, range queries, memory management |
| Interval counting | Counting how many intervals are active at any time | Event monitoring, resource usage tracking, traffic analysis |
| Interval insertion | Inserting a new interval into an existing set | Calendar apps, task management systems, scheduling tools |
Example: Merging Overlapping Intervals
function mergeIntervals(intervals) {
if (intervals.length <= 1) return intervals;
intervals.sort((a, b) => a[0] - b[0]);
const merged = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const current = intervals[i];
const last = merged[merged.length - 1];
if (current[0] <= last[1]) {
last[1] = Math.max(last[1], current[1]);
} else {
merged.push(current);
}
}
return merged;
}
// Example usage:
const intervals = [[1, 3], [2, 6], [8, 10], [15, 18]];
console.log(mergeIntervals(intervals)); // [[1, 6], [8, 10], [15, 18]]
Example: Counting Active Intervals
function countActiveIntervals(intervals) {
const events = [];
for (const [start, end] of intervals) {
events.push({ time: start, type: 'start' });
events.push({ time: end, type: 'end' });
}
events.sort((a, b) => {
if (a.time === b.time) {
return a.type === 'start' ? -1 : 1;
}
return a.time - b.time;
});
let maxActive = 0;
let activeCount = 0;
for (const event of events) {
if (event.type === 'start') {
activeCount++;
maxActive = Math.max(maxActive, activeCount);
} else {
activeCount--;
}
}
return maxActive;
}
// Example usage:
const intervals = [[1, 4], [2, 5], [7, 9]];
console.log(countActiveIntervals(intervals)); // 2
Note: When working with intervals, sorting by start time is often the first step to simplify overlap detection and merging logic.