347. Top K Frequent Elements

Problem

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

  Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

  Constraints:

• 1 <= nums.length <= 10^5

• -10^4 <= nums[i] <= 10^4

• k is in the range [1, the number of unique elements in the array].

• It is guaranteed that the answer is unique.

  Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

Solution (Java)

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Arrays.sort(nums);
        // Min heap of <number, frequency>
        Queue<int[]> queue = new PriorityQueue<>(k + 1, (a, b) -> (a[1] - b[1]));
        // Filter with min heap
        int j = 0;
        for (int i = 0; i <= nums.length; i++) {
            if (i == nums.length || nums[i] != nums[j]) {
                queue.offer(new int[] {nums[j], i - j});
                if (queue.size() > k) {
                    queue.poll();
                }
                j = i;
            }
        }
        // Convert to int array
        int[] result = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            result[i] = queue.poll()[0];
        }
        return result;
    }
}

Solution (Javascript)

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
  //1. build a hash map : {i => 2, love => 2, leetcode =>1, coding => 1}
  let map = new Map();
  nums.forEach((word) => map.set(word, map.get(word) + 1 || 1));

  //2. build a min-heap with k length (based on hashmap above)
  let minheap = new MinHeap(k);
  let arr = [];
  map.forEach((value, key)=>{
    arr.push({
      key: key,
      priority: value
    })
  })
  minheap.build(arr);

 //3. log out result
  return minheap.get().map(item=>item.key).reverse()
};

const calcDistance =  (point) =>  Math.sqrt( Math.pow(point[0],2) + Math.pow(point[1],2) );

class Heap {
  constructor(size, type) {
    this.data = new Array(size); // SC: O(k)
    this.type = type;
  }

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

  build(arr) {  // O(nlogk)
    let i = 0;
    for (i = 0; i < this.size(); i++) {
      this.data[i] = arr[i]; // O(k)
    }

    /* 
      this step is for bubble UP: 
      calling heapify function on all the parent nodes, 
      the for loop will iterate for each parent node from 
      indices (n - 2) / 2 to 0.
    */
    for (
      let parentIdx = Math.floor((this.size() - 1 - 1) / 2);
      parentIdx >= 0;
      --parentIdx
    ) {
      this._heapify(parentIdx);   // O(klogk)
    }

    /* 
      this step kinda like bubble down, 
      i start as heap size, end as input arr length 
    */
    while (i < arr.length) { // O((n - k) * logk)
   //if heap top is less than next entry, replace the heap top
      if (this.compare(this.data[0], arr[i])) {
        this.data[0] = arr[i];
        this._heapify(0); //ie: parentId is 0
      }
      ++i;
    }

  }

  _heapify(idx) {
    // O(logk)
    const leftIndex = 2 * idx + 1;
    const rightIndex = 2 * idx + 2;
    let p = idx;

    if (
      leftIndex < this.size() &&
      this.compare(this.data[leftIndex], this.data[p])
    ) {
      p = leftIndex;
    }
    if (
      rightIndex < this.size() &&
      this.compare(this.data[rightIndex], this.data[p])
    ) {
      p = rightIndex;
    }
    if (p !== idx) {
      // swap here
      [this.data[p], this.data[idx]] = [this.data[idx], this.data[p]];
      this._heapify(p);
    }
  }

  compare(a, b) { // O(1)
    switch (this.type) {
      case "MIN": // MinHeap
        if (typeof a !== "object" && typeof b !== "object") {
          // a,b are number, string etc..
          return a < b;
        } else {
          // a and b structor is {key: '' , priority: 1}
          // if freq of a < freq of b OR if freq is same but a is lexicographically greater than b then a should be the parent node
          return (
            a.priority < b.priority ||
            (a.priority === b.priority && a.key > b.key)
          );
        }
      case "MAX": //MaxHeap
        if (typeof a !== "object" && typeof b !== "object") {
          return a > b;
        } else {
          return (
            // if freq of a > freq of b OR if freq is same but a is lexicographically smaller than b then a should be the parent node
            a.priority > b.priority ||
            (a.priority === b.priority && a.key < b.key)
          );
        }
      default:
        return "";
    }
  }

  get() {
    // until the heap is empty, create the resultant array by removing elements from the top
    const result = [];
    while (this.size()) {
      const top = this.data[0];
      [this.data[0], this.data[this.size() - 1]] = [
        this.data[this.size() - 1],
        this.data[0]
      ];
      this.data.pop();
      this._heapify(0);
      result.push(top);
    }
    return result;
  }

  insert(item) {
    this.data.push(item);
    this.build(this.data);
  }

  removeRoot() {
    let root = this.data[0];
    let last = this.data.pop();

    if (this.data.length > 0) {
      this.data[0] = last;
      this.build(this.data);
    }
    return root;
  }

  peek() {
    return this.data[0];
  }

}

class MinHeap extends Heap {
  constructor(size) {
    super(size, "MIN");
  }
}

class MaxHeap extends Heap {
  constructor(size) {
    super(size, "MAX");
  }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).