Skip to main content
Mapagam

Finding Top K Elements

1. Understanding Heap-based Selection

Approach Description Time Complexity Space Complexity
Min-Heap Use a min-heap of size k to keep track of the top k elements. For each new element, if it's larger than the smallest in the heap, replace it. O(n log k) O(k)
Max-Heap Use a max-heap to store all elements. Extract the top k elements by popping from the heap. O(n log n) O(n)

Example: Using Min-Heap to Find Top K Elements

const findKthLargest = (nums, k) => {
  const minHeap = new MinHeap();
  for (let num of nums) {
    if (minHeap.size() < k) {
      minHeap.push(num);
    } else if (num > minHeap.top()) {
      minHeap.pop();
      minHeap.push(num);
    }
  }
  return minHeap.top();
};

class MinHeap {
  constructor() {
    this.heap = [];
  }

  push(val) {
    this.heap.push(val);
    this.bubbleUp(this.heap.length - 1);
  }

  pop() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();
    
    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown(0);
    return min;
  }

  top() {
    return this.heap[0];
  }

  size() {
    return this.heap.length;
  }

  bubbleUp(index) {
    if (index === 0) return;
    const parentIndex = Math.floor((index - 1) / 2);
    if (this.heap[parentIndex] > this.heap[index]) {
      [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
      this.bubbleUp(parentIndex);
    }
  }

  bubbleDown(index) {
    const leftChild = 2 * index + 1;
    const rightChild = 2 * index + 2;
    let minIndex = index;

    if (leftChild < this.heap.length && this.heap[leftChild] < this.heap[minIndex]) {
      minIndex = leftChild;
    }

    if (rightChild < this.heap.length && this.heap[rightChild] < this.heap[minIndex]) {
      minIndex = rightChild;
    }

    if (minIndex !== index) {
      [this.heap[index], this.heap[minIndex]] = [this.heap[minIndex], this.heap[index]];
      this.bubbleDown(minIndex);
    }
  }
}
Note: The min-heap approach is preferred for top-k problems when k < n, as it avoids sorting all elements.

2. Finding K Largest Elements

Approach Description Time Complexity Space Complexity
Sorting Sort the array in descending order and pick first K elements. O(n log n) O(1)
Min-Heap Use a min-heap of size K to keep track of the largest K elements. O(n log k) O(k)
QuickSelect Use the QuickSelect algorithm to find the Kth largest element and partition around it. O(n) average, O(n²) worst O(1)

Example: Using Min-Heap

const findKLargest = (nums, k) => {
  const minHeap = new MinHeap();
  for (let num of nums) {
    if (minHeap.size() < k) {
      minHeap.push(num);
    } else if (num > minHeap.top()) {
      minHeap.pop();
      minHeap.push(num);
    }
  }
  return minHeap.toArray();
};

class MinHeap {
  constructor() { this.heap = []; }
  push(val) { /* implementation */ }
  pop() { /* implementation */ }
  top() { return this.heap[0]; }
  size() { return this.heap.length; }
  toArray() { return [...this.heap]; }
}

Example: Using QuickSelect

const findKLargest = (nums, k) => {
  const kthLargestIndex = nums.length - k;
  quickSelect(nums, 0, nums.length - 1, kthLargestIndex);
  return nums.slice(kthLargestIndex).sort((a, b) => b - a);
};

const quickSelect = (nums, left, right, k) => {
  if (left === right) return;
  const pivotIndex = partition(nums, left, right);
  if (k === pivotIndex) return;
  else if (k < pivotIndex) quickSelect(nums, left, pivotIndex - 1, k);
  else quickSelect(nums, pivotIndex + 1, right, k);
};

const partition = (nums, left, right) => {
  const pivot = nums[right];
  let i = left;
  for (let j = left; j < right; j++) {
    if (nums[j] < pivot) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
      i++;
    }
  }
  [nums[i], nums[right]] = [nums[right], nums[i]];
  return i;
};
Note: The QuickSelect approach is efficient for large datasets when K is small relative to N.

3. Finding Kth Largest Element

Approach Description Time Complexity Space Complexity
Sorting Sort the array in descending order and return the element at index k-1. O(n log n) O(1)
Min-Heap Use a min-heap of size k to keep track of the k largest elements. The root of the heap is the kth largest element. O(n log k) O(k)
Quickselect Use the quickselect algorithm to find the kth largest element in average O(n) time. O(n) average O(1)

Example: Using Min-Heap

const findKthLargest = (nums, k) => {
  const minHeap = new MinHeap();
  for (let num of nums) {
    if (minHeap.size() < k) {
      minHeap.push(num);
    } else if (num > minHeap.top()) {
      minHeap.pop();
      minHeap.push(num);
    }
  }
  return minHeap.top();
};

class MinHeap {
  constructor() {
    this.heap = [];
  }
  push(val) {
    this.heap.push(val);
    this.bubbleUp(this.heap.length - 1);
  }
  pop() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();
    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown(0);
    return min;
  }
  top() {
    return this.heap[0];
  }
  size() {
    return this.heap.length;
  }
  bubbleUp(index) {
    if (index === 0) return;
    const parentIndex = Math.floor((index - 1) / 2);
    if (this.heap[parentIndex] > this.heap[index]) {
      [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
      this.bubbleUp(parentIndex);
    }
  }
  bubbleDown(index) {
    const leftChild = 2 * index + 1;
    const rightChild = 2 * index + 2;
    let minIndex = index;

    if (leftChild < this.heap.length && this.heap[leftChild] < this.heap[minIndex]) {
      minIndex = leftChild;
    }
    if (rightChild < this.heap.length && this.heap[rightChild] < this.heap[minIndex]) {
      minIndex = rightChild;
    }

    if (minIndex !== index) {
      [this.heap[index], this.heap[minIndex]] = [this.heap[minIndex], this.heap[index]];
      this.bubbleDown(minIndex);
    }
  }
}

Example: Using Quickselect

const findKthLargest = (nums, k) => {
  return quickSelect(nums, 0, nums.length - 1, k);
};

const quickSelect = (nums, left, right, k) => {
  if (left === right) return nums[left];

  const pivotIndex = partition(nums, left, right);

  if (k === pivotIndex) {
    return nums[k];
  } else if (k < pivotIndex) {
    return quickSelect(nums, left, pivotIndex - 1, k);
  } else {
    return quickSelect(nums, pivotIndex + 1, right, k);
  }
};

const partition = (nums, left, right) => {
  const pivot = nums[right];
  let i = left;

  for (let j = left; j < right; j++) {
    if (nums[j] > pivot) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
      i++;
    }
  }

  [nums[i], nums[right]] = [nums[right], nums[i]];
  return i;
};

4. Finding K Closest Points

Approach Description Time Complexity Space Complexity
Max Heap Use a max heap of size k to keep track of the k closest points. For each point, calculate distance and maintain heap. O(n log k) O(k)
Quickselect Use quickselect algorithm to find the kth closest point, then return all points up to that threshold. O(n) average O(1)

Example: Max Heap Implementation

function kClosest(points, k) {
  const maxHeap = new MaxHeap();
  
  for (const point of points) {
    const dist = point[0] * point[0] + point[1] * point[1];
    
    if (maxHeap.size() < k) {
      maxHeap.push({ point, dist });
    } else if (dist < maxHeap.peek().dist) {
      maxHeap.pop();
      maxHeap.push({ point, dist });
    }
  }
  
  return maxHeap.toArray().map(item => item.point);
}

Example: Quickselect Implementation

function kClosest(points, k) {
  const distances = points.map(p => ({
    point: p,
    dist: p[0] * p[0] + p[1] * p[1]
  }));
  
  quickSelect(distances, 0, distances.length - 1, k - 1);
  
  return distances.slice(0, k).map(item => item.point);
}

function quickSelect(arr, left, right, k) {
  if (left === right) return;
  
  const pivotIndex = partition(arr, left, right);
  
  if (pivotIndex === k) return;
  else if (pivotIndex > k) quickSelect(arr, left, pivotIndex - 1, k);
  else quickSelect(arr, pivotIndex + 1, right, k);
}
Note: The max heap approach is more intuitive and easier to understand, while quickselect offers better average-case performance for large datasets.

5. Finding Top K Frequent Elements

Approach Description Time Complexity Space Complexity
HashMap + Min-Heap Count frequencies using HashMap, maintain a min-heap of size k to track top k elements O(n log k) O(n + k)
QuickSelect Use partitioning to find elements with frequencies in top k range O(n) average O(n)
Sorting Sort elements by frequency in descending order, take first k O(n log n) O(n)

Example: Using HashMap + Min-Heap

const topKFrequent = (nums, k) => {
  const freqMap = new Map();
  for (const num of nums) {
    freqMap.set(num, (freqMap.get(num) || 0) + 1);
  }

  const minHeap = new MinHeap();
  for (const [num, freq] of freqMap) {
    if (minHeap.size() < k) {
      minHeap.push({ num, freq });
    } else if (freq > minHeap.peek().freq) {
      minHeap.pop();
      minHeap.push({ num, freq });
    }
  }

  return minHeap.toArray().map(item => item.num);
};

Example: Using QuickSelect

const topKFrequent = (nums, k) => {
  const freqMap = new Map();
  for (const num of nums) {
    freqMap.set(num, (freqMap.get(num) || 0) + 1);
  }

  const freqArray = Array.from(freqMap.entries()).map(([num, freq]) => ({ num, freq }));
  quickSelect(freqArray, 0, freqArray.length - 1, k);

  return freqArray.slice(0, k).map(item => item.num);
};

const quickSelect = (arr, left, right, k) => {
  if (left < right) {
    const pivotIndex = partition(arr, left, right);
    if (pivotIndex === k - 1) return;
    else if (pivotIndex < k - 1) {
      quickSelect(arr, pivotIndex + 1, right, k);
    } else {
      quickSelect(arr, left, pivotIndex - 1, k);
    }
  }
};

const partition = (arr, left, right) => {
  const pivot = arr[right].freq;
  let i = left - 1;

  for (let j = left; j < right; j++) {
    if (arr[j].freq > pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }

  [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
  return i + 1;
};
Note: The QuickSelect approach has O(n) average time complexity but can be O(n^2) in worst case. The heap-based approach is more predictable and generally preferred for interviews.

6. Sorting Array by Frequency

Method Description Time Complexity Space Complexity
HashMap + Sorting Count frequencies using a hash map, then sort keys by frequency. O(n log n) O(n)
Heap (Min-Heap) Use a min-heap of size k to keep top k frequent elements. O(n log k) O(n)
Bucket Sort Group elements by frequency in buckets, then collect from highest to lowest. O(n) O(n)

Example: Using HashMap + Sorting

const nums = [1, 1, 2, 2, 3];
const k = 2;

const freqMap = new Map();
for (let num of nums) {
  freqMap.set(num, (freqMap.get(num) || 0) + 1);
}

const sorted = [...freqMap.entries()].sort((a, b) => b[1] - a[1]);
const result = sorted.slice(0, k).map(pair => pair[0]);

console.log(result); // [1, 2]

Example: Using Min-Heap

const nums = [1, 1, 2, 2, 3];
const k = 2;

const freqMap = new Map();
for (let num of nums) {
  freqMap.set(num, (freqMap.get(num) || 0) + 1);
}

class MinHeap {
  constructor() {
    this.heap = [];
  }

  push(val) {
    this.heap.push(val);
    this.bubbleUp(this.heap.length - 1);
  }

  pop() {
    if (this.heap.length === 0) return null;
    const min = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.bubbleDown(0);
    }
    return min;
  }

  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[parentIndex][1] <= this.heap[index][1]) break;
      [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
      index = parentIndex;
    }
  }

  bubbleDown(index) {
    const len = this.heap.length;
    while (true) {
      const leftChild = 2 * index + 1;
      const rightChild = 2 * index + 2;
      let minIndex = index;

      if (leftChild < len && this.heap[leftChild][1] < this.heap[minIndex][1]) {
        minIndex = leftChild;
      }
      if (rightChild < len && this.heap[rightChild][1] < this.heap[minIndex][1]) {
        minIndex = rightChild;
      }

      if (minIndex === index) break;
      [this.heap[index], this.heap[minIndex]] = [this.heap[minIndex], this.heap[index]];
      index = minIndex;
    }
  }

  size() {
    return this.heap.length;
  }
}

const minHeap = new MinHeap();
for (let [num, freq] of freqMap.entries()) {
  if (minHeap.size() < k) {
    minHeap.push([num, freq]);
  } else if (freq > minHeap.heap[0][1]) {
    minHeap.pop();
    minHeap.push([num, freq]);
  }
}

const result = [];
while (minHeap.size() > 0) {
  result.push(minHeap.pop()[0]);
}

console.log(result); // [1, 2]

7. Finding K Closest Numbers

Approach Description Time Complexity Space Complexity
Two Pointers Use two pointers to find the k closest elements from a sorted array to a target value. O(n) O(1)
Binary Search + Heap Use binary search to find the insertion point, then use a max-heap to maintain k closest elements. O(log n + k log k) O(k)
Min-Heap Use a min-heap to keep track of elements based on their distance from the target. O(n log n) O(n)

Example: Two Pointers Approach

function findClosestElements(arr, k, x) {
    let left = 0;
    let right = arr.length - 1;

    while (right - left >= k) {
        if (Math.abs(arr[left] - x) > Math.abs(arr[right] - x)) {
            left++;
        } else {
            right--;
        }
    }

    return arr.slice(left, right + 1);
}

// Example usage:
const arr = [1, 2, 3, 4, 5];
const k = 4;
const x = 3;
console.log(findClosestElements(arr, k, x)); // [1, 2, 3, 4]

Example: Binary Search + Heap Approach

function findClosestElements(arr, k, x) {
    let left = 0;
    let right = arr.length - 1;

    // Binary search to find the insertion point
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] < x) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    let start = Math.max(0, left - k);
    let end = Math.min(arr.length - 1, left + k);

    // Create a min-heap based on distance from x
    const heap = new MinHeap();
    for (let i = start; i <= end; i++) {
        heap.push({ value: arr[i], distance: Math.abs(arr[i] - x) });
    }

    // Extract k closest elements
    const result = [];
    for (let i = 0; i < k; i++) {
        result.push(heap.pop().value);
    }

    return result.sort((a, b) => a - b);
}

class MinHeap {
    constructor() {
        this.heap = [];
    }

    push(val) {
        this.heap.push(val);
        this.bubbleUp(this.heap.length - 1);
    }

    pop() {
        if (this.heap.length === 0) return null;
        const min = this.heap[0];
        const last = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = last;
            this.bubbleDown(0);
        }
        return min;
    }

    bubbleUp(index) {
        if (index === 0) return;
        const parentIndex = Math.floor((index - 1) / 2);
        if (this.heap[parentIndex].distance > this.heap[index].distance) {
            [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
            this.bubbleUp(parentIndex);
        }
    }

    bubbleDown(index) {
        const leftChild = 2 * index + 1;
        const rightChild = 2 * index + 2;
        let minIndex = index;

        if (leftChild < this.heap.length && this.heap[leftChild].distance < this.heap[minIndex].distance) {
            minIndex = leftChild;
        }

        if (rightChild < this.heap.length && this.heap[rightChild].distance < this.heap[minIndex].distance) {
            minIndex = rightChild;
        }

        if (minIndex !== index) {
            [this.heap[index], this.heap[minIndex]] = [this.heap[minIndex], this.heap[index]];
            this.bubbleDown(minIndex);
        }
    }
}

// Example usage:
const arr = [1, 2, 3, 4, 5];
const k = 4;
const x = 3;
console.log(findClosestElements(arr, k, x)); // [1, 2, 3, 4]
Note: The two pointers approach is generally preferred for its simplicity and linear time complexity.

8. Finding Maximum Distinct Elements

Approach Description Time Complexity Space Complexity
Hash Set Use a hash set to store unique elements and count distinct values. O(n) O(n)
Sorting + Counting Sort the array and count distinct elements by comparing adjacent elements. O(n log n) O(1) (if sorting in-place)
Heap + Hash Map Use a min-heap to keep track of top k distinct elements and a hash map for frequency. O(n log k) O(k)

Example: Using Hash Set

const findDistinctElements = (arr) => {
  const set = new Set(arr);
  return set.size;
};

// Example usage:
const array = [1, 2, 2, 3, 4, 4, 5];
console.log(findDistinctElements(array)); // Output: 5

Example: Using Sorting

const findDistinctElements = (arr) => {
  if (arr.length === 0) return 0;
  
  arr.sort((a, b) => a - b);
  let count = 1;
  
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] !== arr[i - 1]) {
      count++;
    }
  }
  
  return count;
};

// Example usage:
const array = [1, 2, 2, 3, 4, 4, 5];
console.log(findDistinctElements(array)); // Output: 5
Note: The hash set approach is preferred for its simplicity and linear time complexity.

9. Finding Sum of K Elements

Approach Description Time Complexity Space Complexity
Sorting Sort the array and take the first K elements. Sum them. O(n log n) O(1)
Min-Heap Use a min-heap of size K to keep track of the largest elements. O(n log k) O(k)
QuickSelect Use QuickSelect to find the Kth largest element, then sum all elements >= it. O(n) average O(1)

Example: Using Min-Heap

const findSumOfK = (arr, k) => {
  const minHeap = new MinHeap();
  for (let num of arr) {
    if (minHeap.size() < k) {
      minHeap.push(num);
    } else if (num > minHeap.top()) {
      minHeap.pop();
      minHeap.push(num);
    }
  }

  let sum = 0;
  while (minHeap.size()) {
    sum += minHeap.pop();
  }
  return sum;
};

Example: Using QuickSelect

const findSumOfK = (arr, k) => {
  const kthLargest = quickSelect(arr, 0, arr.length - 1, arr.length - k);
  let sum = 0;
  for (let num of arr) {
    if (num >= kthLargest) sum += num;
  }
  return sum;
};

10. Rearranging String K Distance Apart

Given a string and an integer k, rearrange the string such that the same characters are at least k distance apart. If it's not possible, return an empty string.

Property Description Example
Input String and integer k "aabbcc", k = 3
Output Rearranged string or empty string if impossible "abcabc"

Example: Rearranging String

function rearrangeStringKDistanceApart(s, k) {
    const charCount = {};
    for (let char of s) {
        charCount[char] = (charCount[char] || 0) + 1;
    }

    const maxHeap = new MaxHeap();
    for (let [char, count] of Object.entries(charCount)) {
        maxHeap.push({ char, count });
    }

    const result = [];
    const queue = [];

    while (!maxHeap.isEmpty()) {
        const current = maxHeap.pop();
        result.push(current.char);
        queue.push({ char: current.char, count: current.count - 1 });

        if (queue.length >= k) {
            const front = queue.shift();
            if (front.count > 0) {
                maxHeap.push({ char: front.char, count: front.count });
            }
        }
    }

    return result.length === s.length ? result.join('') : '';
}

class MaxHeap {
    constructor() {
        this.heap = [];
    }

    push(val) {
        this.heap.push(val);
        this.bubbleUp(this.heap.length - 1);
    }

    pop() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();

        const max = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown(0);
        return max;
    }

    isEmpty() {
        return this.heap.length === 0;
    }

    bubbleUp(index) {
        if (index === 0) return;
        const parentIndex = Math.floor((index - 1) / 2);
        if (this.heap[parentIndex].count < this.heap[index].count) {
            [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
            this.bubbleUp(parentIndex);
        }
    }

    bubbleDown(index) {
        const left = 2 * index + 1;
        const right = 2 * index + 2;
        let maxIndex = index;

        if (left < this.heap.length && this.heap[left].count > this.heap[maxIndex].count) {
            maxIndex = left;
        }

        if (right < this.heap.length && this.heap[right].count > this.heap[maxIndex].count) {
            maxIndex = right;
        }

        if (maxIndex !== index) {
            [this.heap[index], this.heap[maxIndex]] = [this.heap[maxIndex], this.heap[index]];
            this.bubbleDown(maxIndex);
        }
    }
}

// Example usage:
console.log(rearrangeStringKDistanceApart("aabbcc", 3)); // "abcabc"
console.log(rearrangeStringKDistanceApart("aaabc", 3)); // ""
Note: If k = 0, any arrangement is valid. If k >= s.length, it's impossible unless all characters are the same.

Key Points

  • Use a max heap to always select the most frequent character.
  • Use a queue to keep track of characters that are too recent to be reused.
  • If the queue size exceeds k, it's safe to reuse a character.
  • Return empty string if rearrangement is impossible.

11. Scheduling Tasks with Constraints

Task Property Description Constraints
task.id Unique identifier for the task Must be unique within the schedule
task.duration Time required to complete the task Non-negative integer
task.dependencies List of tasks that must complete before this one starts Array of task IDs or empty array
task.resources Resources required to execute the task Array of resource names or empty array
task.deadline Latest time the task can finish ISO 8601 timestamp or null

Example: Basic Task Scheduling

const tasks = [
  {
    id: "task1",
    duration: 2,
    dependencies: [],
    resources: ["cpu"],
    deadline: "2026-04-15T18:00:00Z"
  },
  {
    id: "task2",
    duration: 3,
    dependencies: ["task1"],
    resources: ["cpu", "memory"],
    deadline: "2026-04-15T20:00:00Z"
  }
];

function scheduleTasks(tasks) {
  const schedule = [];
  const readyTasks = tasks.filter(task => task.dependencies.length === 0);
  
  while (readyTasks.length > 0) {
    const task = readyTasks.shift();
    schedule.push(task);
    
    // Update dependencies for other tasks
    tasks.forEach(t => {
      const index = t.dependencies.indexOf(task.id);
      if (index !== -1) {
        t.dependencies.splice(index, 1);
        if (t.dependencies.length === 0) {
          readyTasks.push(t);
        }
      }
    });
  }

  return schedule;
}

const scheduled = scheduleTasks(tasks);
console.log(scheduled);
Note: This example uses a simple topological sort to schedule tasks with dependencies. For more complex constraints like resource availability or time windows, additional algorithms such as constraint satisfaction or integer programming may be required.

12. Finding Frequency Sort

Property Description Usage
frequencyMap Map storing element frequencies const freq = new Map();
topKElements Result array of top K elements by frequency const result = [];

Example: Frequency Sort

const nums = [1, 1, 2, 2, 3];
const k = 2;

// Step 1: Build frequency map
const freq = new Map();
for (let num of nums) {
  freq.set(num, (freq.get(num) || 0) + 1);
}

// Step 2: Sort by frequency descending
const sorted = [...freq.entries()].sort((a, b) => b[1] - a[1]);

// Step 3: Take top K elements
const result = sorted.slice(0, k).map(pair => pair[0]);

console.log(result); // [1, 2]
Note: This approach has O(n log n) time complexity due to sorting.

Time & Space Complexity

  • Time: O(n log n) where n is the number of unique elements
  • Space: O(n) for frequency map and sorted array

Was this article helpful?

Related Cheat Sheets